33

Boyer Moore 文字列検索アルゴリズムを理解する上で問題に直面しています。

私は次の文書に従っています。リンク

ここでの delta1 と delta2 の本当の意味と、これをどのように適用して文字列検索アルゴリズムを見つけているかについて、私は自分のやり方を理解することができません。言語は少し曖昧に見えました..

誰かがこれを理解するのを手伝ってくれるなら、それは本当に役に立ちます。

または、理解しやすい他のリンクまたは利用可能なドキュメントを知っている場合は、共有してください。

前もって感謝します。

4

2 に答える 2

117

Boyer-Moore の背後にある洞察は、パターンの最後の文字から始まる文字列のパターンの検索を開始すると、不一致にヒットしたときに複数の文字を前方に検索できるということです。

私たちのパターンpが一連の文字p1, p2, ... であるとしましょう。現在pn、文字列 を検索しているため、インデックスは で整列されています。sppnis

例えば：

s = WHICH FINALLY HALTS.  AT THAT POINT...
p = AT THAT
i =       ^

BM の論文では、次のような見解が示されています。

(1) 含まれていない文字を照合しようとすると、次の文字にpジャンプできnます。

'F' は にないpため、文字を進めnます:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =        AT THAT
i =              ^

k(2) 最後の位置がの最後にある文字を照合しようとすると、次の文字pにジャンプできkます。

' の最後の位置は最後pから 4 つなので、4 文字進めます。

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =            AT THAT
i =                  ^

ここでi、成功するか不一致に達するまで、から逆方向にスキャンします。(3a)kの先頭から文字の不一致が発生pし、不一致の文字が にない場合、p(少なくとも)k文字を進めることができます。

'L' が含まれておらず、pに対して不一致が発生したp6ため、(少なくとも) 6 文字進めることができます。

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =                  AT THAT
i =                        ^

ただし、実際にはこれよりも優れたことができます。i(3b) 以前はすでにいくつかの文字 (この場合は 1) に一致していたことがわかっているためです。一致した文字が の先頭に一致しない場合、p実際にはもう少し先にジャンプできます (この余分な距離は、論文では「デルタ 2」と呼ばれます)。

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =                   AT THAT
i =                         ^

この時点で、観測 (2) が再び適用され、次のようになります。

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =                       AT THAT
i =                             ^

そしてビンゴ！終わったね。

于 2011-06-02T02:25:30.697 に答える
49

このアルゴリズムは単純な原理に基づいています。length の部分文字列を照合しようとしているとしmます。最初に index の文字を見ていきますm。その文字が文字列に含まれていない場合、必要な部分文字列は indexs の文字で開始できないことがわかります1, 2, ... , m。

その文字が文字列にある場合、文字列の最後の場所にあると想定します。次に、ジャンプして、その可能性のある開始位置から文字列を一致させようとします。この情報は私の最初の表です。

部分文字列の先頭から照合を開始すると、不一致が見つかったときに、最初からやり直すことはできません。別のポイントから始まる試合を部分的に通過する可能性があります。たとえば、正常に一致する で一致しようとしている場合anand、ananand次は ではないananことに気付きますが、一致したのは であるため、部分文字列の 3 番目の文字を一致させる試みに戻る必要があります。この「x 文字の一致後に失敗した場合、一致の y 番目の文字にいる可能性がある」という情報は、2 番目のテーブルに格納されます。adan

一致に失敗した場合、2 番目のテーブルは、一致した内容に基づいて、一致がどの程度進んでいるかを認識していることに注意してください。最初の表は、マッチできなかったキャラクターに基づいて、私がどれだけ遡った可能性があるかを示しています。これら 2 つの情報のうち、より悲観的な方を使用する必要があります。

これを念頭に置いて、アルゴリズムは次のように機能します。

start at beginning of string
start at beginning of match
while not at the end of the string:
    if match_position is 0:
        Jump ahead m characters
        Look at character, jump back based on table 1
        If match the first character:
            advance match position
        advance string position
    else if I match:
        if I reached the end of the match:
           FOUND MATCH - return
        else:
           advance string position and match position.
    else:
        pos1 = table1[ character I failed to match ]
        pos2 = table2[ how far into the match I am ]
        if pos1 < pos2:
            jump back pos1 in string
            set match position at beginning
        else:
            set match position to pos2
FAILED TO MATCH
于 2011-06-01T23:36:49.823 に答える