文字列のセットから最も長い共通のサブ文字列を見つけるためのPythonライブラリを探しています。この問題を解決するには、次の2つの方法があります。
- 接尾辞木を使用する
- 動的計画法を使用します。
実装された方法は重要ではありません。(2つの文字列だけでなく)文字列のセットに使用できることが重要です。
文字列のセットから最も長い共通のサブ文字列を見つけるための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セバスティアンによって示されているように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
お役に立てれば、
ジェイソン。
これはもっと短くすることができます:
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)setデータ型をトライとして実装し、(2)接尾辞をトライに格納してから、各ノードをエンドポイントにする場合(これは、すべてのサブストリングを追加するのと同じです)、理論的には推測しますこの赤ちゃんは、特に試行の交差が非常に簡単であるため、かなりメモリ効率が良いです。
それにもかかわらず、これは短く、時期尚早の最適化がかなりの時間の浪費の根源です。
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
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
# 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
正直言って、私は満足していません。
誰かが任意のオブジェクトのシーケンスのリストを取得できる一般化されたバージョンを探している場合:
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!'])
私の答えは、かなり遅いですが、非常に理解しやすいです。1 kbの文字列が100個あるファイルでの作業には、それぞれ約2秒かかります。複数ある場合は、最長の部分文字列を1つ返します。
ls = list()
ls.sort(key=len)
s1 = ls.pop(0)
maxl = len(s1)
#1長さで逆方向にソートされたすべてのサブストリングのリストを作成します。したがって、リスト全体を確認する必要はありません。
subs = [s1[i:j] for i in range(maxl) for j in range(maxl,i,-1)]
subs.sort(key=len, reverse=True)
#2次に短い文字列、次に次の短い文字列などをチェックします。次の短い文字列にない場合は、サイクルを中断します。これは一般的ではありません。すべてのチェックに合格した場合、デフォルトで最長のチェックであり、サイクルを中断します。
def isasub(subs, ls):
for sub in subs:
for st in ls:
if sub not in st:
break
else:
return sub
break
print('the longest common substring is: ',isasub(subs,ls))
リストとして渡す部分文字列の長さに基づいて、文字列の中で最も頻度の高い部分文字列を含むデータフレームを提供するCavemanソリューション:
import pandas as pd
lista = ['How much wood would a woodchuck',' chuck if a woodchuck could chuck wood?']
string = ''
for i in lista:
string = string + ' ' + str(i)
string = string.lower()
characters_you_would_like_to_remove_from_string = [' ','-','_']
for i in charecters_you_would_like_to_remove_from_string:
string = string.replace(i,'')
substring_length_you_want_to_check = [3,4,5,6,7,8]
results_list = []
for string_length in substring_length_you_want_to_check:
for i in range(len(string)):
checking_str = string[i:i+string_length]
if len(checking_str) == string_length:
number_of_times_appears = (len(string) - len(string.replace(checking_str,'')))/string_length
results_list = results_list+[[checking_str,number_of_times_appears]]
df = pd.DataFrame(data=results_list,columns=['string','freq'])
df['freq'] = df['freq'].astype('int64')
df = df.drop_duplicates()
df = df.sort_values(by='freq',ascending=False)
display(df[:10])
結果は次のとおりです。
string freq
78 huck 4
63 wood 4
77 chuc 4
132 chuck 4
8 ood 4
7 woo 4
21 chu 4
23 uck 4
22 huc 4
20 dch 3
単一の「ブレーク」を追加すると、私のマシンでjtjacquesの回答が大幅に高速化されます(16Kファイルの場合は1000倍程度)。
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(substr)+1, len(data[0])-i+1):
if all(data[0][i:i+j] in x for x in data[1:]):
substr = data[0][i:i+j]
else:
break
return substr
一般化されたサフィックスツリーのANSIC実装に基づくラッパーであるSuffixTreeモジュールを使用できます。モジュールは扱いやすいです...。
見てください:ここ