編集距離

計算機の世界では、文字の並びの比較は至る所で行われています。例えば、探し物をするための仕掛けに入力された言葉と、目的地の題名の類似点を調べたり、書き間違いを正すための候補を示したりする際に、文字の並び同士がどれくらい似ているかを判断する必要があります。レーベンシュタイン距離とは、このような文字の並びの類似度を測るための物差しのひとつです。二つの文字の並びが与えられた時、それらの間のレーベンシュタイン距離は、片方の文字の並びをもう片方の文字の並びに変換するために必要な最小の編集回数で表されます。編集操作には、文字の挿入、削除、置換の三つの種類があります。具体的に、文字列「ねこ」と「ねずみ」のレーベンシュタイン距離を計算してみましょう。「ねこ」を「ねずみ」に変換するには、「こ」を削除し、「ず」「み」を挿入する必要があります。あるいは、「こ」を「ず」に置換し、「み」を挿入する方法もあります。いずれの場合も、二回の編集が必要です。つまり、「ねこ」と「ねずみ」のレーベンシュタイン距離は２です。レーベンシュタイン距離が小さいほど、二つの文字の並びは類似しているとみなされます。例えば、「りんご」と「みかん」のレーベンシュタイン距離は３ですが、「りんご」と「りんこ」のレーベンシュタイン距離は１です。これは、「りんご」と「りんこ」の方が「りんご」と「みかん」より似ているという直感と一致しています。レーベンシュタイン距離は、様々な場面で活用されています。例えば、文章の剽窃検出や、データベースにおけるあいまい検索、音声認識などです。情報処理において、文字の並びの比較は欠かせないものであり、レーベンシュタイン距離はそのための強力な道具として利用されています。