【纠错算法】

纠错算法（Error correction algorithm）是建立在概率统计的基础上的：出现2个差错的概率远小于出现1个差错的概率，而出现3个差错的概率又远小于出现2个差错的概率。从而有理由认为：当接收到的代码是一个非法的代码时，它的正确代码应该是在逻辑空间中离它最近的有效代码。

 

工作原理

汉明码

如果某种编码的合法代码之间的最小码距为1（所有的顺序编码都是如此），显然没有检错能力，更没有纠错能力。要想使得其具有纠错能力，必须进行改造，或者按某种纠错码格式重新编码，或者在原编码的基础上附加一部分代码，使其满足纠错码的条件。后一种方法比较方便，只是在发送时临时附加一部分代码，接收端利用它进行纠错处理后就舍弃，使原代码部分维持不变，汉明码就是这一类型的纠错码。

 

检二纠一码

包含4位有效信息的汉明码只能发现并纠正一个差错，如果出现两个差错，就会被它强行“纠正”成另外一个合法代码，造成不被发现的错误。例如发方将十六进制数6按7位汉明码66H发出，在接收过程中如果出现两个差错而变成60H，经纠错处理使得到68H，还原后就成为十六进制数8，这就产生了错误。能否进一步提高编码的性能，使它在出现两个差错时能够及时发现而不乱加纠正呢？根据检错理论，只要将有效编码之前的最小码距加大到4就可以达到这个目的，这就是“检二纠一码”。

7位汉明码在实际使用中是用1字节来表示的，如果把浪费了的1位也利用起来，无疑会进一步提供抗干扰性能。

要想在不加大码距的前提下，纠正连续多位差错，提供抵抗突发干扰的能力，方法就是将编码后的汉明码重新进行组织排列。以16位的汉明码为例，把11字节的数据编码为16字节的汉明码后再按高低字节分成两组。把每组字节8个汉明码的第1位分别取出，组成1字节；然后再把这8字节吗的第2位取出，组成第2字节；依此类推，将这组8字节汉明码处理完毕，得到新的8字节编码。只要在纠错前把受干扰的编码恢复原来正常的排列顺序，就可通过计算校验码完成差错的定位及纠错

 

 

 常见的英文单词纠错法有：，主要有误拼词典法、词形距离法、最小编辑距离法、相似键法、骨架键法、N-gram法、基于规则的技术、词典及神经网络技术。

(1)误拼字典法。收集大规模真实文本中拼写出错的英文单词并给出相应的正确拼写，建造一个无歧义的误拼字典。在进行英文单词拼写检查时，查找误拼字典，如命中，则说明该单词拼写有误，该词的正确拼写字段为纠错建议。该方法的特点是侦错和纠错一体化，效率高。但英文拼写错误具有随机性，很难保证误拼字典的无歧义性和全面性，因此查准率低、校对效果差。

(2)词形距离法。这是一种基于最大相似度和最小串间距离的英文校对法。其核心思想是构造单词的似然性函数，如该单词在词典中，则单词拼写正确；否则，按照似然性函数，在词典中找到一个与误拼单词最相似的词作为纠错候选词。该方法的特点是节省存储空间，能反映一定的常见拼写错误统计规律，是一种模糊校对法。

(3)最小编辑距离法。通过计算误拼字符串与词典中某个词间的最小编辑距离来确定纠错候选词。所谓最小编辑距离是指将一个词串转换为另一个词串所需的最少的编辑操作次数(编辑操作是指插入、删除、易位和替换等)。还有人提出了反向最小编辑距离法，这种方法首先对每个可能的单个错误进行交换排列，生成一个候选集，然后，通过查词典看哪些是有

效的单词，并将这些有效的单词作为误拼串的纠错建议。

(4)相似键法。相似键技术是将每个字符串与一个键相对应。使那些拼写相似的字符串具有相同或相似的键。当计算出某个误拼字符串的键值之后，它将给出一个指针。指向所有与该误拼字符串相似的单词，并将它们作为给误拼字符串的纠错建议。

(5)骨架键法。通过构建骨架键词典，在英文单词出现错误时，先抽取出该错误单词的骨架键，然后再去查骨架键词典，将词典中与该单词具有相同骨架键的正确单词作为该单词的纠错建议。

(6)N-gram法。基于n元文法，通过对大规模英文文本的统计得到单词与单词问的转移概率矩阵。当检测到某英文单词不在词典中时。查转移概率矩阵，取转移概率大于某给定阈值的单词为纠错建议。

(7)基于规则的技术。利用规则的形式将通常的拼写错误模式进行表示，这些规则可用来将拼写错误蛮换为有效的单词。对于一个误拼字符串，应用所有合适的规则从词典中找到一些与之对应的单词作为结果，并对每个结果根据事先赋予生成它的规则的概率估计计算一个数值，根据这个数值对所有候选结果排序。