2つ以上の文字列からの最も長い一般的なサブストリング-Python
-
04-10-2019 - |
質問
から最も長い共通のサブストリングを見つけるためのPythonライブラリを探しています 文字列のセット. 。この問題を解決するには2つの方法があります。
- 接尾辞ツリーを使用します
- 動的プログラミングの使用。
実装された方法は重要ではありません。使用できることが重要です 文字列のセット (2つの文字列だけではありません)。
解決
これらのペアの関数は、任意の文字列の配列で最も長い一般的な文字列を見つけます。
def long_substr(data):
substr = ''
if len(data) > 1 and len(data[0]) > 0:
for i in range(len(data[0])):
for j in range(len(data[0])-i+1):
if j > len(substr) and is_substr(data[0][i:i+j], data):
substr = data[0][i:i+j]
return substr
def is_substr(find, data):
if len(data) < 1 and len(find) < 1:
return False
for i in range(len(data)):
if find not in data[i]:
return False
return True
print long_substr(['Oh, hello, my friend.',
'I prefer Jelly Belly beans.',
'When hell freezes over!'])
アルゴリズムが改善される可能性があり、Pythonにあまり曝露していないことは間違いありません。そのため、構文的にもより効率的になる可能性がありますが、仕事をするはずです。
編集: JF Sebastianによって示されているように、2番目のIS_SubSTR関数に並んでいます。使用法は同じままです。注:アルゴリズムへの変更はありません。
def long_substr(data):
substr = ''
if len(data) > 1 and len(data[0]) > 0:
for i in range(len(data[0])):
for j in range(len(data[0])-i+1):
if j > len(substr) and all(data[0][i:i+j] in x for x in data):
substr = data[0][i:i+j]
return substr
お役に立てれば、
ジェイソン。
他のヒント
私はこれを好みます is_substr
, 、私はそれがもう少し読みやすく、直感的だと思うので:
def is_substr(find, data):
"""
inputs a substring to find, returns True only
if found for each data in data list
"""
if len(find) < 1 or len(data) < 1:
return False # expected input DNE
is_found = True # and-ing to False anywhere in data will return False
for i in data:
print "Looking for substring %s in %s..." % (find, i)
is_found = is_found and find in i
return is_found
これは短くすることができます:
def long_substr(data):
substrs = lambda x: {x[i:i+j] for i in range(len(x)) for j in range(len(x) - i + 1)}
s = substrs(data[0])
for val in data[1:]:
s.intersection_update(substrs(val))
return max(s, key=len)
セットは(おそらく)ハッシュマップとして実装されているため、これは少し非効率的になります。 (1)セットデータタイプをtrieとして実装し、(2)ポストフィックスをtrieに保存してから、各ノードをエンドポイントにするだけの場合(これはすべてのサブストリングを追加するのと同等です)、理論的には推測しますこの赤ちゃんは、特にトライの交差点が非常に簡単であるため、かなり記憶に効率的です。
それにもかかわらず、これは短く、時期尚早の最適化はかなりの量の無駄な時間の根源です。
def common_prefix(strings):
""" Find the longest string that is a prefix of all the strings.
"""
if not strings:
return ''
prefix = strings[0]
for s in strings:
if len(s) < len(prefix):
prefix = prefix[:len(s)]
if not prefix:
return ''
for i in range(len(prefix)):
if prefix[i] != s[i]:
prefix = prefix[:i]
break
return prefix
から http://bitbucket.org/ned/cog/src/tip/cogapp/whiteutils.py
# this does not increase asymptotical complexity
# but can still waste more time than it saves. TODO: profile
def shortest_of(strings):
return min(strings, key=len)
def long_substr(strings):
substr = ""
if not strings:
return substr
reference = shortest_of(strings) #strings[0]
length = len(reference)
#find a suitable slice i:j
for i in xrange(length):
#only consider strings long at least len(substr) + 1
for j in xrange(i + len(substr) + 1, length + 1):
candidate = reference[i:j] # ↓ is the slice recalculated every time?
if all(candidate in text for text in strings):
substr = candidate
return substr
免責事項 これは、Jtjacquesの答えにほとんど追加されません。ただし、うまくいけば、これはもっと読みやすくなるはずです と もっと早く と それはコメントに収まらなかったので、なぜ私はこれを答えに投稿しています。私は満足していません shortest_of
, 、 実を言うと。
一般化されたサフィックスツリーのANSI C実装に基づいたラッパーである接尾辞モジュールを使用できます。モジュールは簡単に処理できます。
を見てみましょう: ここ
誰かが任意のオブジェクトのシーケンスのリストを取得できる一般化バージョンを探している場合:
def get_longest_common_subseq(data):
substr = []
if len(data) > 1 and len(data[0]) > 0:
for i in range(len(data[0])):
for j in range(len(data[0])-i+1):
if j > len(substr) and is_subseq_of_any(data[0][i:i+j], data):
substr = data[0][i:i+j]
return substr
def is_subseq_of_any(find, data):
if len(data) < 1 and len(find) < 1:
return False
for i in range(len(data)):
if not is_subseq(find, data[i]):
return False
return True
# Will also return True if possible_subseq == seq.
def is_subseq(possible_subseq, seq):
if len(possible_subseq) > len(seq):
return False
def get_length_n_slices(n):
for i in xrange(len(seq) + 1 - n):
yield seq[i:i+n]
for slyce in get_length_n_slices(len(possible_subseq)):
if slyce == possible_subseq:
return True
return False
print get_longest_common_subseq([[1, 2, 3, 4, 5], [2, 3, 4, 5, 6]])
print get_longest_common_subseq(['Oh, hello, my friend.',
'I prefer Jelly Belly beans.',
'When hell freezes over!'])