时间戳

首页 > 解决方案 > 获取句子（表示为字符串）和短语列表之间的最接近匹配

python-3.x - 获取句子（表示为字符串）和短语列表之间的最接近匹配

问题描述

让我从一个例子开始。在 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其中最接近 list 中的任何字符串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

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

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

更新

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

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

标签： python-3.xstringalgorithmlongest-substring

解决方案

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

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

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

推荐阅读