Jan Fan     About     Archive     Feed     English Blog

字符串匹配算法统一论

String searching algorithms, sometimes called string matching algorithms.

字符串匹配算法(String Searching Algorithms)是在CS学科中无处不在的一类算法。

在字串匹配中,通常有两个角色,\(T\)指Text(或者叫sequence database),\(P\)指Pattern。 即从长篇文字T中搜索其中的小段文字P。 这种搜索又称 Needle in a haystack

T: AGCCTAAGCTCCTAAGTC (length: n)
P: CCTA               (length: m)

匹配结果:AGCCTAAGCT CCTAAGTC

本文并不是各种精确匹配(exact string matching)算法的入门介绍与讲解,但会附上一些优质的教程文章供读者参考学习。

本文的主要目的,是针对各种精确匹配(exact string matching)算法,用一个基础的规则——单个字符的匹配规则,对它们做一个统一的论述,并基于这个规则进行比较。

字符串匹配算法——总述

分类

按照字符是否逐一匹配可分为

按照与Text匹配的Pattern数目可分为

常见的字符串匹配算法

除了最差劲的作法——\(O(mn)\)复杂度的暴力破解法(Brute Force)之外,各种改进的算法可以分为两类:

  1. 基于对P的改进:基于对P序列的分析,建立索引,当某个字符mismatch的时候,加大P的移位跨度。
  2. 基于对T的改进:改进存储T的数据结构(最朴素的结构为线性数组,可换成后缀树等)

本文主要讨论exact matching的字符串算法,即主要是基于P建立索引。 这类改进算法包括但不限于:

  1. 基于前缀匹配的算法
    • KMP (Knuth-Morris-Pratt)
    • Shift-And/Shift-Or
  2. 基于后缀匹配的算法
    • BM (Boyer-Moore)
    • Horspool
    • Sunday(这个算法可以适应前、后缀或任意匹配,属于BM的简化算法)
  3. 基于子串匹配的算法
    • BNDM (Backward Nondeterministic Dawg Matching)(平均匹配速度最优的算法)

统一论

在讲述具体的规则之前,先介绍一个字符串匹配的基本套路——滑动窗口(sliding window)

把P和T对齐以后开始进行匹配,当前窗口不匹配时,根据一定规则将P进行滑动,再次进行匹配,直到匹配成功或滑动到T的末尾。

 T: AGCC TAAGCTCCTAAGTC (length: n)
 P:+----+               (length: m)
   |CCTA|
   +----+
   window

 T: AG CCTA AGCTCCTAAGTC (length: n)
 P:   +----+             (length: m)
      |CCTA|
      +----+
      window

基础规则——单个字符的匹配规则

Horspool算法

很特别的,我们不从KMP这个历史地位很高的算法讲起,我们从Horspool算法讲起。

Horspool算法是BM算法的简化版本,它摒弃了BM中的“好后缀规则”,却获得了比BM更优异的平均速度,至于原因我们会在后面讲述。

Horspool算法也是基于后缀匹配,Pattern从左向右滑动。

当当前窗口的字符串不匹配时,根据“T在窗口中的子串”(下文称为\(t\))的“最末尾的字符”(下文称为\(t[$]\))来制定P的滑动规则:

t[$] ∉ P:

 T: AGCC TAAGCTCCTAAGTC (length: n)
 P:+----+               (length: m)
   |AAAA|
   +----+
   window

 T: AGCC TAAG CTCCTAAGTC (length: n)
 P:    |+----+           (length: m)
       ?|AAAA|
        +----+
        window
t[$] ∈ P:

 T: AGCC TAAGCTCCTAAGTC (length: n)
 P:+----+               (length: m)
   |CCTA|
   +----+
   window

 T: AG CCTA AGCTCCTAAGTC (length: n)
 P:   +-|--+             (length: m)
      |CCTA|
      +----+
      window

这个规则就是本文最重要的基础了——单个字符的匹配规则(下文称为SCR,即Single Character Rule)。 后面我会基于这个规则来揭示其它算法的原理。

SCR在字母表(Alphabet ∑)较小时,效果很差(如DNA,只有4种碱基)。 因为坏字符很容易就能遇到匹配的字符,使P跳跃的距离大大减小。

这种情况下,下面要介绍的基于子串的匹配则有效得多(因为即使字母表较小,多个字母产生的排列组合还是很多的,使得两个排列完全相等的可能性较小)。

前后缀子串匹配规则的转化

BM算法 (Boyer-Moore)

接下来要讲的是不那么简单的BM算法。

BM算法实质是两种规则的权衡(取滑动距离最大的规则)——坏字符规则 vs. 好后缀规则

即我们可以只用一种规则来描述BM算法的全部规则,使得原理更加清晰。

当前窗口“A”与“C”不匹配
坏字符:A
好后缀:TC

 T: AGC CTAAAATC CTAAGTC (length: n)
 P:    +------||+        (length: m)
       |AATCGCTC|
       +--------+
         window


对 好后缀的“C” 使用SCR:true
对 好后缀的“T” 使用SCR:false
“与”操作:false

 T: AGC CTAAAATC CTAAGTC (length: n)
 P:      +----\|--+      (length: m)
         |AATCGCTC|
         +--------+
           window


对 好后缀的“C” 使用SCR:true
对 好后缀的“T” 使用SCR:true
“与”操作:true
当前窗口存在匹配的可能,滑动结束,重新从P的后缀开始匹配

 T: AGC CTAAAATC CTAAGTC (length: n)
 P:        +--||----+    (length: m)
           |AATCGCTC|
           +--------+
             window

