algorithm - 获得最接近的字符串匹配(字符串大小可能非常不同)

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

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

1. “我在 1984 年 11 月 12 日向我的妻子求婚，那是在一次疯狂的加利福尼亚优胜美地中部倾盆大雨”
2. “我喜欢在纽约中央公园遛狗”
3. “我爱香港”

现在假设我想从这些句子集中提取位置，我会继续这样做吗？我知道 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']