段落中多词组的模糊匹配算法 [英] Algorithm for Fuzzy Matching Multiple Word Phrases in a Paragraph
问题描述
首先，我不是在寻找实际的模糊匹配算法.我们同时使用 Dice 的系数和 Levenshtein 距离.我正在寻找最聪明的方法来利用这些算法.
First, I'm not looking for the actual fuzzy matching algorithm. We're using both Dice's Coefficient and Levenshtein Distance. I'm looking for the cleverest way to utilize these algorithms.
目标:
我正在尝试按照城市名称出现的顺序检测文本段落中的城市名称.我们有一个包含约 100 万个位置名称的列表.我想搜索一段文本，并检测何时出现这些位置之一，然后存储该城市.地名可以是单个或多个词.
I'm trying to detect the names of cities in paragraph of text, in the order they occur. We have a list of ~1 million location names. I want to search through a paragraph of text, and detect when one of these locations are present, then store that city. Location names can be a single or multiple words.
示例段落:
妈妈你好！山姆和我正在考虑在加拿大公路旅行下个月.我们知道我们已经可以住在魁北克的约翰家了城市.我知道你在加拿大经常旅行，所以我想得到你的建议.
Hi Mom! Sam and I are thinking of road tripping through Canada in the next month. We know we can already stay at John's house in Quebec City. I know you have traveled a lot in Canada, so I wanted to get your advice.
就像我说的，我们会从魁北克市开始，然后可能会开车到Miramichi，然后前往哈利法克斯.2天后我们想去布雷顿角.最后，我们想看看倡导港看看芬迪湾、迪格比和圣伊丽莎白码头
Like I said, we'd start in Quebec city, then probably drive to Miramichi before heading to Halifax. After 2 days we want to go to Cape Breton. Finally, we want to check out Advocate Harbor to see things like the Bay of Fundy, Digby, and the Pier of St. Elizabeth
尽快与您联系！
预期结果
- 加拿大
- 魁北克市
- 加拿大
- 米拉米奇
- 哈利法克斯
- 布雷顿角
- 倡导港
- 芬迪湾
- 迪格比
- 圣伊丽莎白码头
问题
我目前的障碍是如何检测包含多个单词的地名.我知道我可以将段落拆分为单词，然后将它们与我的列表进行比较，例如:
My current roadblock is how to detect location names with multiple words. I know I can split the paragraph into words, then compare them against my list, like:
- 根据我的位置名称列表模糊匹配第一个单词
- 如果不匹配，则对我的位置名称列表进行模糊匹配(第一个单词 + 第二个单词)
- 如果不匹配，则根据我的位置名称列表进行模糊匹配(第一个 + 第二个 + 第三个单词)
- ...等
这是我目前的方法，但它非常缓慢且效率低下.有没有一种聪明的方法可以完成我正在寻找的东西?
This is my current approach, but it is incredibly slow and inefficient. Is there a clever way I can accomplish what I'm looking for?
推荐答案
我认为某些字符串匹配算法非常适合您，
I think some string matching algorithm works perfectly well for you,
这是它们的列表:字符串匹配算法
在您的情况下，我认为您需要多个模式字符串匹配一个，例如 Aho-Corasick 算法
In your case, I think you need multiple pattern string matching one, such as Aho–Corasick algorithm
这篇关于段落中多词组的模糊匹配算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
