文字列内の重複したフレーズを見つけるためにどのようなアルゴリズムを使用できますか?

Question

任意の文字列が与えられた場合、重複するフレーズを見つける効率的な方法は何でしょうか?一定の長さ以上のフレーズが含まれる必要があると言えます。

理想的には、各フレーズの出現数が得られるはずです。

Answer 1

先ほどの人が述べたように、サフィックス ツリーはこの作業に最適なツールです。私のお気に入りの接尾辞ツリーのサイトは次のとおりです。 http://www.allisons.org/ll/AlgDS/Tree/Suffix/. 。接尾辞ツリーの気の利いた使い方をすべて 1 ページに列挙し、テストを行っています。 js 文字列をテストし、例を実行するために埋め込まれたアプリケーション。

Answer 2

理論的には

• あ サフィックス配列 これは、線形空間と時間を使用して重複する部分文字列を検出するように実装できるため、「最良の」答えです。ただし、単純な実装では実際にサフィックスをソートするのに O(n^2 log n) の時間がかかり、これを O(n) どころか O(n log n) に減らす方法も完全には明らかではありません。必要に応じて、関連する論文もご覧ください。
• あ サフィックスツリー サフィックス配列よりもわずかに多くのメモリ (それでも線形ですが) を必要とする可能性がありますが、ツリーに要素を追加するときに基数ソートのアイデアのようなものを使用できるため、迅速に構築するために実装するのが簡単です (名前からの wikipedia リンクを参照してください)詳細）。
• の KMPアルゴリズム これは、長い文字列内の特定の部分文字列を非常に迅速に検索することに特化していることにも注意してください。この特別なケースのみが必要な場合は、KMP を使用するだけでよく、最初に十分なインデックスを作成する必要はありません。

実際には

あなたは実際の自然言語の文書を分析していると思います（例：英語) という言葉を使い、実際に収集したデータを使って何かをしたいと考えています。

この場合、簡単に実行するとよいでしょう。 Nグラム n=2 または 3 など、いくつかの小さな n に対する分析。たとえば、句読点、大文字の使用、単語のステミング (running、runs Both -> 'run') を削除して、ドキュメントを単語のリストにトークン化し、意味上の一致を増やすことができます。次に、隣接する各単語のペアの、これまでの出現数に対するハッシュ マップ (C++ の hash_map、Python の辞書など) を構築するだけです。最終的には、非常に高速にコードを作成でき、実行もそれほど遅くない、非常に有用なデータが得られます。

Answer 3

接尾辞ツリー これを実装する良い方法です。その記事の下部には、さまざまな言語での実装へのリンクがあります。

Answer 4

jmah が言ったように、これには接尾辞ツリー/接尾辞配列を使用できます。

使用できるアルゴリズムの説明があります ここ (セクション 3.1 を参照)。

さらに詳しい説明は、彼らが引用している本 (Gusfield、1997) で見つけることができます。 Googleブックスで.

Answer 5

n 個のエントリ (i=1,2,3,...,n) を持つソートされた配列 A が与えられたとします。

Algo(A(i))
{
  while i<>n
  {
    temp=A[i];
    if A[i]<>A[i+1] then
    {     
      temp=A[i+1];
      i=i+1;
      Algo(A[i])
    }
    else if A[i]==A[i+1] then
      mark A[i] and A[i+1] as duplicates
  }
}

このアルゴリズムは O(n) 時間で実行されます。