字符串近似匹配

在计算机科学中， 字符串近似匹配（通常俗称为字符串模糊查询)，是一种字符串查找技术，用来近似匹配一个模式，而不是完全匹配。

概览
匹配的近似度用如下方法来度量：把字符串转换成完全匹配的字符串所需要的基本操作步数。这个数量被称为编辑距离。通常基本操作有：

这三个操作可以泛化为使用NULL字符来替换原来的字符（这里使用*来表示）：

某些近似匹配算法还将转置（字符串中的2个字母交换位置）作为一次基本操作来对待。一个例子是cost → cots。

问题表述和算法
一个可能的字符串近似匹配问题定义如下：给定模式 P = p_1p_2...p_m 和字符串 T = t_1t_2\dots t_n，查找T的一个子字符串 T_{j',j} = t_{j'}\dots t_j，使得在所有的子字符串中，这个子字符串和P的编辑距离最小。

一种暴力的算法是，计算T的所有子字符串和P的编辑距离，然后选择距离最小的那个。然而，这个算法的运行时间为 O(n3 m)。

一个更好的解决办法，是由Sellers提出的动态规划方法。

在线和离线
传统上，字符串近似匹配算法被分为两类：在线和离线。

在线算法模式可以被预处理，但是文本没有预处理。换言之，在线技术搜索不需要索引。早期的在线算法是由Wagner和Fischer、Sellers提出的。Sellers算法用来近似搜索文本的子字符串。而Wagner-Fischer算法计算莱文斯坦距离, 只能适合作字典模糊查询。

在线搜索技术已经被持续改善。也许最著名改善是（又称shift-or算法、shift-and算法)，对于较短的模式搜索效率非常高。Bitap算法是Unix操作系统中agrep工具的核心算法。G.Navarro对在线搜索算法做了一个回顾。

在线算法对于大量数据是不可接受的。
文本预处理、索引使得搜索大幅度加速。
如今，有各种各样的索引算法，如后缀树，和n元语法。

应用
最常见的应用如拼写检查，在大量的DNA数据中匹配核苷酸，还有垃圾邮件过滤。

字符串近似匹配不能应用于大多数二进制数据如图像和声音，它们需要不同的算法，例如声学指纹。

链接

]

参考文献
*
*