執筆：金子冴 人はだれしも間違いを犯すものである．徹夜で仕上げた報告書を提出した後，よく見直してみると誤字脱字が山ほど見つかった経験が読者にもあるだろう(もしかすると私だけかもしれないが)．そういう時，もし自動で間違っている単語を見つけてくれるプログラムがあったら…と考える人もいるかもしれない．そこで今回は，文字列同士の似ている度合いを計算する2つの手法を紹介しよう． 　●レーベンシュタイン距離(Levenshtein Distance) 　●ジャロ・ウィンクラー距離(Jaro-winkler Distance) 目次 文字列の類似度，距離 編集処理(挿入，削除，置換) レーベンシュタイン距離(Levenshtein Distance)とは ジャロ・ウィンクラー距離(Jaro-winkler Distance)とは レーベルシュタイン距離とジャロ・ウィンクラー距離の応用可能性 参考 文字列の類似度，距離 初めに類似度というものを理解しよう．類似度とは，2つの対象が似ている度合いを表す尺度である．対象は何でもよく，自然言語処理分野では主に文書，文字列，集合等について類似度を計算する場面が多いように見受けられる．また，今回紹介する手法を見たときに「なんで距離なんだ？」と思った読者も少なくないであろう．自然言語処理分野では，類似度のことを距離と呼ぶ場面がしばしば見られる．類似度と距離の関係は以下のようになる．類似度と距離では値の大小が逆になるため，注意が必要である． 　・2対象が似ている = 類似度が高い = 距離が近い(値が小さい) 　・2対象が似ていない = 類似度が低い = 距離が遠い(値が大きい) 編集処理(挿入，削除，置換) さて，今回紹介する2つの手法を理解するためには事前に編集処理というものを理解しておく必要がある．編集処理とは，ある文字列に対して「挿入(insertion)」，「削除(deletion)」，「置換(substitution)」の３つの操作を組み合わせ，別の文字列に変換する処理を指す．それぞれの操作について，図を交えて解説していこう． ・挿入(insertion) 「挿入」は，文字列に文字を1つ入れる操作である．追加する位置はどこでもよい．例えば，「かんり(管理)」の３文字目(「ん」の後)に「き」を挿入すれば「かんきり(缶切り)」になるし，「コップ」の先頭に「ス」を挿入すれば「スコップ」になる．ただし，追加する文字は１回につき１文字でなければならない．例えば，「たんし(端子)」を「たんぱくしつ(タンパク質)」にするためには３文字挿入する必要があるが，一度に３文字は挿入できないため，「ぱ」の挿入に１回，「く」の挿入に１回，「つ」の挿入に１回，合計３回の挿入操作が必要となる． ・削除(deletion) 「削除」は，文字列の文字を1つ消す操作である．消す位置はどこでもよい．挿入で用いた例を用いて説明すると，「かんきり(缶切り)」の３文字目を削除すれば「かんり(管理)」になるし，「スコップ」の１文字目を削除すれば「コップ」になる．また，「挿入」操作と同様に，削除する文字は１回につき１文字でなければならない． ・置換(substitution) 「置換」は，文字列の文字を1つ別の文字に変える操作である．例えば，「たいこ(太鼓)」の３文字目を「や」に置換すると「たいや(タイヤ)」になり，「テスト」の２文字目を「ン」に置換すると「テント」になる．「挿入」操作，「削除」操作のときと同じく，置換する文字は１回につき１文字でなければならない(図解中の説明は割愛)．また，置換操作は１文字削除⇒１文字挿入でも再現可能であるため，「挿入」と「削除」のみを「編集」処理に採用して距離を計算する場合もある． それでは，編集処理について理解できたところで，まずはレーベンシュタイン距離について解説する． レーベンシュタイン距離(Levenshtein Distance)とは まずはレーベンシュタイン距離の意味と計算方法について確認しよう． レーベンシュタイン距離の意味と計算方法 レーベンシュタイン距離の意味 レーベンシュタイン距離(Levenshtein Distance)は，ある文字列と別の文字列の最小編集距離で表される距離である．なお，計算方法の項目で再度解説するが，編集操作ごとに異なるコストを指定してもよい．そのため，「編集距離が最小である=レーベンシュタイン距離である」と断定することはできないため注意が必要である． レーベンシュタイン距離の計算方法 例として，「ひだるま」(以下，s1)を「けんだま」(以下，s2)に変換する際のレーベンシュタイン距離を計算してみよう． s1をs2に変換する編集パターンはいくつかあるが，その中で以下の２つのパターン(パターンA,B)をピックアップする．なお，今回はs1をs2に変換する場合を考える． 【パターンA：編集回数3回】 　①１文字目に「け」を挿入する． 　②２文字目の「ひ」を「ん」に置換する． 　③４文字目の「る」を削除する． 【パターンB：編集回数4回】 　①１文字目の「ひ」を削除する． 　②１文字目に「け」を挿入する． 　③２文字目に「ん」を挿入する． 　④４文字目の「る」を削除する． … Continue reading 【技術解説】似ている文字列がわかる！レーベンシュタイン距離とジャロ・ウィンクラー距離の計算方法とは