文字列の類似度を測る編集距離
仕事である固有名詞に対してデータソースがAのものとBのもので、微妙に表記ゆれがあったため名寄せ作業をおこなう必要があった。
目で見ていくとキリがないので文字列の類似度測って閾値以上のものをリストアップした上で目で見ると効率が良くなりそうなので文字間の類似度比較について調べた。
文字の編集距離
ある文字Aに対して何回の「編集」をしたら別の文字Bになるか、このときの回数を編集距離という。
編集距離、つまり編集した回数が少ないほどその文字同士は似ている(近い)と考えられる。
同じ文字間でも、編集の仕方はいろいろと考えられるが、考えられる最低編集回数を見ることで類似度を考える。
「編集」とは
一言に「編集」といっても、様々なものが考えられる。
以下で、「編集」とされる要素を紹介するが、それら要素を目的に応じて組み合わせて距離を測る。
挿入
文字Aに文字を加えて文字Bにする。
A:東大
B:東大赤門
ならば、「東大」の後ろに「赤」「門」の2文字を挿入している。
挿入さえされていたら文字の間でも文字の頭でもよい。
削除
文字Aの文字を削除して文字Bにする。
A:東京大学
B:東大
置換
文字Aの文字をある文字に変えて文字Bにする。
ならば、「東」→「大」、「京」→「阪」の2置換。
レーベンシュタイン距離
上記の「挿入」「削除」「置換」を用いた編集回数で距離を求める場合、その距離をレーベンシュタイン距離(Levenshtein distance)といい、一般的によく用いられる。
ならば、最短編集(多分...)は
そのため、編集回数は1 + 1 + 4 = 6より、A,Bのレーベンシュタイン距離は6となる。
他の距離
レーベンシュタイン距離以外にも、編集の定義を変更・追加した様々な距離が提案されている。
例えば、レーベンシュタイン距離の「挿入」「削除」「置換」に「転置」を加えた4種の編集でのDamerau–Levenshtein distanceや、「挿入」「削除」「複写」「複写解除(un-copy)」の4種のCompression distance、「挿入」「削除」「移動」の3種のstring edit distance with movesなどがある。
「複写」「複写解除(uncopy)」「移動」の意味は以下。
転置
文字Aの隣接する文字を入れ替えて文字Bにする。
ならば、隣接する「京」「大」部分を入れ替えて(転置して）「大」「京」にすることで「東大京大」になる。 ちなみに、「置換」で考えた場合は「京」→「大」、「京」→「大」の2置換となる。
複写
文字Aの一部の文字をもう1度繰り返して文字Bにする。
A.東大様 B.東大様東大東大
ならば、「東大」を2回繰り返して（複写して）いるので2複写となる。
複写解除(uncopy)
複写の逆で、文字Aの一部の繰り返し文字を削除して文字Bにする。
A.東大様東大東大 B.東大様
ならば、「東大」を2回削除しているので2複写解除となる。
移動
文字Aの文字を文字Bにする。
A.なう東大経済学部 B.東大経済学部なう
ならば、「なう」が末尾に移動している。
この際、「な」「う」の2文字が移動しているので2移動とするのか、隣接するひとかたまりの「なう」が移動しているので1移動とするかは利用したい状況によって定義を変える。
距離の標準化
編集回数は文字の長さに強く依存する。
例えば、
A.鈴木 B.大福
のレーベンシュタイン距離は2である。 一方で、
C.東大経済学部 D.阪大政経学部
のレーベンシュタイン距離は3となる。
A,Bの字面は全く似ておらず、C,Dは割と似ているが、レーベンシュタイン距離では前者の方が似ていることになる。
これは、A,Bの文字数が少なく、C,Dの文字数が多いのが原因となっている。
そのため、文字数に依存しないように、文字数で割るなどの標準化をおこなうとより適切な類似度になる。
なお、文字数で割るとA,Bは2/2 = 1、C,Dは3/6 = 0.5でc,dの方が近くなる。
編集内容の工夫
編集内容によって重みを変えて編集回数を求める、例えば編集削除の場合は1、挿入の場合は2にする、など。
ジャロウィンクラー距離
レーベンシュタイン距離の他に、ジャロウィンクラー距離というものもある。 これは、ある文字列と別の文字列で一致する文字数と置換の要不要（部分的な違い）から距離を計算する。
詳細は複雑なので以下を参考。
部分的な違いを基準としているので、レーベンシュタイン距離と比較してスペルミスなどに強いようだ。
