text-mining - 如何进行邮政地址模糊匹配？

Question

我想知道当格式不同或其中一个拼写错误时如何匹配邮政地址。

到目前为止，我已经找到了不同的解决方案，但我认为它们已经过时且效率不高。我确信存在一些更好的方法，所以如果你有引用资料供我阅读，我相信这个主题可能会让很多人感兴趣。

我找到的解决方案(示例在 R 中):

• 编辑距离，它等于您必须插入、删除或更改以将一个词转换为另一个词的字符数。

  agrep("acusait", c("accusait", "abusait"), max = 2, value = TRUE) ## [1] "accusait" "abusait"

• 音位比较

  library(RecordLinkage) soundex(x<-c('accusait','acusait','abusait')) ## [1] "A223" "A223" "A123"

• 拼写校正器的使用(eventually a bayesian one like Peter Norvig's) ，但我猜地址效率不高。

• 我考虑过使用 Google suggest 的建议，但同样，它对个人邮政地址的效率不是很高。

• 您可以想象使用机器学习监督方法，但您需要存储用户拼写错误的请求才能这样做，这对我来说不是一个选项。

Answer 1

我将其视为拼写纠正问题，您需要在某种字典中找到最接近的匹配词。我所说的“近”是指 Levenshtein 距离，除了最小数量的单字符插入、删除和替换限制太多。其他类型的“拼写错误”也是可能的，例如调换两个字符。

我已经做过几次了，但不是最近。最近的案例与临床试验的伴随药物有关。您会惊讶于有多少种方法可以拼错“acetylsalicylic”。

Here is an outline in C++ of how it is done.

简而言之，字典存储为一个 trie 树，您会看到一个可能拼写错误的单词，您可以尝试在 trie 树中查找它。当你搜索的时候，你会尝试这个词的原样，并且你会在每个点尝试这个词的所有可能的变化。随着您的进行，您有一个整数预算，表示您可以容忍多少更改，每次您进行更改时您都会减少。如果预算用尽，则不允许进行进一步的更改。

现在有一个顶级循环，您可以在其中调用搜索。在第一次迭代中，您使用预算 0 调用它。当预算为 0 时，不允许更改，因此它只是直接查找。如果它找不到预算为 0 的单词，您会以预算为 1 再次调用它，因此它将允许一次更改。如果失败，请尝试将预算设置为 2，依此类推。

我没有尝试过的是部分预算。例如，假设一个典型的改动将预算减少了 2，而不是 1，并且预算变为 0、2、4 等。那么一些改动可以被认为是“更便宜”的。例如，元音替换可能只会使预算减少 1，因此对于一个辅音替换的成本，您可以进行两个元音替换。

如果单词没有拼错，所花费的时间与单词中字母的数量成正比。一般来说，它所花费的时间是单词更改次数的指数。

如果您在 R 中工作(就像我在上面的示例中那样)，我会让它调用 C++ 程序，因为为此您需要编译语言的速度。