3

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

到目前为止，我已经找到了不同的解决方案，但我认为它们已经很老了而且效率不高。我确信存在一些更好的方法，所以如果您有参考资料供我阅读，我相信这是一个可能会引起几个人兴趣的主题。

我找到的解决方案（示例在 R 中）：

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

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

  • 音位比较

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

  • 使用拼写校正器（最终是像彼得诺维格那样的贝叶斯校正器），但我猜对地址不是很有效。

  • 我想使用谷歌建议的建议，但同样，它在个人邮政地址上效率不高。

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

4

2 回答 2

1

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

我已经这样做了几次，但不是最近。最近的病例与临床试验的伴随药物有关。你会惊讶于有多少种方法可以拼错“乙酰水杨酸”。

这是 C++ 中如何完成的大纲。

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

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

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

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

如果你在 R 中工作（就像我在上面的例子中一样），我会让它调用 C++ 程序，因为你需要编译语言的速度。

于 2016-03-21T12:35:47.430 回答
0

扩展 Mike 不得不说的内容，并使用 R 中的字符串匹配库 stringdist 来匹配在 ARCGIS 的地理编码功能中出错的地址向量：

rows<-length(unmatched$addresses)
#vector to put our matched addresses in
matched_add<-rep(NA, rows)
score<-rep(NA, rows)

#for instructional purposes only, you should use sapply to apply functions to vectors

 for (u in c(1:rows)){
     #gives you the position of the closest match in an address vector

     pos<-amatch(unmatched$address[u],index$address, maxDist = Inf)
     matched_add[u]<-index$address[pos]

     #stringsim here will give you the score to go back and adjust your
     #parameters

     score[u]<-stringsim(unmatched$address[u],index$address[pos])
}

Stringdist 有多种方法可用于查找近似匹配，包括 Levenshtein (method="lv")。您可能需要修改这些以尽可能适合您的数据集。

于 2017-11-29T20:01:39.153 回答