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

首先，我没有找到实际的模糊匹配算法。我们使用Dice系数和Levenshtein距离。我正在寻找最聪明的方式来利用这些算法。段落中模糊匹配多词短语的算法

目标：

我试图发现城市的名字在一段文字中，它们发生的顺序。我们有一个约100万个位置名称的列表。我想搜索一段文字，并检测其中一个位置是否存在，然后存储该城市。地点名称可以是单个或多个单词。

例段落：

妈妈你好！山姆和我正在考虑下个月在加拿大 绊倒。我们知道我们已经可以住在约翰的房子里魁北克省城市。我知道你已经在加拿大旅行了很多，所以我想得到你的建议。

就像我说的，我们会在魁北克市启动，那么很可能前往哈利法克斯前开车到 米拉米奇。 2天后我们想去 布雷顿角。最后，我们想看看倡导港看到像湾芬迪的，迪格的事情，圣伊丽莎白的码头

你说话很快！

预期结果

加拿大
魁北克市
加拿大
米罗米奇
哈利法克斯
布雷顿角
提倡港
芬迪
迪格
圣伊丽莎白码头

的问题

我目前的路障湾是如何检测与多个单词的位置名称。我知道我可以分割段成词，然后比较他们对我的列表，如：第一个字对我的位置名单

模糊匹配
如果不匹配，模糊匹配（第一个字+第二字）对我的位置名单
如果不匹配，模糊匹配（第一+第二+三字）对我的地点名称
的列表...等

这是我目前的做法，但它非常慢，而且效率低下。有没有一种聪明的方式可以完成我正在寻找的东西？

来源

2016-06-21 CHawk

段落可以像一串字符串对待，并使用某种字符串匹配算法吗？如https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm匹配多个模式（在你的情况下的位置） – shole

是的，这正是我所期待的。它不做模糊匹配，但完美运作。提交这个答案，我会标记为正确的。 – CHawk

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

我认为一些字符串匹配算法可以工作得很好了你，

这里是他们的列表：String Matching Algorithms

在你的情况，我认为你需要多模式字符串匹配的一个，如Aho–Corasick algorithm

来源

2016-06-23 06:03:04 shole

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

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

回答

相关问题