在句子（表示为字符串）和短语列表之间获得最接近的匹配

Question

让我从一个例子开始。考虑 python

中的以下列表

cities = [
    'New york'
    'San francisco',
    'California',
    'Las vegas',
    'Chicago',
    'Miami'
]

我还有下面的句子

sentences = [
    "Both of us were new to New York City, and had few or no friends.",
    "Win three more games and he becomes king of San Francisco.",
    "Uncurling from the couch, she started to the bedroom of her father's small Miami apartment."
]

对于每个句子，找出该句子中最接近列表中存在的任何字符串的子字符串。所以，在这个例子中，我想为 sentences 中的每个句子获取最长的子字符串，它最接近列表 cities 中的任何字符串。因此，在这种情况下，我的结果应该如下所示：

desired_result = [
    'New york',
    'San fransisco',
    'Miami'
]

心目中的算法很少，但都不是很理想

算法 1

一个算法可以给出很好的结果，但是在时间复杂度上就很糟糕了。我试图提取一个句子的所有子短语，从 n 个单词子短语到一个带有 n 个标记的句子的单词子短语。然后我使用 difflib.get_close_matches 函数来检测最接近 cities 列表中任何字符串的任何子短语。但是，我们可以清楚地看到，复杂度非常高。对于长度为 n 的句子，我们总共有 O(n*n) 个子短语。此外，城市名单也不小。在我的真实用例中，此列表包含大约 700 万个字符串。

在这种情况下，我的代码如下所示：


def generate_subphrases(sen): 
    subphrases: List[str] = []
    # My logic to generate all possible subphrases
    # . 
    # . 
    # . 
    return subphrases


result = []
for sen in sentences:
    subphrases = generate_subphrases(sen)
    ans = None
    for phrase in subphrases:
        if get_close_matches(phrase, cities):
            ans = phrase
            break
    result.append(ans)

print(result)

算法 2

与以前的方法相比，这要快一些，但是，不如上一个好。使用最后一种方法的好处是我们可以容忍该方法中的一些不匹配。例如，如果 cities 列表甚至包含 New york，也会检测到 New York。但是，在这种情况下，我们甚至不能容忍单个字符不匹配。在我的用例中，就字符不匹配而言，我可以容忍高达 30-35% 的错误。在这种方法中，我用列表中所有城市的联合形成了巨大的正则表达式。然后我使用 re.search 来搜索我句子中的子短语。在我看来，这更快但不是很好。

我想知道我是否可以使用任何数据结构来完成此任务，或者是否可以使用类似于 difflib.get_close_matches 的任何 python 实用函数来搜索整个句子。

更新

我的最终目标是使算法 1 更高效，可能会使用一些我可能不熟悉的字符串算法，或者可能是一些数据结构。我也曾经想到过 `Trie` 数据结构，但同样，这有助于精确匹配，而不是算法 1 中描述的 python 效用函数提供的软匹配。

注意：在这种情况下我没有做 NER 任务。提供的示例只是为了轻松说明事情。出于这个原因，我不能使用像 Spacy 或 NLTK 这样的预训练机器学习模型来识别城市。总体目标不是识别城市，而是识别字符串中最接近字符串列表中任何字符串的子短语

Answer 1

如果您可以在运行算法之前创建可能的匹配字符串，pyahocorasick 将是您用例的完美解决方案，因为它会预先计算出包含您正在尝试的所有城市的特里树匹配。

缺点是您需要提供变体/可能的字符不匹配模式。

对于您的朴素算法 1，我建议只返回大小不超过 M 的子短语，其中 M 是您拥有的字符串列表中最长的标记。（例如，尝试将 10 个单词的子句与最多只有 3 个单词的字符串匹配是没有意义的）。这至少应该有助于加快速度。

在句子（表示为字符串）和短语列表之间获得最接近的匹配

Get closest match between sentence(represented as string) and list of phrases

string

algorithm

python-3.x

longest-substring

算法 1

算法 2

更新