2023年7月20日发(作者：)

常见经典字符串匹配算法简要介绍 柔性的字符串匹配pdf下载地址 在⽹络安全的研究中，字符串匹配是⼀种使⽤普遍⽽关键的技术，如杀毒软件、IDS中的特征码匹配、内容过滤等，都需要⽤到字符串匹配。作为字符串匹配中的⼀种特殊情况，近似字符串匹配的研究也同样重要。这⾥对经典的字符串匹配算法与思想进⾏简要分析和总结。本⽂的主要参考了《柔性字符串匹配》⼀书。不可多得的⼀部专业书籍，有兴趣者可移步这⾥下载PDF电⼦书：柔性字符串匹配下载地址⼀ 精确字符串匹配字符串的精确匹配算法中，最著名的有KMP算法和BM算法。下⾯分别对⼏种常⽤的算法进⾏描述。1：KMP算法KMP算法，即Knuth-Morris-Pratt算法，是⼀种典型的基于前缀的搜索的字符串匹配算法。Kmp算法的搜索思路应该算是⽐较简单的：模式和⽂件进⾏前缀匹配，⼀旦发现不匹配的现象，则通过⼀个精⼼构造的数组索引模式向前滑动的距离。这个算法相对于常规的逐个字符匹配的⽅法的优越之处在于，它可以通过数组索引，减少匹配的次数，从⽽提⾼运⾏效率。详细算法介绍参考：KMP算法详解（matrix67原创）2：Horspool算法和KMP算法相反，Horspool算法采⽤的是后缀搜索⽅法。Horspool算法可以说是BM算法的意见简化版本。在进⾏后缀匹配的时候，若发现不匹配字符，则需要将模式向右移动。假设⽂本中对齐模式最后⼀个字符的元素是字符C，则Horspool算法根据C的不同情况来确定移动的距离。实际上，Horspool算法也就是通过最⼤安全移动距离来减少匹配的次数，从⽽提⾼运⾏效率的。算法参考：《算法设计与分析基础》 第⼆版 清华⼤学出版社3：BM算法BM算法采⽤的是后缀搜索（Boyer-Moore算法）。BM算法预先计算出三个函数值d1、d2、d3，它们分别对应三种不同的情形。当进⾏后缀匹配的时候，如果模式最右边的字符和⽂本中相应的字符⽐较失败，则算法和Horspool的操作完全⼀致。当遇到不匹配的字符并⾮模式最后字符时，则算法有所不同。算法参考：《算法设计与分析基础》 第⼆版 清华⼤学出版社4：Shift-And算法这种算法⽐KMP简单，不过它的特点在于运⽤了位并⾏技术，提⾼程序运⾏效率。Shift-And算法⾸先构造⼀个表，记录字母表中每个字符的位掩码。然后每读取⼀个⽂本字符的时候，通过计算公式的运算，获取新的位向量。⼆近似字符串匹配近似字符串匹配主要有四种⽅法。第⼀种是动态规划⽅法，这是最古⽼，同时也是最灵活的近似匹配算法。第⼆种是基于⾃动机公式模拟⽂本搜索。第三种⽅式采⽤位并⾏⽅法来模拟其他⽅法，号称是“最成功”的⼀种⽅法。最后则是通过简单的过滤⽂本中不相关⽂本时间快速搜索。1：动态规划算法动态规划算法是基于“编辑距离”的概念实现近似字符串匹配。通俗地说，编辑距离表⽰将⼀个字符串变换成另⼀个字符串所需要进⾏的最少的编辑次数。这⾥的编辑操作包括添加、删除、替换。通过计算编辑距离矩阵，可以得出最佳匹配。编辑矩阵的初始化和计算是动态规划算法的关键。初始化数值直接决定是全局匹配还是局部匹配，⽽在计算公式中所采⽤的增量，则表⽰了各种操作的权值。上⾯公式中，这三种编辑操作的权值都为1，但是实际上可以修改权值以限制各种编辑操作出现的频率。例如，在PI项⽬中，就采⽤了不同的权值进⾏计算。详细描述参考”Network Protocol Analysis using Bioinformatics Algorithms”。算法描述中提到，为了减少空间复杂度，没有必要保存整个编辑矩阵。但是，貌似如果不保存整个编辑矩阵的话，就很难通过回溯的⽅法找到最优匹配。2：基于⾃动机的算法关于基于⾃动机的⽅法，相关资料⽐较少，⽽中⽂资料则更少。在《柔性字符串匹配》⼀书中稍微提到的这种⽅法，但是并没有深⼊讲解其中的原理和实现步骤。上⾯这个状态转换图让⼈感觉莫名其妙，不知道这个⾃动机是如何转换的。实际上，这是通过公式计算出来的。详细介绍请参考：Faster Approximate String Matching3：位并⾏算法实际上，与其说位并⾏算法是⼀种近似搜索⽅法，倒不如说它是⼀种加速实现的⼿段。位并⾏算法是⽤来模拟经典算法的。在搜索中，通过并⾏模拟，可以加快经典算法的运⾏速度。位并⾏算法⾮常适合模式串⽐较短的情况。位并⾏实际上利⽤了计算机的并⾏性原理，将若⼲不同的值打包到⼀个长度为w的计算机字中，这样就可以利⽤⼀次操作或运算来实现原本需要若⼲次操作或运算才能完成的功能。参考：《⽤位并⾏法进⾏过滤的中⽂近似串匹配算法》4：⽂本快速过滤算法过 滤算法是基于这种思想：判断⽂中某个位置的字串和模式串不匹配，可能⽐判断⽽这相匹配更容易。所以过滤算法的思路为：通过过滤算法过滤⽂本中不能产⽣成功 匹配的区域，然后结合⾮过滤⽂本搜索算法，最终实现快速字符串匹配。当错误⽔平⽐较低时，⽂本过滤算法的运⾏效果很好，否则就很差。过滤算法⽐较多，当字母表不是太⼩的时候，PEX⽅法运⾏效果最好。当字母表很⼩的时候，ABNDM算法⽐较好。5 总结以 上讨论了四种近似字符串匹配⽅法的主要思路。实际上，我们可以看到，字符串匹配⽅法的关键计算编辑距离。动态规划直接计算编辑距离矩阵，⽽⾃动机⽅法则以 另⼀种⽅式表⽰了⽂本输⼊后的编辑距离向量。位并⾏算法主要是利⽤计算机的并⾏性，模拟经典近似匹配算法，加快运算速度。⽂本过滤算法则通过过滤不可能成 功匹配的⽂本，然后结合经典近似匹配算法实现快速字符串匹配。