Boyer-Moore字符串搜索算法

维基百科,自由的百科全书
跳转至: 导航搜索

计算机科学里,Boyer-Moore字符串搜索算法是一种非常高效的字符串搜索算法。它由Bob BoyerJ Strother Moore设计于1977年。此算法仅对搜索目标字符串(关键字)进行预处理,而非被搜索的字符串。虽然Boyer-Moore算法的执行时间同样线性依赖于被搜索字符串的大小,但是通常仅为其它算法的一小部分:它不需要对被搜索的字符串中的字符进行逐一比较,而会跳过其中某些部分。通常搜索关键字越长,算法速度越快。它的效率来自于这样的事实:对于每一次失败的匹配尝试,算法都能够使用这些信息来排除尽可能多的无法匹配的位置。

原理[编辑]

假设被检索文字列是“1234567890”,檢索文字列是“MOORE”。简单的比较需要执行十次才得到结论不匹配。

被检索文字列:1234567890
  第一次比较:M....         (M和1比较,不匹配)
  第二次比较: M....        (M和2比较,不匹配)
  第三次比较:  M....       (M和3比较,不匹配)
        ...
  第十次比较:         M....(M和0比较,不匹配)

※未参与比较的文字用【.】占位。

BM算法只需要2次比较。

被检索文字列:1234567890
  第一次比较:....E        (E和5比较,不匹配,并且5不是MOORE中任何文字)
  第二次比较:     ....E   (E和0比较,不匹配,并且0不是MOORE中任何文字)

第一次从检索文字的末尾开始,因为如果被检索文字的第5文字位置不是E,则无论前4个文字是什麽,都绝不可能匹配了。这一点比较容易理解。
那么,为什么不用E和6比较呢?

这是BM算法又一处精妙之处。在E和5进行比较的时候不仅知道他们不相等,而且还知道了5不和检索文字MOORE中的任何一个文字相等,这使得下面这些比较都可以省略掉。

被检索文字列:....5......
不需要的比较: ...R.       (E和5比较时也同时发现5不等于R,于是这个比较是不必要的)
不需要的比较:  ..O..      (E和5比较时也同时发现5不等于O,于是这个比较是不必要的)
不需要的比较:   .O...     (E和5比较时也同时发现5不等于O,于是这个比较是不必要的)
不需要的比较:    M....    (E和5比较时也同时发现5不等于M,于是这个比较是不必要的)

另见[编辑]

参考资料[编辑]


外部链接[编辑]