7 
bigString = "AGAHKGHKHASNHADKRGHFKXXX_I_AM_THERE_XXXXXMHHGRFSAHGSKHASGKHGKHSKGHAK"
smallString = "I_AM_HERE"

「smallString」と密接に一致する「bigString」の部分文字列を見つけるには、どの効率的なアルゴリズムを使用すればよいですか

output = "I_AM_THERE"

小さい文字列と比較すると、出力の挿入や削除が少ない場合があります。

編集: ここで私の問題に非常に近い良い例を見つけました: How to add variable error to regex fuzzy search. パイソン

4

3 に答える 3

7

あいまい一致を備えたほぼ準備ができている全員の正規表現パッケージを使用できます。

>>> import regex
>>> bigString = "AGAHKGHKHASNHADKRGHFKXXX_I_AM_THERE_XXXXXMHHGRFSAHGSKHASGKHGKHSKGHAK"
>>> regex.search('(?:I_AM_HERE){e<=1}',bigString).group(0)
'I_AM_THERE'

または：

>>> bigString = "AGAH_I_AM_HERE_RGHFKXXX_I_AM_THERE_XXX_I_AM_NOWHERE_EREXXMHHGRFS"
>>> print(regex.findall('I_AM_(?:HERE){e<=3}',bigString))
['I_AM_HERE', 'I_AM_THERE', 'I_AM_NOWHERE']

新しい正規表現モジュールは (うまくいけば) Python3.4 の一部になります。

pip がある場合は、 Python 3.4 がリリースされるまでpip install regexorと入力するだけpip3 install regexです (正規表現の一部が含まれています...)。

コメントへの回答Is there a way to know the best out of the three in your second example? How to use BESTMATCH flag here?

ベスト マッチ フラグ(?b)を使用して、ベスト マッチを 1 つ取得します。

print(regex.search(r'(?b)I_AM_(?:ERE){e<=3}', bigString).group(0))
# I_AM_THE

または、difflib と組み合わせるか、最初のリテラルとのすべての許容可能な一致のリストを使用してレーベンシュタイン距離を取得します。

import regex

def levenshtein(s1,s2):
    if len(s1) > len(s2):
        s1,s2 = s2,s1
    distances = range(len(s1) + 1)
    for index2,char2 in enumerate(s2):
        newDistances = [index2+1]
        for index1,char1 in enumerate(s1):
            if char1 == char2:
                newDistances.append(distances[index1])
            else:
                newDistances.append(1 + min((distances[index1],
                                             distances[index1+1],
                                             newDistances[-1])))
        distances = newDistances
    return distances[-1]

bigString = "AGAH_I_AM_NOWHERE_HERE_RGHFKXXX_I_AM_THERE_XXX_I_AM_HERE_EREXXMHHGRFS"
cl=[(levenshtein(s,'I_AM_HERE'),s) for s in regex.findall('I_AM_(?:HERE){e<=3}',bigString)]

print(cl)
print([t[1] for t in sorted(cl, key=lambda t: t[0])])

print(regex.search(r'(?e)I_AM_(?:ERE){e<=3}', bigString).group(0))

版画:

[(3, 'I_AM_NOWHERE'), (1, 'I_AM_THERE'), (0, 'I_AM_HERE')]
['I_AM_HERE', 'I_AM_THERE', 'I_AM_NOWHERE']
于 2013-11-13T00:44:16.077 に答える
0

おそらく、動的プログラミングの問題である Longest Common Substring がここで役立つでしょう。ニーズと一致基準に応じて、Longest Common Subseuence を使用できます

于 2013-11-13T02:38:14.587 に答える