原始Boyer-Moore和Boyer-Moore-Horspool算法之间的区别 [英] Difference between original Boyer–Moore and Boyer–Moore–Horspool Algorithm

问题描述

我无法理解Horspool在他的算法中所做的更改。如果您有Boyer–Moore–Horspool算法的任何链接，请告诉我。

I am not able to understand the changes which Horspool made in his algorithm. If you have any link of Boyer–Moore–Horspool algorithm then please do tell me.

推荐答案

以下是我的一些观察结果：

Here are my few observations:

BM：

Preprocessing complexity: Θ(m + σ)

Worst Case : Θ(nm) If pattern exists Θ(n+m) If pattern doesn't exist" 
Best Case : Θ(n/m) 
Space: Θ(σ) 
Comparisions: Θ(3n)

Preprocessing: Uses Good Suffix and Bad Character Shift.
At every step, it slides the pattern by the max of the slides suggested by 
the two heuristics. So it uses best of the two heuristics at every step.

Boyer Moore algorithm uses the "bad" text character itself to determine the 
shift distance.

Probably the fastest non-indexed text-search algorithm known.  
Works better in natural text and larger text searches.

A little difficult to implement.

Mostly used.

BMH：

Preprocessing complexity : Θ(m + σ)

Worst Case : Θ(nm)
Best Case : Θ(n)
Space : Θ(σ)
Comparisons : Θ(1/σ) to Θ(2/σ+1)

Preprocessing:

Recommends to Use only Bad Character Shift.
uses the rightmost character of the current text window to determine the 
shift distance.

Efficient for small alphabets

Easy to implement.

这篇关于原始Boyer-Moore和Boyer-Moore-Horspool算法之间的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！