8

任意の文字列が与えられた場合、重複するフレーズを効率的に見つける方法は何ですか? フレーズが含まれるには、特定の長さよりも長くなければならないと言えます。

理想的には、各フレーズの出現回数になります。

4

5 に答える 5

7

理論的には

  • 接尾辞配列は、線形空間と時間を使用して重複する部分文字列を検出するように実装できるため、「最良の」答えです。ただし、単純な実装では、実際には接尾辞を並べ替えるのにO（n ^ 2 log n）の時間がかかります。これを、O（n）は言うまでもなく、O（n log n）に減らす方法は完全には明らかではありません。必要に応じて、関連する論文。
  • 接尾辞ツリーは、接尾辞配列よりもわずかに多くのメモリを消費する可能性がありますが（ただし、線形ですが）、ツリーに物を追加するときに基数ソートのアイデアのようなものを使用できるため、すばやく構築するための実装が簡単です（詳細については名前）。
  • KMPアルゴリズムも知っておくとよいでしょう。これは、長い文字列内の特定の部分文字列を非常にすばやく検索することに特化しています。この特殊なケースのみが必要な場合は、KMPを使用するだけで、最初にわざわざインデックスを作成する必要はありません。

実際には

あなたは実際の自然言語（英語など）の単語の文書を分析していて、収集したデータを使って実際に何かをしたいと思っていると思います。

この場合、n = 2や3などの小さなnについて、簡単なn-gram分析を実行したい場合があります。たとえば、句読点、大文字と小文字を削除して、ドキュメントを単語のリストにトークン化できます。セマンティック一致を増やすために、単語をステミング（実行中、両方を実行->'実行'）します。次に、隣接する各単語ペアのハッシュマップ（C ++のhash_map、pythonの辞書など）を、これまでの出現回数に合わせて作成します。結局、コーディングが非常に速く、実行が非常に遅くない、非常に有用なデータが得られます。

于 2008-09-18T15:38:29.467 に答える
4

以前の人々が言及したように、サフィックスツリーは仕事に最適なツールです。接尾辞ツリーに関する私のお気に入りのサイトはhttp://www.allisons.org/ll/AlgDS/Tree/Suffix/です。接尾辞ツリーの気の利いた使用法をすべて 1 ページに列挙し、js文字列をテストして例を実行するためのテスト アプリケーションが埋め込まれています。

于 2008-09-17T23:49:14.413 に答える
1

サフィックス ツリーは、これを実装するための優れた方法です。その記事の下部には、さまざまな言語での実装へのリンクがあります。

于 2008-09-17T23:23:52.993 に答える
0

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）時間で実行されます。

于 2009-02-24T01:40:49.483 に答える
0

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

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

彼らが引用した本 (Gusfield, 1997) で、より詳細な説明を見つけることができます。これはgoogle books にあります。

于 2008-09-17T23:33:24.467 に答える