2

外国語のリストがあるとしましょう:

  1. イリクワ
  2. アリクワ
  3. ニリフンディシャ
  4. アナフンディシャ
  5. ツナソマ
  6. ツリソマ

この単語のリスト内で、単語に共通する長さ 4 以上の部分文字列を特定したいと考えています。たとえば、「kuwa」、「fundisha」、および「soma」という単語はすべてこのカテゴリに分類されます。

次に、周波数分析を行うと、次のようになります。

cnt = Counter()
for lines in list:
    cnt[words]
print cnt.most_common(2000)

これらの部分文字列がリスト全体に表示される回数をカウントするようにしたい...次の最終出力が次のようになるように: print cnt.most_common(3) は次のようになります。

  1. くわ - 2
  2. フンディシャ - 2
  3. 相馬-2
  4. イリクワ 1 ...etc

ただし、これを行う方法については完全に途方に暮れています。何か案は？

4

2 に答える 2

4

すでに を使用しているCounterため、不足しているのは、特定の文字列の部分文字列を生成する方法だけです。そのビットが、文字列と部分文字列の最小長を取る関数のどこかにある場合、カウント ロジックは次の助けを借りてワンライナーにすることができますitertools.chain。

cnt = Counter(chain.from_iterable(substrings(line, 4) for line in lines))
cnt.most_common(2000)

これらの部分文字列を生成する方法を考え出すという問題が残ります。これを行う最も簡単な方法は、部分文字列の可能なサイズをループしてから、文字列をループして、文字列内の連続する各位置から開始し、指定された長さを持つスライスを返すことです (ただし、Python のスライスはと終了インデックス、それを機能させるためにいくつかのスライス演算を行う必要があります):

def substrings(s, min_length=1):
   for length in range(min_length, len(s)+1):
     for start in range(len(s) - min_length + 1):
        yield s[start:start+length]
于 2012-08-06T06:26:52.003 に答える
1

効率が重要な場合は、 Suffix Arrayが必要になると思います。

wiki に示されているように、接尾辞配列を使用すると、O(m+logN) 内の任意の部分文字列の出現回数をカウントできます。ここで、m は部分文字列の長さであり、N はすべての単語の合計の長さです。

それでも、各単語のすべての部分文字列を列挙する必要があります。最悪の場合、O(N*N) 列挙は避けられないと思います。ただし、重複した部分文字列の複数のチェックを回避するために dict() を使用すると、平均的なケースでパフォーマンスが確実に向上します。

于 2012-08-06T05:52:58.277 に答える