複数の文字列の中で最も長い共通部分文字列を見つけるにはどうすればよいですか？

Question

私は複数の文字列を持つpythonスクリプトを書いています。例えば

：

x = "brownasdfoersjumps" 
y = "foxsxzxasis12sa[[#brown" 
z = "thissasbrownxc-34a@s;" 

すべてのこれらの3つの文字列で、彼らはbrownで共通して一つのサブ文字列を持っています。辞書を作成する方法で検索したいのですが、

dict = {[commonly occuring substring] => 
      [total number of occurrences in the strings provided]} 

これを行うにはどうすればよいでしょうか？私は毎回200以上の文字列を持つことを考慮して、それを行うのは簡単で効率的な方法は何でしょうか？

Answer 1

これは比較的最適化されたナイーブなアルゴリズムです。最初に、各シーケンスをすべてのnグラムのセットに変換します。次に、すべてのセットを交差させ、交差点で最も長いngramを見つけます。

from functools import partial, reduce 
from itertools import chain 
from typing import Iterator 


def ngram(seq: str, n: int) -> Iterator[str]: 
    return (seq[i: i+n] for i in range(0, len(seq)-n+1)) 


def allngram(seq: str) -> Iterator[str]: 
    lengths = range(len(seq)) 
    ngrams = map(partial(ngram, seq), lengths) 
    return set(chain.from_iterable(ngrams)) 


sequences = ["brownasdfoersjumps", 
      "foxsxzxasis12sa[[#brown", 
      "thissasbrownxc-34a@s;"] 

seqs_ngrams = map(allngram, sequences) 
intersection = reduce(set.intersection, seqs_ngrams) 
longest = max(intersection, key=len) # -> brown 

この方法では短いシーケンスが得られるかもしれませんが、このアルゴリズムは長いシーケンスでは非常に非効率的です。シーケンスが長い場合は、ヒューリスティックを追加して、可能な限り最大のngram長（つまり、可能な限り長い共通部分文字列）を制限することができます。そのようなヒューリスティックの1つの明白な値は、最短シーケンスの長さであってもよい。

def allngram(seq: str, minn=1, maxn=None) -> Iterator[str]: 
    lengths = range(minn, maxn) if maxn else range(minn, len(seq)) 
    ngrams = map(partial(ngram, seq), lengths) 
    return set(chain.from_iterable(ngrams)) 


sequences = ["brownasdfoersjumps", 
      "foxsxzxasis12sa[[#brown", 
      "thissasbrownxc-34a@s;"] 

maxn = min(map(len, sequences)) 
seqs_ngrams = map(partial(allngram, maxn=maxn), sequences) 
intersection = reduce(set.intersection, seqs_ngrams) 
longest = max(intersection, key=len) # -> brown 

あなたには、いくつかの最適なアルゴリズムを（私はあなたの質問に私のコメントで左のリンクを参照）について読みたいと思うかもしれませんので、これはまだ、あまりにも長い間を取る（またはあなたのマシンがRAMを使い果たす作る）ことがあります。

更新

各nグラムが

from collections import Counter 
sequences = ["brownasdfoersjumps", 
      "foxsxzxasis12sa[[#brown", 
      "thissasbrownxc-34a@s;"] 

seqs_ngrams = map(allngram, sequences) 
counts = Counter(chain.from_iterable(seqs_ngrams)) 

Counterを発生し、前記文字列の数をカウントするには、そのインスタンスは、同様のインタフェースを持っているので、dictのサブクラスである：

print(counts) 
Counter({'#': 1, 
     '#b': 1, 
     '#br': 1, 
     '#bro': 1, 
     '#brow': 1, 
     '#brown': 1, 
     '-': 1, 
     '-3': 1, 
     '-34': 1, 
     '-34a': 1, 
     '-34a@': 1, 
     '-34a@s': 1, 
     '-34a@s;': 1, 
     ... 

あなたはカウントをフィルタリングして、少なくとも部分文字列を残すことができますn文字列：{string: count for string, count in counts.items() if count >= n}