17

Rabin-Karp 文字列マッチング アルゴリズムに関するウィキペディアのエントリによると、線形の複雑さを維持しながら、文字列内の複数の異なるパターンを同時に検索するために使用できます。すべてのパターンが同じ長さの場合、これが簡単に実行できることは明らかですが、長さが異なるパターンを同時に検索するときに O(n) の複雑さを維持する方法はまだわかりません。誰かがこれに光を当てることができますか？

編集（2011年12月）：

ウィキペディアの記事はその後更新され、O(n) で異なる長さの複数のパターンに一致すると主張しなくなりました。

4

2 に答える 2

5

これが正しい答えかどうかはわかりませんが、とにかく: ハッシュ値

を構築する際に、文字列ハッシュのセットで一致を確認できます。別名、現在のハッシュ値。ハッシュ関数/コードは通常、ループとして実装され、そのループ内にクイック ルックアップを挿入できます。

もちろん、m文字列のセットから最大の文字列長を選択する必要があります。

更新:ウィキペディアから、

[...]
for i from 1 to n-m+1
         if hs ∈ hsubs
             if s[i..i+m-1] = a substring with hash hs
                 return i
         hs := hash(s[i+1..i+m]) // <---- calculating current hash
[...]

現在のハッシュを段階的に計算しmます。各ステップには、ハッシュのセットで検索できる一時的なハッシュ値 (O(1) 複雑さ) があります。すべてのハッシュは同じサイズ、つまり 32 ビットになります。

更新 2:償却された (平均) O(n) 時間の複雑さ ?

上記でm、最大文字列長が必要であると述べました。反対のことを利用できることがわかりました。部分文字列検索をシフトするためのハッシュと固定サイズ
により、O(n) の複雑さを実現できます。 可変長の文字列がある場合は、最小文字列長に設定できます。さらに、ハッシュのセットでは、ハッシュを文字列全体ではなく、文字列の最初の m 文字に関連付けます。 ここで、テキストを検索しながら、現在のハッシュがハッシュ セットに含まれているかどうかを確認し、関連する文字列が一致するかどうかを調べます。 この手法は誤報を増やしますが、平均して O(n) 時間の複雑さがあります。m

m


于 2009-08-23T09:40:51.960 に答える
0

これは、部分文字列のハッシュ値が数学的に関連付けられているためです。ハッシュH(S,j) (文字列Sの j 番目の位置から始まる文字のハッシュ)の計算には、長さmの文字列でO(m)時間がかかります。しかし、それがあれば、H(S, j+1) は H(S, j) の関数として表現できるため、H(S, j+1) の計算は一定時間で実行できます。

O(m) + O(1) => O(m)、つまり線形時間。

これがより詳細に説明されているリンクは次のとおりです (たとえば、「Rabin-Karp が高速になる理由」のセクションを参照してください)。

于 2009-08-23T10:14:58.337 に答える