7 
bigString = "AGAHKGHKHASNHADKRGHFKXXX_I_AM_THERE_XXXXXMHHGRFSAHGSKHASGKHGKHSKGHAK"
smallString = "I_AM_HERE"

我应该使用哪种有效算法来找到与“smallString”密切匹配的“bigString”子字符串

output = "I_AM_THERE"

与小字符串相比，输出可能很少有插入和删除。

编辑：找到了一个很好的例子，非常接近我的问题：如何将变量错误添加到正则表达式模糊搜索。Python

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，只需输入pip install regexorpip3 install regex直到 Python 3.4 出来（带有正则表达式的一部分......）

回复评论Is there a way to know the best out of the three in your second example? How to use BESTMATCH flag here?

使用最佳匹配标志(?b)来获得单个最佳匹配：

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

或者与 difflib 结合使用，或者将 levenshtein 距离与第一个文字的所有可接受匹配项的列表相结合：

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

这是一个有点hacky的方法difflib：

from difflib import *

window = len(smallString) + 1  # allow for longer matches
chunks = [bigString[i:i+window] for i in range(len(bigString)-window)]
get_close_matches(smallString,chunks,1)

输出：

['_I_AM_THERE']
于 2013-11-12T22:08:14.093 回答
0

也许动态规划问题最长公共子串在这里会有一些用处。根据您的需要和匹配标准，您也许可以使用最长公共子序列

于 2013-11-13T02:38:14.587 回答