21

Bitapアルゴリズムについて理解しようとしていますが、アルゴリズムのステップの背後にある理由を理解するのに苦労しています。

アルゴリズムの基本的な前提を理解しています (間違っている場合は修正してください)。

Two strings:     PATTERN (the desired string)
                 TEXT (the String to be perused for the presence of PATTERN)

Two indices:     i (currently processing index in PATTERN), 1 <= i < PATTERN.SIZE
                 j (arbitrary index in TEXT)

Match state S(x): S(PATTERN(i)) = S(PATTERN(i-1)) && PATTERN[i] == TEXT[j], S(0) = 1

英語ではPATTERN.substring(0,i) 、前の部分文字列PATTERN.substring(0, i-1)が正常に一致し、文字 atPATTERN[i]が文字 at と同じである場合、 は TEXT の部分文字列と一致しTEXT[j]ます。

私が理解していないのは、これのビットシフトの実装です。このアルゴリズムの詳細を説明している公式の論文は基本的にそれを説明していますが、何が起こっているのかを視覚化できないようです。 アルゴリズムの仕様は論文の最初の 2 ページのみですが、重要な部分を強調します。

概念のビットシフト バージョンは次のとおりです。

ここに画像の説明を入力

サンプル検索文字列の T[text] は次のとおりです。

ここに画像の説明を入力

そして、これがアルゴリズムのトレースです。

ここに画像の説明を入力

OR具体的には、T テーブルが何を意味するのか、現在の状態でエントリを作成する理由がわかりません。

誰かが正確に何が起こっているのかを理解するのを手伝ってくれたらありがたいです

4

2 に答える 2

16

T通常、パターン内の位置に左から右に番号を付けるため、少し混乱します。

0 1 2 3 4
a b a b c

...一方、ビットは通常、右から左に番号が付けられます。

しかし、パターンをビットの上に逆向きに書くと、次のことが明確になります。

  ビット: 4 3 2 1 0

       cb a b a 
T[a] = 1 1 0 1 0

       c b a b a
T[b] = 1 0 1 0 1

       c馬場
T[c] = 0 1 1 1 1

       ばば
T[d] = 1 1 1 1 1

ビットnは、位置nT[x]に表示される0場合、または表示されない場合です。x1

同様に、これは、入力文字列の現在の文字が で、 のn番目の位置にxa が表示されている場合、一致がn文字前に開始された場合にのみパターンに一致する可能性があることを示していると考えることができます。0T[x]

ではマッチングの手順へ。0状態のビットnのAは、 n文字前にパターンの照合を開始したことを意味します(0 は現在の文字です)。最初は、何も一致しません。

  [start]
1 1 1 1 1

一致しようとしている文字を消費すると、状態が左にシフトされ (ゼロが最下位ビットのビット 0 にシフトされます)、現在の文字のテーブル エントリと OR 演算されます。最初の文字はa; 左にシフトして OR-ing すると、次のようになりT[a]ます。

        a
1 1 1 1 0

現在の文字がパターンの一致を開始できるため、シフトされた0ビットは保持されます。a他の文字の場合、ビットは に設定されてい 1ます。

状態のビット 0 が現在 であるという事実は0、現在の文字でパターンの照合を開始したことを意味します。続けると、次のようになります。

      a b
1 1 1 0 1

...0ビットが左にシフトされているため - 1 文字前にパターンのマッチングを開始したと考えてください - 同じ位置に a があり、T[b]マッチングを開始した場合に現在の位置に a が表示されるのは良いことを示しています1文字前。0b

    a b d
1 1 1 1 1

dどこにも一致しません。すべてのビットが に戻され1ます。

  a b d a
1 1 1 1 0

従来通り。

a b d a b
1 1 1 0 1

従来通り。

b d a b a
1 1 0 1 0

aマッチが 2 文字前または現在の文字で開始された場合は良好です。

d a b a b
1 0 1 0 1

bマッチが 1 文字または 3 文字前に開始された場合は良好です。ビット 3は0、パターン全体がほぼ一致したことを意味します...

a b a b a
1 1 0 1 0

...しかし、次の文字は ですa。これは、4 文字前に試合が開始された場合は良くありません。ただし、より短い一致はまだ良い場合があります。

b a b a b
1 0 1 0 1

まだまだ元気そうです。

a b a b c
0 1 1 1 1

最後に、試合が 4 文字前に開始されていれば問題ありませんc 。a が一番上のビットまで到達したという事実0は、一致したことを意味します。

于 2012-07-04T00:25:24.783 に答える
1

他の誰にも答えられなくて申し訳ありませんが、私は今それを理解したと確信しています.

アルゴリズムを理解するために不可欠な概念は、一致状態 (元の投稿で定義) をバイナリで表現することです。元の投稿の記事で正式に説明されています。私は口語的にそうすることに手を出します：

これはSTR、特定のアルファベットの文字で作成された文字列です。

STRを一連の 2 進数で表してみましょう: STR_BINARY. アルゴリズムでは、この表現を逆にする必要があります (したがって、最初の文字は最後の数字に対応し、2 番目の文字は最後から 2 番目の数字に対応するなど)。

同じアルファベットから作成されRANDOMたランダムな文字を含む文字列を参照すると仮定しましょう。STR

STR_BINARYで、特定のインデックスの 0 は、 ～ に一致するRANDOMことSTRを示します。STR[0]

STR[(index of letter in STR that the 0 in STR_BINARY corresponds to)]. 空白は一致としてカウントされます。1 は、同じ境界内でRANDOM一致しないことを示します。STR

これを理解すると、アルゴリズムの学習が容易になります。

于 2012-07-04T00:17:40.100 に答える