在段落中模糊匹配多个单词短语的算法

Question

首先，我不是在寻找真正的模糊匹配算法。我们同时使用Dice系数和Levenshtein距离。我正在寻找利用这些算法的最聪明方法。

目标：尝试从文本段落中检测出城市名称，并按它们出现的顺序进行存储。我们有一个包含约100万个地名的列表。我希望搜索文本段落，当其中一个这些地点出现时，就会检测到它，然后存储该城市。地名可以由一个或多个单词组成。

示例段落：

“嗨妈妈！Sam和我正计划在下个月通过Canada进行公路旅行。我们知道我们已可以住在Quebec City的John家里。我知道你在加拿大旅行过很多次，所以我想听听你的建议。 像我说的，我们会从魁北克市出发，然后可能开车去Miramichi，然后前往Halifax。两天后我们想去Cape Breton。最后，我们想去Advocate Harbor看看Bay of Fundy、Digby和St. Elizabeth码头等景点。 待会儿再联系你！”

预期结果： - Canada - Quebec City - Canada - Miramichi - Halifax - Cape Breton - Advocate Harbor - Bay of Fundy - Digby - Pier of St. Elizabeth

问题： 我的当前难题是如何检测由多个单词组成的地名。我知道可以将段落分为单词，然后与我的列表进行比较，例如： 1. 将第一个单词与我的地点名称列表进行模糊匹配。 2. 如果没有匹配，则将（第一个单词+第二个单词）与我的地点名称列表进行模糊匹配。 3. 如果没有匹配，则将（第一个单词+第二个单词+第三个单词）与我的地点名称列表进行模糊匹配。 4. ...等等。

这是我目前的方法，但它非常慢且低效。有没有聪明的方法可以实现我想要的功能？

- CHawk

---

这段文字能否被视为单行字符串，并使用某种字符串匹配算法（比如 Aho–Corasick 算法）来匹配多个模式（在你的情况下是位置）？ - shole

是的，这正是我在寻找的。它不进行模糊匹配，但运行得非常完美。请提交它作为答案，我会将其标记为正确的。 - CHawk

谢谢。很高兴知道它有帮助 :) - shole

Answer 1

我认为一些字符串匹配算法非常适合您的需求，

以下是它们的列表：字符串匹配算法 在您的情况下，我认为您需要使用多模式字符串匹配算法，例如Aho-Corasick算法。

- shole

---

这个很棒！作为其他人的参考，我最终使用了这个宝石中的Aho-Corasick实现：https://github.com/ahnick/ahocorasick - CHawk