レーベンシュタイン距離で文字列の差分を調べる
正しい住所と間違った住所の差分に
間違った住所をどうやって見つけていくかですが、基本的には郵便データにある「都道府県・市・区・町・村・郡・町域」と入手した名刺からスキャンした住所を比較していきます。
きちんとマッチングできればそれでよしなんですが、当然、誤認識された住所については一致しません。
で、不一致になった住所について、候補となりうる住所の部分となるべく近しい住所を調べるのですが、その方法としてレーベンシュタイン距離という方法をとっています。
具体的にはそれぞれの住所を比較して、その違っている文字数を調べるというものです。
参考ソースコード
難しい理論は置いといて今日は参考になるソースコードを添付しておきます。
下記は、Visual Basicの例です。
'************************************************************************ '* (.NET)文字列の比較 / 第1引数:元のテキスト 第2引数:比較テキスト '************************************************************************ Public Function lsDist(baseText As String, tryText As String) As Integer Dim matrix(,) As Integer Dim matmin() As Integer Dim i As Integer, j As Integer, cost As Integer lsDist = 0 If (baseText = tryText) Then Exit Function End If If (Len(baseText) = 0) Then lsDist = Len(tryText) Exit Function End If If (Len(tryText) = 0) Then lsDist = Len(baseText) Exit Function End If ReDim matrix(Len(baseText), Len(tryText)) For i = 0 To Len(baseText) matrix(i, 0) = i Next i For j = 0 To Len(tryText) matrix(0, j) = j Next j For i = 1 To Len(baseText) For j = 1 To Len(tryText) cost = IIf(Mid$(baseText, i, 1) = Mid$(tryText, j, 1), 0, 1) matmin = {matrix(i - 1, j) + 1, matrix(i, j - 1) + 1, matrix(i - 1, j - 1) + cost} matrix(i, j) = matmin.Min Next j Next i lsDist = matrix(Len(baseText), Len(tryText)) End Function
次にExcelで使用する場合もあると思いますので Visual Basic for Applications(VBA)もあわせて添付しておきます。
'************************************************************************ '* (VBA)文字列の比較 / 第1引数:元のテキスト 第2引数:比較テキスト '************************************************************************ Public Function lsDist(baseText As String, tryText As String) As Integer Dim matrix() As Variant Dim i As Integer, j As Integer, cost As Integer lsDist = 0 If (baseText = tryText) Then Exit Function End If If (Len(baseText) = 0) Then lsDist = Len(tryText) Exit Function End If If (Len(tryText) = 0) Then lsDist = Len(baseText) Exit Function End If ReDim matrix(Len(baseText), Len(tryText)) For i = 0 To Len(baseText) matrix(i, 0) = i Next i For j = 0 To Len(tryText) matrix(0, j) = j Next j For i = 1 To Len(baseText) For j = 1 To Len(tryText) cost = IIf(Mid$(baseText, i, 1) = Mid$(tryText, j, 1), 0, 1) matrix(i, j) = WorksheetFunction.Min(matrix(i - 1, j) + 1, matrix(i, j - 1) + 1, matrix(i - 1, j - 1) + cost) Next j Next i lsDist = matrix(Len(baseText), Len(tryText)) End Function
閲覧数が伸びているのでC#の例も追記しておきます。
// ************************************************************************ // * (.NET)文字列の比較 / 第1引数:元のテキスト 第2引数:比較テキスト // ************************************************************************ public static int Levenshtein_Distance(string baseText, string tryText) { int[,] matrix; int[] matmin; int i; int j; int cost; int lsDist = 0; if ((baseText == tryText)) return lsDist; if (baseText.Length == 0) { lsDist = tryText.Length; return lsDist; } if (tryText.Length == 0) { lsDist = baseText.Length; return lsDist; } matrix = new int[baseText.Length + 1,tryText.Length + 1]; for (i = 0; i < baseText.Length; i++) matrix[i, 0] = i; for (j = 0; j < tryText.Length; j++) matrix[0, j] = j; for (i = 1; i < baseText.Length; i++) { for (j = 1; j < tryText.Length; j++) { cost = baseText.Substring(i, 1) == tryText.Substring(j, 1) ? 0 : 1; matmin = new[] { matrix[i - 1, j] + 1, matrix[i, j - 1] + 1, matrix[i - 1, j - 1] + cost }; matrix[i, j] = matmin.Min(); } } return matrix[baseText.Length - 1, tryText.Length - 1]; }
誤住所発見ツールの公開
このレーベンシュタイン距離の方法により、誤住所発見ツールは作られています。
[誤住所/統廃合市町村/京都通り名]を判別して分割する
よければ使ってみてください。
使い方のYouTubeはこちら
その他にもさまざまな名寄せ処理の無料サービスを提供しています。
※おかしなとこあったら教えてくださるとうれしいです。
それではまた。