字符串近似匹配
在计算机科学中, 字符串近似匹配(通常俗称为字符串模糊查询),是一种字符串查找技术,用来近似匹配一个模式,而不是完全匹配。
概览
匹配的近似度用如下方法来度量:把字符串转换成完全匹配的字符串所需要的基本操作步数。这个数量被称为编辑距离。通常基本操作有:
- 插入: cot → coat
- 删除: coat → cot
- 替换: coat → cost
这三个操作可以泛化为使用NULL字符来替换原来的字符(这里使用*来表示):
- 插入: co*t → coat
- 删除: coat → co*t
- 替换: coat → cost
某些近似匹配算法还将转置(字符串中的2个字母交换位置)作为一次基本操作来对待。 一个例子是cost → cots。
问题表述和算法
一个可能的字符串近似匹配问题定义如下:给定模式 和字符串 ,查找 的一个子字符串 ,使得在所有的子字符串中,这个子字符串和 的编辑距离最小。
一种暴力的算法是,计算T的所有子字符串和P的编辑距离,然后选择距离最小的那个。 然而,这个算法的运行时间为 O(n3 m)。
一个更好的解决办法,是由Sellers提出的动态规划方法。
在线和离线
传统上,字符串近似匹配算法被分为两类:在线和离线。
在线算法模式可以被预处理,但是文本没有预处理。换言之,在线技术搜索不需要索引。早期的在线算法是由Wagner和Fisher、Sellers提出的。Sellers算法用来近似搜索文本的子字符串。而Wagner-Fisher算法计算莱文斯坦距离, 只能适合作字典模糊查询。
在线搜索技术已经被持续改善。 也许最著名改善是Bitap算法(又称shift-or算法、shift-and算法),对于较短的模式搜索效率非常高。Bitap算法是Unix操作系统中agrep工具的核心算法。G.Navarro对在线搜索算法做了一个回顾。
在线算法对于大量数据是不可接受的。 文本预处理、索引使得搜索大幅度加速。 如今,有各种各样的索引算法,如后缀树,度量树和n元语法。
应用
最常见的应用如拼写检查,在大量的DNA数据中匹配核苷酸,还有垃圾邮件过滤。
字符串近似匹配不能应用于大多数二进制数据如图像和声音,它们需要不同的算法,例如声学指纹。
链接
- Flamingo工程
(页面存档备份,存于互联网档案馆) - Efficient Similarity Query Processing Project
- StringMetric (页面存档备份,存于互联网档案馆) Scala工程,字符串度量和语音学算法。
- Natural(页面存档备份,存于互联网档案馆) JavaScript工程,自然语言处理库
参考文献
- ^ Cormen, Thomas; Leiserson, Rivest. Introduction to Algorithms 2nd. MIT Press. 2001: 364–7. ISBN 0-262-03293-7.
- A guided tour to approximate string matching. ACM Computing Surveys. 2001, 33 (1): 31–88. doi:10.1145/375360.375365. CiteSeerX: 10.1.1.96.7225 . Navarro, Gonzalo.