レーベンシュタイン距離
今日は、月１回の『研究開発の日』
システムを音声操作すべく、思考錯誤を重ねています。
以前ブログに書いた「表記ゆれ」対策の「編集距離」について調べた内容を残しておこうと思います。
例えば、ネーブル、ポンカン、シークァーサーの中から、シークワーサーを選択させるにはコンピューターにはどんな指示をだしたら良いでしょうか？
完全に一致せずとも、類似したものを見つけ出すには、編集距離（レーベンシュタイン距離）という考え方を使います。
編集距離とは、＜キーワードA＞を＜キーワードB＞に変換するのに必要な手数（距離）を数値化したものです。
この距離が小さいほど、類似していると判断できます。
早速、それぞれの編集距離についてみてみましょう。
----------------------------------------------------------------------------
ネーブル → シークワーサー 距離：9
ポンカン → シークワーサー 距離：9
シークァーサー → シークワーサー 距離：1
----------------------------------------------------------------------------
レーベンシュタイン距離は、下記表を作成して、距離を割り出しています。
s | i | - | k | u | w | a | - | s | a | - | ||
s | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
i | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
- | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
k | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
w | 4 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
a | 5 | 4 | 3 | 2 | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 6 |
- | 6 | 5 | 4 | 3 | 2 | 2 | 2 | 1 | 2 | 3 | 4 | 5 |
s | 7 | 6 | 5 | 4 | 3 | 3 | 3 | 2 | 1 | 2 | 3 | 4 |
a | 8 | 7 | 6 | 5 | 4 | 4 | 4 | 3 | 2 | 1 | 2 | 3 |
- | 9 | 8 | 7 | 6 | 5 | 5 | 5 | 4 | 3 | 2 | 1 | 2 |
10 | 9 | 8 | 7 | 6 | 6 | 6 | 5 | 4 | 3 | 2 | 1 |
↓ 削除 → 挿入 斜め(1増) 置換
今回は、削除、挿入、置換を距離1としてカウントしましたが、置換を距離2としてカウントする考え方もあるようです。
