レーベンシュタイン距離に触れてみる
職場で、「レーベンシュタイン距離」というものがあることを教わった。切っ掛けは、様々な部品の仕様値について、表現の揺らぎに負けない検索方法を模索していたことだった。ネジの表現一つとってもみても、
- M6-10L（ハイフン）
- M6×10L（掛け算の「×」）
- M6*10L（アスタリスク）
- M6x10L（エックスの小文字）
- M6X10L（エックスの大文字）
など様々。同じ人でも、定まっていなかったりする。正規表現を使えばかなり高度なマッチングが可能なものの、部品の仕様毎にパターンを作成するのは現実的ではない。そこで教わったのが、レーベンシュタイン距離だった。
レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される[1]。名称は、1965年にこれを考案したロシアの学者ウラジーミル・レーベンシュタイン (露: Влади́мир Левенште́йн) にちなむ。
引用元：Wikipedia
つまり、レーベンシュタイン距離が短いほど（＝数値が小さいほど）、二つの文字列は似ているということか。
原理を理解して自作できればベストだが、ここはWeb上に公開されているコードをお借りして、まずはレーベンシュタイン距離に触れてみることにした。
まず、引用元はこちら（ありがとうございます）。
[excel] Levenshtein VBAでの距離 [excel-vba] | CODE Q&A 問題解決 [日本語]
この中の、「Levenshtein3」を使ってみた。
一致率100％があれば問題ないが、100％のものが無かったとしても、例えば「80％以上のものを表示する」としておけば、幾つかの「候補」を得ることが出来る。
これは面白い。これとあれを組み合わせて、ああすれば・・・。
参考まで。
