-2

我必须匹配许多商店名称，而且我很难让 Levenshtein 和 SoundEx 在给定我的数据的情况下产生可接受的结果。

以下是我正在处理的一些示例：

The Home Depot 
Office Depot
Apple store 
Apple 
Walgreens 
Walgreens Denver 
Quiznos 
Quiznos Sandwich Restaurants

因此，例如，给定“Quiznos Sandwich Restaurants”，我想将其与“Quiznos”相匹配……“Walgreens Denver”与“Walgreens”相匹配。我有这些商店名称的完整列表。

任何帮助都会很棒。

4

2 回答 2

1

也许尝试通过“规范化”来缩小搜索范围？从查询中删除诸如“the”和“store”之类的绒毛，通过字典运行它以修复明显的错误和拼写错误？识别和删除明显的位置引用（如上面的“denver”）也可能有所帮助。

编辑：扩展一点（并删除一些其他 CS 主题 ;-) ）-如果您真的想解决“最佳”（最复杂）的方法，您需要获取输入字符串，运行它一些词性标注器（在此处查看有用的问题Java Stanford NLP: Part of Speech labels?），然后使用标注数据删除连接词（例如 - “mcdonalnds around manhatten” - around 可以被识别和删除）。也许它甚至可以帮助识别复数形式（不知道，从未尝试过），因此可以将诸如“华盛顿的家得宝”之类的东西规范化为“家得宝”

于 2012-07-18T04:59:55.507 回答
0

对于这个问题，你知道 Levenshtein 复杂度是 O(mn)，这对于大量数据来说非常高。

通过检查对角线而不是行，并使用lazy evaluation，我们可以在 O(m (1 + d)) 时间内找到 Levenshtein 距离（其中 d 是 Levenshtein 距离），如果距离比常规动态规划算法快得多是小。

惰性评估链接：http ://en.wikipedia.org/wiki/Lazy_evaluation

或者我们也可以用 0 初始化矩阵的第一行，该算法可以用于fuzzy string search文本中的字符串。这种修改给出了文本匹配子串的结束位置。为了确定匹配子串的起始位置，插入和删除的数量可以单独存储，并用于从结束位置计算起始位置。

于 2012-07-18T04:59:50.310 回答