郵便番号ファジーマッチングの仕方は？

Question

郵便住所の形式が異なる場合や、郵便住所の1つが誤って綴られている場合に、郵便住所の照合方法を知りたいと思います。

これまでのところ、私はさまざまな解決策を見つけましたが、かなり古くて効率的ではないと思います。私はいくつかのより良い方法が存在すると確信しています。もし私が読むための参照があれば、それはいくつかの人に興味があるかもしれない主題であると確信しています。私が見つけた

ソリューションは、（例は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の提案を使用することについて約束していますが、同様に個人の郵便住所ではあまり効率的ではありません。

• マシンラーニングの管理アプローチを使用して想像することができますが、私にはオプションではないというユーザーの誤った要求を保存する必要があります。

Answer 1

私はこれをスペルチェックの問題として見ています。ここでは、辞書の中で最も近い単語を見つける必要があります。 「近い」とは、1文字の挿入、削除、置換の最小数が制限的すぎることを除いて、Levenshtein距離です。 他の種類の「スペルミス」も可能です。たとえば、2文字を転置します。

私はこれを数回しましたが、最近は行っていません。 最新のケースは、治験のための併用薬と関連していました。 「アセチルサリチル酸」のスペルを間違える方法がいくつあるか驚かれるでしょう。

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

簡単に言えば、辞書はトライとして保存され、そしてあなたは、あなたがトライでルックアップするためにしようとし、おそらくスペルミスの単語が提示されています。 検索する際には、そのまま単語を試してみて、それぞれの点で可能なすべての単語の変更を試してみてください。 あなたが行っているように、変更の可能性のある整数があります。これは変更を加えるたびに減少します。 予算を使い果たした場合、これ以上の変更は許可されません。

ここで、検索を呼び出すトップレベルのループがあります。 最初の繰り返しでは、予算が0であると呼びます。 予算が0の場合、変更は許可されないため、単に直接検索になります。 予算が0の単語が見つからない場合は、予算を1として再度呼び出すので、1回の変更が許可されます。 これが失敗した場合は、2の予算を試してください。

私が試したことがないものは、部分予算です。 たとえば、典型的な変更によって予算が1ではなく2で減り、予算が0,2,4などになるとします。 次に、いくつかの変更は「安価」と見なすことができます。たとえば、母音の置換は予算を1だけ減らすことができるため、子音の置換のコストは2つの母音の置換を行うことができます。

単語のスペルが間違っていない場合、かかる時間は単語の文字数に比例します。 一般に、時間がかかると、単語の改変数が指数関数的になります。

Rで作業している場合（上記の例のように）、コンパイルされた言語の速度が必要なので、C++プログラムを呼び出す必要があります。マイクが言っていたものの拡張、とArcGISのジオコーディング機能で実行エラーが発生したアドレスのベクトルを一致させるためにRにライブラリstringdistにマッチする文字列を使用して

Answer 2

：

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"）を含む近似マッチ。あなたはおそらくあなたのデータセットに合わせてできるだけ早くこれらを使って調整したいと思うでしょう。