人工知能してみる

人工知能の中の人が機械学習とか統計とかAI的なことを書き連ねます

文字列類似度評価 レーベンシュタイン距離 / ジャロ・ウィンクラー距離

こんにちは。Grahamianです。 文字列の類似度を評価するアルゴリズムであるレーベンシュタイン距離とジャロ・ウィンクラー距離です。

レーベンシュタイン距離

レーベンシュタイン距離は2つの文字列の間の編集距離を示します。編集とは「挿入」と「削除」(と置換)です。距離とは2つの文字列が等しくなるまでの編集回数です。文字列の類似度はこの距離の最短距離で表します。

Pythonであれば python-Levenshtein というライブラリがあるので簡単に導入することができます。ライブラリによってはマルチバイト文字に対応できないケースもあるので日本語に適用する場合は注意が必要です。

使い方はこちらのQiita記事に書いてあるので省略します。 qiita.com

レーベンシュタイン距離は、長さがm, nの文字列間の距離がO(mn)で計算できることが知られています。これは縦横がm+1, n+1の長さの行列を用いて動的計画法で計算を行います。動的計画法については長くなるので別の記事に譲ります。 mathwords.net

計算例

レーベンシュタイン距離について簡単な例を出します。"dog" と "bag" の距離を考えてみましょう。 編集に置換を許すと距離は"2"になります。
d は b に置換 距離+1
o は a に置換 距離+1
g はそのまま 距離+0
=> 合計距離は "2"

置換を許さず挿入と削除の場合は距離は4になります d を削除 距離+1
o を削除 距離+1
b を挿入 距離+1
a を挿入 距離+1
g はそのまま 距離+0
=> 合計距離は"4"

ジャロ・ウィンクラー距離

ジャロ・ウィンクラー距離はレーベンシュタイン距離よりミスタイプの検知に特化したアイディアです。Jaro距離と呼ばれるメトリクスに文字列の先頭数文字の一致度を加算しています。レーベンシュタイン距離が有名かつ分かりやすいのであんまり知られていないかもしれません。このジャロ・ウィンクラー距離も python-Levenshtein から呼び出すことができます。

Jaro距離の定義は下記のとおりです。 f:id:Grahamian:20180223001936p:plain 引用: A Comparison of String Metrics for Matching Names and Records

s, t が元の文字列の長さ、s', t' が一致する文字列の長さ、T_{s,' t'} が置換数です。これで得られたJaro距離を使って下記の用に文字列の先頭数文字における一致度を加えます。

f:id:Grahamian:20180223003309p:plain

sim_jJaro距離でsim_wがジャロ・ウィンクラー距離です。lは先頭から何文字を考慮に入れるかで英語だと最大4文字までを使うようです。これはタイプミスをするときは先頭の文字は正しく打ち込むという調査結果を反映したものらしいです。英語だと複数文字の接頭語があるのでpは長めにとってもうまくいきますが日本語だと長い接頭語は少ないのでl=1, 2が望ましいようです。pは定数で論文だと0.1です。

まとめ

レーベンシュタイン距離はそこそこ理解できているのですがジャロ・ウィンクラー距離はちゃんと理解してないので頑張りたいところ。実際に組んでみるのが一番早いんだろうなあ。
文字列の類似度というと直ぐにembeddedしたがってword2vecを使う人がいるのですが状況によってはレーベンシュタイン距離の方が上手くいくケースは多々あります。word2vecと違い学習もいらず高速に動作するのも良い点です。こういう古典的なアルゴリズムも一個ずつモノにしていきたいですね。