2つの文字列から、レーベンシュタイン距離(編集距離)と類似度 1 − d/max(長さ) を計算します。表記ゆれの検出やあいまい検索、OCR結果の誤り評価などで、文字列がどれだけ近いかを数値で確かめたいときに使えます。
レーベンシュタイン距離 計算ツール(編集距離・類似度)
2つの文字列のレーベンシュタイン距離(編集距離)と類似度を計算し、必要な挿入・削除・置換の回数を表示します。
使い方
- 「文字列A」と「文字列B」に比べたい文字列を入力します。
- 入力すると自動で計算されます。「計算する」を押しても計算できます。
- 編集距離、類似度、文字数、編集の内訳(置換・挿入・削除の回数の一例)を確認します。
計算式
レーベンシュタイン距離は、文字列Aを文字列Bに変えるのに必要な「1文字の挿入・削除・置換」の最小回数です。各操作のコストは1です。動的計画法で表 D を埋めて求めます。
D[i][0] = i、D[0][j] = j
D[i][j] = min( D[i−1][j] + 1, (削除)
D[i][j−1] + 1, (挿入)
D[i−1][j−1] + c ) (置換。同じ文字なら c=0、違えば c=1)
類似度 = 1 − D[m][n] ÷ max(m, n)
m は文字列Aの文字数、n は文字列Bの文字数で、右下の D[m][n] が編集距離です。
よく使われる場面
編集距離は、検索窓の入力ミスに対する「もしかして」候補の提示、商品名や住所の表記ゆれの統合、OCRや音声認識の結果がどれだけ正解と違うかの評価などに使われます。音声認識の分野では、文字単位の編集距離を正解の文字数で割った値を文字誤り率(CER)、単語単位で計算した値を単語誤り率(WER)と呼びます。DNA配列の比較など、文字列以外の並びにも同じ考え方が使われます。
計算例
初期値の「kitten」(6文字)と「sitting」(7文字)で計算します。
- k を s に置換:sitten
- e を i に置換:sittin
- 末尾に g を挿入:sitting
これより少ない回数では変換できないため、編集距離は3(置換2・挿入1・削除0)です。類似度は 1 − 3 ÷ 7 = 0.5714 になります。
結果の見方
- 編集距離0は完全一致です。値が大きいほど文字列が離れています。
- 編集距離は文字数の影響を受けるため、長さの違う組み合わせを比べるときは類似度(0〜1)を見ると便利です。
- 表記ゆれの候補を探す場合、たとえば距離1〜2の語を候補として目で確認する、といった使い方が一般的です。しきい値はデータに合わせて決めます。
- 内訳は最短手順の一例です。同じ回数で済む別の手順がある場合もあります。
注意点
- 大文字と小文字、全角と半角、ひらがなとカタカナはすべて別の文字として扱います。必要に応じて、入力前に表記をそろえてください。
- 絵文字などのサロゲートペアも1文字として数えるよう、文字単位で分割しています。ただし、複数の文字を組み合わせた絵文字や結合文字は複数文字になることがあります。
- 隣り合う文字の入れ替え(例:ab→ba)は置換2回と数えます。入れ替えを1回と数えるのはダメラウ・レーベンシュタイン距離という別の指標です。
- 文字列の長さはそれぞれ2,000文字までです。計算量は文字数の積に比例します。
- 前後の空白も1文字として数えます。比べる前に余分な空白を取り除いておくと、意図しない差を防げます。
編集距離(レーベンシュタイン)のよくある質問
Q. 編集距離とレーベンシュタイン距離は同じですか?
A. 一般に「編集距離」といえば、挿入・削除・置換のコストを1とするレーベンシュタイン距離を指すことが多いです。操作の種類やコストを変えた別の編集距離もあります。
Q. 日本語の文字列でも計算できますか?
A. できます。1文字ずつ比べるので、漢字・ひらがな・カタカナもそのまま扱えます。読みが同じでも表記が違えば別の文字になります。
Q. 類似度はどのように計算していますか?
A. 1 − 編集距離 ÷ 長いほうの文字数 で計算しています。完全一致なら1、すべての文字を変える必要があれば0になります。
