65

文字列のセットから最も長い共通のサブ文字列を見つけるためのPythonライブラリを探しています。この問題を解決するには、次の2つの方法があります。

  • 接尾辞木を使用する
  • 動的計画法を使用します。

実装された方法は重要ではありません。（2つの文字列だけでなく）文字列のセットに使用できることが重要です。

4

10 に答える 10

65

これらの対関数は、任意の文字列配列から最長の共通文字列を検索します。

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

お役に立てれば、

ジェイソン。

于 2010-05-24T00:12:40.897 に答える
6

これはもっと短くすることができます：

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）接尾辞をトライに格納してから、各ノードをエンドポイントにする場合（これは、すべてのサブストリングを追加するのと同じです）、理論的には推測しますこの赤ちゃんは、特に試行の交差が非常に簡単であるため、かなりメモリ効率が良いです。

それにもかかわらず、これは短く、時期尚早の最適化がかなりの時間の浪費の根源です。

于 2015-09-16T14:29:32.563 に答える
4 
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から

于 2010-05-23T18:59:08.133 に答える
4

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
于 2013-02-18T20:12:01.963 に答える
2 
# 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正直言って、私は満足していません。

于 2010-05-24T07:51:17.620 に答える
1

誰かが任意のオブジェクトのシーケンスのリストを取得できる一般化されたバージョンを探している場合：

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!'])
于 2015-03-05T03:53:02.360 に答える
0

私の答えは、かなり遅いですが、非常に理解しやすいです。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))
于 2021-03-08T10:51:56.493 に答える
0

リストとして渡す部分文字列の長さに基づいて、文字列の中で最も頻度の高い部分文字列を含むデータフレームを提供する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
于 2021-04-03T21:05:14.703 に答える
0

単一の「ブレーク」を追加すると、私のマシンで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
于 2021-08-16T00:21:43.603 に答える
-1

一般化されたサフィックスツリーのANSIC実装に基づくラッパーであるSuffixTreeモジュールを使用できます。モジュールは扱いやすいです...。

見てください：ここ

于 2011-04-16T09:30:22.217 に答える