26

文字列内で最も一般的なフレーズ (または部分文字列) を見つけるために使用できるアルゴリズムはありますか? たとえば、次の文字列には、最も一般的な 2 語句として「hello world」が含まれます。

"hello world this is hello world. hello world repeats three times in this string!"

上記の文字列で、最も一般的な文字列 (空の文字列文字の後、無限に繰り返される文字列) はスペース文字です。

最も一般的なものから最も一般的でないものまで、この文字列で一般的な部分文字列のリストを生成する方法はありますか?

4

5 に答える 5

15

これは Nussinov アルゴリズムに似たタスクであり、アラインメントのギャップ、挿入、または不一致を許可しないため、実際にはさらに単純です。

長さ N の文字列 A について、F[-1 .. N, -1 .. N]テーブルを定義し、次の規則を使用して入力します。

  for i = 0 to N
    for j = 0 to N
      if i != j
        {
          if A[i] == A[j]
            F[i,j] = F [i-1,j-1] + 1;
          else
            F[i,j] = 0;
        }

たとえば、BA O BA B の場合:

AlgChart

これはO(n^2)時間通りに実行されます。テーブル内の最大値は、最長の自己一致サブシーケンスの終了位置を指します (i - 1 つの発生の終了、j - 別の発生の終了)。最初は、配列はゼロで初期化されていると想定されています。最も長いが、おそらく面白くない自己一致である対角線を除外する条件を追加しました。

さらに考えてみると、この表は対角線上で対称であるため、その半分だけを計算するだけで十分です。また、配列はゼロ初期化されているため、ゼロを割り当てることは冗長です。それが残っている

  for i = 0 to N
    for j = i + 1 to N
      if A[i] == A[j]
         F[i,j] = F [i-1,j-1] + 1;

短くなりますが、理解するのが難しくなる可能性があります。計算されたテーブルには、短いものと長いもののすべての一致が含まれます。必要に応じて、さらにフィルタリングを追加できます。

次のステップでは、文字列を回復する必要があります。これは、ゼロ以外のセルから上と左の対角線に続きます。このステップでは、いくつかのハッシュマップを使用して、同じ文字列の自己類似性一致の数をカウントすることも簡単です。通常の文字列と通常の最小長では、少数のテーブル セルのみがこのマップで処理されます。

ハッシュマップを直接使用するには、実際には O(n^3) が必要だと思います。これは、アクセスの最後のキー文字列を何らかの方法で比較する必要があるためです。この比較はおそらく O(n) です。

于 2013-02-03T08:24:56.457 に答える
6

Python。これはやや迅速で汚いものであり、データ構造がほとんどのリフティングを実行します。

from collections import Counter
accumulator = Counter()
text = 'hello world this is hello world.'
for length in range(1,len(text)+1):
    for start in range(len(text) - length):
        accumulator[text[start:start+length]] += 1

Counter構造は、何かを見た回数をカウントするために設計されたハッシュベースの辞書です。存在しないキーに追加すると作成されますが、存在しないキーを取得するとエラーではなくゼロになります。したがって、あなたがしなければならないのは、すべての部分文字列を反復処理することだけです。

于 2013-02-03T08:35:55.597 に答える
2

単なる疑似コードであり、おそらくこれは最も美しいソリューションではないかもしれませんが、私は次のように解決します:

function separateWords(String incomingString) returns StringArray{
  //Code
}

function findMax(Map map) returns String{
  //Code
}

function mainAlgorithm(String incomingString) returns String{
    StringArray sArr = separateWords(incomingString);
    Map<String, Integer> map; //init with no content
    for(word: sArr){
        Integer count = map.get(word);
        if(count == null){
            map.put(word,1);
        } else {
            //remove if neccessary
            map.put(word,count++); 
        }
   }
   return findMax(map);
}

マップには、Java HashMap のようにキーと値のペアを含めることができます。

于 2013-02-04T15:44:31.523 に答える
0

Perl、O(n²)ソリューション

my $str = "hello world this is hello world. hello world repeats three times in this string!";

my @words = split(/[^a-z]+/i, $str);
my ($display,$ix,$i,%ocur) = 10;

# calculate

for ($ix=0 ; $ix<=$#words ; $ix++) {
  for ($i=$ix ; $i<=$#words ; $i++) {
    $ocur{ join(':', @words[$ix .. $i]) }++;
  }
}

# display 

foreach (sort { my $c = $ocur{$b} <=> $ocur{$a} ; return $c ? $c : split(/:/,$b)-split(/:/,$a); } keys %ocur) {
  print "$_: $ocur{$_}\n";
  last if !--$display;
}

最も一般的な部分文字列の 10 の最高スコアを表示します (同点の場合は、単語の最も長いチェーンを最初に表示します)。結果のみを表示するように変更$displayします。繰り返しがあります。1
n(n+1)/2

于 2013-02-03T12:53:23.377 に答える