从字符串列表中找到最佳子集以匹配给定字符串

Question

我有一个字符串

s = "mouse"

以及一个字符串列表

sub_strings = ["m", "o", "se", "e"]

我需要找到与字符串s最匹配的子字符串列表中最好且最短的匹配子集。 如何做到这一点呢？ 理想的结果应该是["m", "o", "se"]，因为它们可以拼成mose。

- smor

---

这里的正确答案可能取决于字符串长度与子字符串数量的比较。在实际操作中，该字符串会有多长？你会有多少子串？它需要非常快吗？ - Jason Orendorff

“最好和最短”是什么意思？ - Karl Knechtel

字符串可以尽可能大，子字符串也可以相当大，但所有子字符串都必须是字符串的一部分。 - smor

请查看这个问题及其答案。 - Gareth Rees

Answer 1

您可以使用正则表达式：

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"])

当应该返回["be", "ars"]时，它返回了["bea"]。

---

代码的解释：

• 第一行按长度对子字符串进行排序，以便最长的字符串出现在列表的开头。这确保正则表达式优先选择较长的匹配项而不是较短的匹配项。

• 第二行创建一个正则表达式模式，其中包含所有子字符串，用|符号分隔，表示“或”。

• 第三行只使用re.findall函数在给定的字符串s中查找模式的所有匹配项。

- Jason Orendorff

---

我想到了一个可能导致它被减一的原因，所以我稍微编辑了答案。 - Jason Orendorff

我没有减去任何东西，抱歉。这是完美的答案，谢谢大家。 - smor

-1 是因为它没有解决 OP 的问题。你在回答中自己也说了：“它太贪心了”。 - Gareth Rees

谢谢，加雷斯。这个没什么好争论的。 - Jason Orendorff

Answer 2

这个解决方案基于用户Running Wild的这个答案。它使用Stefan Behnel的acora包来高效地使用Aho–Corasick算法找到目标字符串中所有子字符串的匹配，然后使用动态规划来求解答案。

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]

- Gareth Rees

Answer 3

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]

这将始终为您的目标提供“最接近”的单词（对于某些定义而言）。

从http://www.korokithakis.net/posts/finding-the-levenshtein-distance-in-python/窃取的Levenshtein函数。

- Joran Beasley

---

非常感谢您的努力。这是一个很好的开始。也许我没有描述清楚，但让我们使用另一个例子。假设子字符串只是sub_strings = ["m", "o", "se", "e"]，那么我期望组合["m", "o", "se"]成为结果，因为它们在一起拼出了mose，这是最接近mouse的组合！我会更新我的例子。 - smor

然后SE应该是最接近的...哦，我明白你在做什么了...不知道...从这里开始并从那里工作，你可能需要itertools.combinations（或者也许是排列...我经常混淆这两个）...而且它可能会很慢...非常慢... - Joran Beasley

返回翻译的文本：-1，因为它没有解决 OP 的问题。答案中的代码打印了“mo”，这是错误的。 - Gareth Rees