KMP算法 (Knuth-Morris-Pratt)

好了,到了观众念叨已久的KMP算法了。

KMP算法没有像BM那样单独使用“坏字符规则”,而是根据其采用的前缀匹配方式,使用了“好前缀规则”——寻找“好前缀”的后缀集合与P的前缀集合的交集中,最长的公共子串,并将它们对齐。

inter_set = “好前缀”的后缀集合 ∩ “好前缀”的前缀集合
sub_str_to_align = get_longest_element(inter_set);
 T: DDDDDDDABABABCCCCCABABABCCCCCC
 P:       +|||||||||||||||||-----+
          |ABABABCCCCCABABABDDDDD|
          +----------------------+

 好前缀: ABABABCCCCCABABAB

 +----------+     +----------+
 |+------+  |     |  +------+|
 ||+--+  |  |     |  |  +--+||
 |||AB|AB|AB|CCCCC|AB|AB|AB|||
 ||+--+  |  |     |  |  +--+||
 |+------+  |     |  +------+|
 +----------+     +----------+

 T: DDDDDDDABABABCCCCCABABABCCCCCC
 P:                  +||||||----------------+
                     |ABABABCCCCCABABABDDDDD|
                     +----------------------+

同样的,我们可以用多个字符SCR的“与”操作将其一般化。

一般化的过程只是显示了KMP P的滑动过程, 而实际的实现是通过事先对P做预处理,维护P的好前缀索引数组, 匹配时定位最长公共子串只需要\(O(1)\)的复杂度,并不需要图例中的多次SCR匹配。

 T: DDDDDDDABABABCCCCCABABABCCCCCC
 P:       +|||||||||||||||||-----+
          |ABABABCCCCCABABABDDDDD|
          +----------------------+


对 T的好前缀的“B” 使用SCR:true
对 T的好前缀的“A” 使用SCR:true
…
对 T的好前缀的“B” 使用SCR:false
“与”操作:false

 T: DDDDDDDABABABCCCCCABABABCCCCCC
 P:         +----------\||||-------+
            |ABABABCCCCCABABABDDDDD|
            +----------------------+


对 T的好前缀的“B” 使用SCR:true
对 T的好前缀的“A” 使用SCR:true
对 T的好前缀的“B” 使用SCR:false
“与”操作:false

 T: DDDDDDDABABABCCCCCABABABCCCCCC
 P:           +----------\||||||-----+
              |ABABABCCCCCABABABDDDDD|
              +----------------------+


对 T的好前缀的“B” 使用SCR:true
对 T的好前缀的“A” 使用SCR:true
…
对 T的好前缀的“A” 使用SCR:true
“与”操作:true
当前窗口存在匹配的可能,滑动结束,从T的好后缀后一位开始匹配

 T: DDDDDDDABABABCCCCCABABABCCCCCC
 P:                  +||||||----------------+
                     |ABABABCCCCCABABABDDDDD|
                     +----------------------+

各种算法的比较

Z Algorithm (Dan Gusfield) 本质上和KMP是一样的,都是基于前缀匹配,基于已匹配前缀的回溯算得,只是实现的方式不同。

Shift-And/Shift-Or算法是基于“位运算”实现的KMP,它的速度一般是KMP的2倍的原因——KMP只使用了“好前缀”的信息,而Shift-And/Shift-Or算法还使用了“坏字符”,即不匹配字符的信息,省去了KMP中多余的不存在可能性的窗口的比较。

Sunday算法也是BM算法的简化,与Horspool算法如出一辙,唯一不同的地方是它挑选的SCR字符不是“好后缀”的末位,而是它的再后一位,在理想的情况下可以实现更大的跳跃距离(+1)。

Horspool与Sunday算法都抛弃了BM算法的“好后缀”规则,但反而实现了更优的平均速度(虽然也导致了更差的非线性的下限速度)。 这是因为字符串匹配的速度是非常快的,一次比较可以滑动N位;相较之下把这次比较用作“好后缀”与“坏字符”取舍,它们的差距所取得的提高可能远小于N位,那么这样做就显得划不来了。 更具体的论述可以看这里

基于子串匹配的BDM (Backward Dawg Matching)算法与Horspool类似,在处理滑动的时候也只使用了“坏字符”的信息。 但它强大的地方在于它可以匹配T的后缀与P的任意子串,而不仅限于P的后缀,这样等价于在匹配的时候已经利用了“好后缀”的信息。 可以说BDM完美地融合了两类信息,而不需要付出额外比较的代价。

T的“CTA”后缀同时匹配了P中的两个子串

 T:   AG CCTA AAATCCTAAGTC (length: n)
 P: +-|||+|||+             (length: m)
    |GCTATCTA|
    +----+---+
       window

但其P的任意子串的索引结构实现起来比较复杂,而BNDM (Backward Nondeterministic Dawg Matching)是它的简洁实现方式(位运算),虽然有机器字长的限制。

笔者的唠叨

十三月的的《打破思维断层》系列博文给了我很大的启发。

Algorithms on Strings, Trees and Sequence真是一本关于字符串算法的相当古老的书(作者你多画几张图会shi啊(╯°Д°)╯┬─┬)。 但书中有丰富的逻辑证明和数学语言表达,这也是我在学习和分析算法时(特别是证明算法的正确性)所缺乏的。

哪个算法不清楚的可以在评论里提出来,笔者会努力改进。

有不同见解的朋友欢迎指教~

近似匹配(Approximate string matching algorithms)多pattern匹配(Multiple patterns)(即基于对Text的改进)的坑……有缘再来填上吧(摊手)。

主要参考资料

Comments

多说 Disqus