基于c++的文本内容比较的实现

摘要 本文介绍了一种对文本内容进行比较的简易算法，该算法可以找出两段文本内容的差异位置、差异类型(错、漏、多打处数和字数)并统计出各类错误的数量，最后给出了较完整的算法，该算法也可以用来对程序文件等进行比较和校对。 关键词：文本比较，算法；C++ builder； 目录摘要??? 2Abstract??? 3一、绪论??? 61.1问题的提出??? 61.2课题开发背景??? 71.3系统问题分析??? 7二、系统开发工具和开发平台??? 82.1、开发工具简介??? 82.1.1关于C++ Builder??? 82.1.2 C++ Builder主要特点??? 82.1.3 C++ Builder与Delphi和VC++的比较??? 92.2、系统运行环境??? 102.2.1软件运行平台??? 102.2.2硬件运行平台??? 10三、系统需求分析??? 103.1可行性分析??? 113.1.1经济可行性分析??? 113.1.2 技术可行性分析??? 113.2文本比较的基本问题??? 123.2.1效率问题??? 123.2.2结果的显示问题??? 123.3算法设计??? 123.3.1常用文本比较算法介绍??? 12四、系统总体设计??? 144.1系统基本情况描述??? 14五、系统详细设计与实现??? 175.1主模块设计??? 175.1.1界面设计??? 175.1.2文件打开加载操作??? 185.3 显示模块实现??? 205.4文本比较算法??? 215.4.1随机排课算法的相关数据结构??? 215.4.2文本比较算法的相关函数??? 215.3.3比较算法??? 27六、系统测试与使用说明??? 296.1测试??? 296.2操作说明??? 29结论??? 32致谢??? 32参考文献??? 33 算法设计 3.3.1常用文本比较算法介绍 1）字符串匹配算法 一个字符串是一个定义在有限字母表上的字符串字符串的匹配问题就是在一个大的字符串中搜索某个字符串出现的位置的问题。根据搜索方式的不同，字符串匹配算法可以归结为以下两种基本方法。第一种是逐个读取字符，每读入一个字符就更新相应的新位置变量，检查是否存在一个可能的匹配。第二种是基于滑动窗的匹配方式。 2）过滤算法 过滤算法就是在匹配的时候最大可能的跳过那些不可能存在的大块区域，然后再利用一个飞过滤算法来实现剩下的区域是否匹配。 3）BF(Brute Force)算法 又称蛮力匹配算法，是一种效率很低的算法。其主要思想是模式的第一个字符与文本的第一个字符进行比较，如果相同，就继续比较后面的字符，否则，文本的起始位置加1，即模式右移一个位置，再进行比较。如果模式与文本中一段连续字符串都相同，则匹配成功，返回当时文本的起始比较位置，否则匹配不成功。 4）KMP算法 KMP(Knuth—Morris—Pratt)算法是D．E．Knuth、J．H．Morris和v．R．Pratt三人于i977年提出来的，其核心思想是：在发生失配时，正文不需要回溯，而是利用已经得到的“部分匹配”结果将模式右移尽可能远的距离，继续进行比较。这里要强调的是，模式不一定向右移动一个字符的位置，右移也不一定必须从模式起点处重新匹配，即模式一次可以右移多个字符的位置，右移后可以从模式起点后的某处开始试匹配。假设发生失配时，text[i]≠pat[J]，1≤i≤11≤j≤m，则下一轮比较时，text[i]应与pat[next[j]]对齐往。 5）BM算法 受KMP算法的启发，Boyer和Moore提出了一种新的字符串快速匹配算法一BM算法。它是从另外一个角度出发，提出一种比较新颖的方法来求解模式匹配问题 。其基本思想是从右向左的把模式同文本做比较。开始时仍是P的最左边与T的最左边对齐，当某趟比较中出现不匹配时，BM算法采用两条启发性规则计算模式串右移的距离，即坏字符启发规则和好后缀启发规则；当与最右的模式符号做比较的文本符号在模式中根本就没有出现，则模式可以在这个文本符号之后移位m个位置。