21

Longest Common Prefix（LCP）を使用して、文字列内のパターンの出現回数を見つけることができることを読みました。

具体的には、テキストの接尾辞配列を作成して並べ替えるだけで、バイナリ検索を実行して範囲を見つけて出現回数を把握する代わりに、連続する各エントリのLCPを計算するだけです。接尾辞配列。

バイナリ検索を使用してパターンの出現数を見つけることは明らかですが、LCPがここで出現数を見つけるのにどのように役立つかを理解することはできません。

たとえば、この接尾辞配列の場合banana：

LCP  Suffix entry
N/A  a  
1    ana  
3    anana  
0    banana  
0    na  
2    nana

LCPは、「banana」や「na」などの部分文字列の出現回数を見つけるのにどのように役立ちますか。

LCPがここでどのように役立つかを理解するのに何か助けはありますか？

4

2 に答える 2

33

バイナリ検索を実行する代わりにLCP 配列を使用する方法はわかりませんが、あなたが言及しているのは、Udi Manber と Gene Myers がSuffix arrays: a new method for online string search で説明した手法だと思います。

(注: 以下の説明は、2014 年 4 月 9 日にウィキペディアの記事にコピーされたものです。差分を参照してください。こことウィキペディアの改訂履歴を見ると、ここのものが最初に書かれたことがわかります。挿入しないでください。 「ウィキペディアから取得」などのコメントを私の回答に含めてください。)

アイデアは次のとおりです: テキスト T (長さ N) 内の特定の文字列 P (長さ m) の出現回数を見つけるには、

  • T の接尾辞配列に対して二分探索を使用します(あなたが提案したように)
  • ただし、LCP 配列を補助データ構造として使用して高速化します。より具体的には、特別なバージョンの LCP 配列 (以下では LCP-LR と呼びます) を生成し、それを使用します。

標準のバイナリ検索 ( LCP 情報なし) を使用する際の問題は、必要なO(log N) の比較のそれぞれで、 P をサフィックス配列の現在のエントリと比較することです。これは、 upの完全な文字列比較を意味します。 m 文字まで。したがって、複雑さは O(m*log N) です。

LCP-LR 配列は、次の方法でこれを O(m+log N) に改善するのに役立ちます。

  • 二分探索アルゴリズム中の任意の時点で、通常どおり、接尾辞配列の範囲 (L,...,R) とその中心点 M を考慮し、左側の部分範囲 ( L,...,M) または右側のサブ範囲 (M,...,R)。
  • 決定を下すには、P を M の文字列と比較します。P が M と同一である場合は完了ですが、そうでない場合は、P の最初の k 文字を比較してから、P が辞書編集的に小さいかどうかを決定します。 M よりも大きい。結果として、P が M よりも大きいと仮定しましょう。

  • したがって、次のステップでは、(M,...,R) と中央の新しい中心点 M' を検討します。

                  M ...... M' ...... R
              |
       we know:
          lcp(P,M)==k

    ここでのトリックは、O(1) ルックアップが M と M' の最長の共通プレフィックス lcp(M,M') を教えてくれるように、LCP-LR が事前に計算されることです。

    M 自体が P と共通の k 文字のプレフィックスを持っていることは既に (前のステップから) わかっています: lcp(P,M)=k. 次の 3 つの可能性があります。

    • ケース 1: k < lcp(M,M')、つまり、P がM と共通する接頭文字は、M が M' と共通するよりも少ない。これは、M' の (k+1) 番目の文字が M の文字と同じであることを意味し、P は辞書的に M よりも大きいため、辞書的にも M' よりも大きくなければなりません。右半分 (M',...,R) に進みます。
    • ケース 2: k > lcp(M,M')、つまり、M が M'と共通するよりも、P が M と共通する接頭文字の方が多い。したがって、P と M' を比較すると、共通の接頭辞は k よりも小さくなり、M' は辞書式に P よりも大きくなるため、実際に比較を行うことなく、左半分 (M,.. .,M')。
    • ケース 3: k == lcp(M,M')。したがって、M と M' はどちらも最初の k 文字で P と同じです。左半分と右半分のどちらに進むかを決定するには、(k+1) 番目の文字から始まるP と M' を比較するだけで十分です。

  • 再帰的に続けます。

全体的な効果として、P の文字はテキストのどの文字とも 2 回以上比較されません。文字比較の総数は m で制限されるため、全体の複雑さは実際に O(m+log N) になります。

明らかに、残りの重要な問題は、接尾辞配列の任意の 2 つのエントリ間の lcp を O(1) 時間で伝えることができるように、LCP-LR をどのように事前計算したかということです。あなたが言ったように、標準の LCP 配列は、連続するエントリの lcpのみを示します。つまり、任意の x に対して lcp(x-1,x) を示します。しかし、上記の説明の M と M' は必ずしも連続するエントリではありません。

これの鍵は、バイナリ検索中に特定の範囲 (L,...,R) のみが発生することを認識することです。常に (0,...,N) で始まり、それを中央で分割し、次に左または右に続き、その半分をもう一度分割します。考えてみると、接尾辞配列のすべてのエントリは、バイナリ検索中に正確に 1 つの可能な範囲の中心点として発生します。したがって、二分探索中に役割を果たす可能性がある正確に N 個の異なる範囲 (L...M...R) があり、これらの N 個の可能性について lcp(L,M) と lcp(M,R) を事前計算するだけで十分です。範囲。これは 2*N の個別の事前計算された値であるため、LCP-LR のサイズは O(N) です。

さらに、標準の LCP 配列から O(N) 時間で LCP-LR の 2*N 値を計算する単純な再帰アルゴリズムがあります。詳細な説明が必要な場合は、別の質問を投稿することをお勧めします。

総括する：

  • LCP から O(N) 時間および O(2*N)=O(N) 空間で LCP-LR を計算することが可能です。
  • バイナリ検索中に LCP-LR を使用すると、検索手順が O(M*log N) から O(M+log N) に加速されます。
  • あなたが提案したように、2 つのバイナリ検索を使用して、P の一致範囲の左端と右端を決定できます。一致範囲の長さは、P の出現回数に対応します。
于 2012-07-07T11:48:33.173 に答える