🔤 編集距離（レーベンシュタイン距離）計算機

計算の仕組み

レーベンシュタイン距離（編集距離）は、ある文字列を別の文字列に変えるのに必要な、1文字の「挿入」「削除」「置換」の最小の回数です。1965年にウラジーミル・レーベンシュタインが考案しました。 このツールは、動的計画法で距離を求めます。1つ目の文字列の先頭 i 文字と、2つ目の先頭 j 文字の距離を表に埋めていき、 d[i][j] ＝ 文字が同じなら d[i−1][j−1]、違えば 1 ＋ min(d[i−1][j−1], d[i−1][j], d[i][j−1]) として、表の右下が答えになります。その後、表を逆にたどって、どの文字をどう変えたかの手順も表示します。 類似度は「1 − 距離 ÷ 長い方の文字数」を百分率で表したものです。文字数は見た目の文字（コードポイント）で数えるため、絵文字も1文字として扱います。