我有一个字符串
s = "mouse"
和一个字符串列表
sub_strings = ["m", "o", "se", "e"]
我需要找出与 s 匹配的列表中 sub_strings 的最佳和最短匹配子集是什么。做这个的最好方式是什么?理想的结果是 ["m", "o", "se"] 因为它们一起拼写为 mose
我有一个字符串
s = "mouse"
和一个字符串列表
sub_strings = ["m", "o", "se", "e"]
我需要找出与 s 匹配的列表中 sub_strings 的最佳和最短匹配子集是什么。做这个的最好方式是什么?理想的结果是 ["m", "o", "se"] 因为它们一起拼写为 mose
import difflib
print difflib.get_close_matches(target_word,list_of_possibles)
但不幸的是,它不适用于您上面的示例,您可以改用 Levenstein 距离...
def levenshtein_distance(first, second):
"""Find the Levenshtein distance between two strings."""
if len(first) > len(second):
first, second = second, first
if len(second) == 0:
return len(first)
first_length = len(first) + 1
second_length = len(second) + 1
distance_matrix = [[0] * second_length for x in range(first_length)]
for i in range(first_length):
distance_matrix[i][0] = i
for j in range(second_length):
distance_matrix[0][j]=j
for i in xrange(1, first_length):
for j in range(1, second_length):
deletion = distance_matrix[i-1][j] + 1
insertion = distance_matrix[i][j-1] + 1
substitution = distance_matrix[i-1][j-1]
if first[i-1] != second[j-1]:
substitution += 1
distance_matrix[i][j] = min(insertion, deletion, substitution)
return distance_matrix[first_length-1][second_length-1]
sub_strings = ["mo", "m,", "o", "se", "e"]
s="mouse"
print sorted(sub_strings,key = lambda x:levenshtein_distance(x,s))[0]
这将始终为您提供与目标“最接近”的词(对于最接近的一些定义)
levenshtein 功能从:http://www.korokithakis.net/posts/finding-the-levenshtein-distance-in-python/ 窃取
您可以使用正则表达式:
import re
def matches(s, sub_strings):
sub_strings = sorted(sub_strings, key=len, reverse=True)
pattern = '|'.join(re.escape(substr) for substr in sub_strings)
return re.findall(pattern, s)
这至少短而快,但不一定会找到最佳匹配集;太贪心了。例如,
matches("bears", ["bea", "be", "ars"])
返回["bea"]
,什么时候应该返回["be", "ars"]
。
代码说明:
第一行按长度对子字符串进行排序,以便最长的字符串出现在列表的开头。这确保了正则表达式将更喜欢较长的匹配而不是较短的匹配。
第二行创建一个由所有子字符串组成的正则表达式模式,由|
符号分隔,表示“或”。
第三行仅使用该re.findall
函数查找给定字符串中模式的所有匹配项s
。
此解决方案基于用户Running Wild的此答案。它使用Stefan Behnel的包使用Aho-Corasick 算法有效地找到目标中子串的所有匹配项,然后使用动态规划来找到答案。acora
import acora
import collections
def best_match(target, substrings):
"""
Find the best way to cover the string `target` by non-overlapping
matches with strings taken from `substrings`. Return the best
match as a list of substrings in order. (The best match is one
that covers the largest number of characters in `target`, and
among all such matches, the one using the fewest substrings.)
>>> best_match('mouse', ['mo', 'ou', 'us', 'se'])
['mo', 'us']
>>> best_match('aaaaaaa', ['aa', 'aaa'])
['aaa', 'aa', 'aa']
>>> best_match('abracadabra', ['bra', 'cad', 'dab'])
['bra', 'cad', 'bra']
"""
# Find all occurrences of the substrings in target and store them
# in a dictionary by their position.
ac = acora.AcoraBuilder(*substrings).build()
matches = collections.defaultdict(set)
for match, pos in ac.finditer(target):
matches[pos].add(match)
n = len(target)
# Array giving the best (score, list of matches) found so far, for
# each initial substring of the target.
best = [(0, []) for _ in xrange(n + 1)]
for i in xrange(n):
bi = best[i]
bj = best[i + 1]
if bi[0] > bj[0] or bi[0] == bj[0] and len(bi[1]) < bj[1]:
best[i + 1] = bi
for m in matches[i]:
j = i + len(m)
bj = best[j]
score = bi[0] + len(m)
if score > bj[0] or score == bj[0] and len(bi[1]) < len(bj[1]):
best[j] = (score, bi[1] + [m])
return best[n][1]