文字列の部分文字列を見つける

Question

大きな（50k-100k）文字列のセットmystringsがあります。 mystringsの文字列の一部は、他の文字列の正確な部分文字列である可能性があります。これらを破棄したい（部分文字列を破棄し、最長の文字列のみを残したい）。今私はO(N^2)の複雑さを持つ素朴な方法を使用しています。

unique_strings = set() 
for s in sorted(mystrings, key=len, reverse=True): 
    keep = True 
    for us in unique_strings: 
     if s in us: 
      keep = False 
      break 
    if keep: 
     unique_strings.add(s) 

このタスクを容易にし、O(N^2)操作を必要としないデータ構造またはアルゴリズムはどれですか。ライブラリは大丈夫ですが、私は純粋なPythonを保つ必要があります。

Answer 1

単純なアプローチ：

1. sort strings by length, longest first # `O(N*log_N)` 
2. foreach string: # O(N) 
    3. insert each suffix into tree structure: first letter -> root, and so on. 
     # O(L) or O(L^2) depending on string slice implementation, L: string length 
    4. if inserting the entire string (the longest suffix) creates a new 
     leaf node, keep it! 

O[N*(log_N + L)] or O[N*(log_N + L^2)] 

これは、はるかに最適から、おそらくですが、大N（文字列の数）と小さなL（平均文字列の長さ）のためにO(N^2)よりも有意に良好でなければなりません。

また、文字列の長さを降順で繰り返し、各文字列のすべての部分文字列をセットに追加し、セットに含まれていない文字列のみを保持することもできます。アルゴリズムのビッグOは（O[N*(log_N + L^2)]）上記最悪の場合と同じでなければなりませんが、実装は非常に簡単です：私はこのアプローチを思い付いた平均時間で

seen_strings, keep_strings = set(), set() 
for s in sorted(mystrings, key=len, reverse=True): 
    if s not in seen_strings: 
     keep_strings.add(s) 
     l = len(s) 
     for start in range(0, l-1): 
      for end in range(start+1, l): 
       seen_strings.add(s[start:end]) 

Answer 2

。

from Bio.trie import trie 
unique_strings = set() 
suffix_tree = trie() 
for s in sorted(mystrings, key=len, reverse=True): 
    if suffix_tree.with_prefix(contig) == []: 
     unique_strings.add(s) 
     for i in range(len(s)): 
      suffix_tree[s[i:]] = 1 

良い：≈15分 - 私が働いていたデータ・セットの>≈20秒。 悪い：biopythonが軽量でも純粋なPythonでもない（私が最初に尋ねたように）依存関係を導入しています。