获得最接近的字符串匹配（字符串大小可能非常不同）

Question

我正在寻找一种方法来找到两个字符串之间最接近的字符串匹配，这两个字符串最终可能具有非常不同的大小。假设我有一个可能的位置列表，例如：

Yosemite National Park

Yosemite Valley

Yosemite National Park Lodge

Yosemite National Park Visitor Center

San Francisco

Golden Gate Park San Francisco

Paris

New York

Manhattan New York

Hong Kong

另一方面，我有多个句子，例如：

“我在 1984 年 11 月 12 日向我的妻子求婚加利福尼亚 Yosemite 中间倾盆大雨
"I love to walk my dog in Central Park, New York"
"I love Hong Kong"

现在说我想从这组句子中提取位置，我会继续这样做吗？我知道 Levenshtein distance algorithm 但我不太确定它在这里是否有效，特别是因为我有更多的位置和更多的句子来尝试和匹配。我想我想要的是每个位置的某种匹配分数，这样我就可以选择得分最高的那个，但我不知道如何计算这个分数。

你们知道怎么做吗？或者甚至是一个实现或 python 包？

提前致谢

Answer 1

您可能想查看来自维基百科的 Aho-Corasick algorithm：

In computer science, the Aho–Corasick algorithm is a string-searching algorithm invented by Alfred V. Aho and Margaret J. Corasick. It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all strings simultaneously. The complexity of the algorithm is linear in the length of the strings plus the length of the searched text plus the number of output matches.

在您的示例中，字符串字典是地点列表，输入文本是句子。有多种语言的几种实现，我推荐flashtext(Python)，举个例子：

from flashtext import KeywordProcessor

keywords = ['Yosemite',
            'Yosemite National Park',
            'Yosemite Valley',
            'Yosemite National Park Lodge',
            'Yosemite National Park Visitor Center',
            'San Francisco',
            'Golden Gate Park San Francisco',
            'Paris',
            'New York',
            'Manhattan New York',
            'Hong Kong']

keyword_processor = KeywordProcessor(case_sensitive=False)
for keyword in keywords:
    keyword_processor.add_keyword(keyword)

sentences = ["I proposed to my wife on the 12th of November 1984, during a crazy downpour in the middle of Yosemite in California",
"I love to walk my dog in Central Park, New York",
"I love Hong Kong"]

for sentence in sentences:
    extracted = keyword_processor.extract_keywords(sentence)
    print(extracted)

输出

['Yosemite']
['New York']
['Hong Kong']

Answer 2

对于这样的工作，您通常使用一个管道来处理这个一般顺序的东西：

删除 "noise" 个单词（又名 "stop words"），例如 "a"、"an"、"the"、"is" 等。如果您四处看看，您会发现各种要过滤掉的停用词列表。
为语料库中的每个 "document" 创建一个向量 space 模型。
创建查询的矢量 space 模型。
计算查询向量与每个候选文档向量之间的 TF-IDF 或余弦距离。
选择最高分作为最有可能的匹配项。

参考资料

我可能应该补充一点，当您有大量文档时，更常使用这种管道，并且每个文档单独也相当大。由于 "documents" 和 "queries" 的表示方式完全相同，因此对于您想要对文档进行分类和分组的情况，它也是 useful/usable——也就是说，找出文档彼此之间的相似程度.

获得最接近的字符串匹配（字符串大小可能非常不同）

Getting the closest string match (with possibly very different string sizes)

language-agnostic

algorithm

string-comparison

string-matching

levenshtein-distance