文字列の類似度を表す距離の話

公開日：2025/11/12

技術ノウハウ・Tips

はじめに

2つの文字列があり、それらがどれだけ似ているかを表す値のことを「距離」といいます。
なぜ「距離」というのか？→ ”自然言語処理分野では，類似度のことを距離と呼ぶ場面がしばしば見られる”とのこと。
・2対象が似ている　＝距離が近い
・2対象が似ていない＝距離が遠い
※「距離」とは言わない場合もあります。

類似度を測る代表的な「距離」手法

距離名	特徴・用途
レーベンシュタイン距離 (Levenshtein distance)	文字列変換に必要な「編集操作（挿入・削除・置換）」の最小回数。
ダメラウ・レーベンシュタイン距離	レーベンシュタイン距離に「隣接文字の入れ替え」操作を追加したもの。
ジャロ・ウィンクラー距離 (Jaro-Winkler distance)	文字の位置関係を考慮して類似度を測る
ハミング距離 (Hamming distance)	固定長バイナリ列の誤り数を測定
N-gram	文字列を N 文字ずつ区切った部分列の出現頻度を比較し、文章全体の類似度をざっくり見る。
ユークリッド距離 / コサイン類似度	文章やユーザー行動をベクトル化して、ベクトル間の距離・角度を比較する。

ここでは「レーベンシュタイン距離」と「ジャロ・ウィンクラー距離」を紹介します。

✏️ レーベンシュタイン距離（Levenshtein distance）

🔍 概要

・一方の文字列をもう一方に変換するための操作回数（＝編集距離）のうち最小の回数。
・操作は「挿入・削除・置換」の3つ。
・0：完全一致
・最大値：長い方の文字列の長さ（全く異なる文字列の場合）
👉 距離は文字列が長いほど大きくなるため、**標準化（距離 ÷ 長い方の文字数）**して比較することが多いです（0〜1 の範囲になる）。

🧪 手計算の例

「からあげ」と「かけうどん」のレーベンシュタイン距離 → 4

操作回数	操作内容	1文字目	2文字目	3文字目	4文字目	5文字目
初期	変換前	か	ら	あ	げ
1	2文字目を置換	か	け	あ	げ
2	3文字目を置換	か	け	う	げ
3	4文字目を置換	か	け	う	ど
4	5文字目を挿入	か	け	う	ど	ん

🧑‍💻 プログラム的な計算（動的計画法）

1. 以下のような表を用意します。縦軸に空白文字＋文字列1、横軸に空白文字＋文字列2を1文字ずつ入れ、それぞれ番号を振ります。

	□	か	け	う	ど	ん
□	0	1	2	3	4	5
か	1
ら	2
あ	3
げ	4

2. 各マスには、以下の3つの中で一番小さい数字を入れます。
・上のマス + 1
・左のマス + 1
・左上のマス + c
・文字が同じなら c = 0
・違うなら c = 1

	□	か	け	う	ど	ん
□	0	1	2	3	4	5
か	1	0	1	2	3	4
ら	2	1	1	2	3	4
あ	3	2	2	2	3	4
げ	4	3	3	3	3	4

3. 右下端の数字が、求めるレーベンシュタイン距離となります。

🧰 応用分野

・✅ スペルチェッカー
・✅ 表記ゆれの検出
・✅ 類似研究論文の検索や盗用検知
・文章を形態素解析し、形態素の並びの類似度（距離）に基づいて類似文章を検索
・✅ DNA 配列分析
※ パラメータを変えたり制限を設けるなどし、それぞれの用途に合うよう改良したものを使用します。

🔍 ジャロ・ウィンクラー距離（Jaro-Winkler distance）

✨ 概要

「文字列が近い」ことを、より人間の感覚に近い結果になるようにしたアルゴリズム
・一定の範囲内に置換できる文字が存在するかどうかを加味
・結果は 0～1（1 は一致）。

「ジャロ距離」を計算した後、「ジャロ・ウィンクラー距離」を計算します。

ジャロ距離：𝛷=𝑤_1⋅𝑐/𝑑+𝑤_2⋅𝑐/𝑟+𝑤_𝑡⋅(𝑐−"τ" )/𝑐
ただし，c = 0 で Φ = 0 とする．

・W1：最初の文字列の文字に掛かる重み
・W2：２番目の文字列中の文字に掛かる重み
・Wt：置き換えに掛かる重み
・d：最初の文字列の長さ
・r：２番目の文字列の長さ
・τ：文字の「置換」の数/2
・c：区間内で一致する文字の数（順番は関係ない）
実際は，W1, W2, Wt には 1/3 がセットされる．

ジャロ・ウィンクラー距離：Φ_n=Φ+i・0.1・(1−Φ)
※i は最大4：日本語なら2程度？
※但し、i は先頭からの一致する文字数、0.1は重み
※「先頭から何文字かは正しいはず」を加味

📊 計算例

【技術解説】似ている文字列がわかる！レーベンシュタイン距離とジャロ・ウィンクラー距離の計算方法とはの記事が詳しいです。

📊 レーベンシュタイン距離とジャロ・ウィンクラー距離の結果比較

文字列1	文字列2	レーベンシュタイン距離	1 - レーベンシュタイン標準化	ジャロ・ウィンクラー距離
からあげ	かけうどん	4	0.200	0.796
あおだいしょう	はだかのたいしょう	4	0.444	0.782
うわてなげ	したてなげ	2	0.600	0.880
twitter	twincle	4	0.429	0.800
0752542998	0752223111	6	0.400	0.800
京都市中京区車屋町通竹屋町上る砂金町	京都市中京区御池通河原町西入ル上本能寺前町	11	0.476	0.794
シミュレーション	シュミレーション	2	0.750	0.985
愛敬を振りまく	愛想を振りまく	1	0.857	0.924
Michael Jackson	Magic Johnson	9	0.400	0.711
マイケル・ジャクソン	マジック・ジョンソン	5	0.667	0.863
河原の道を自転車で走る君を追いかけた	河原の道を走る君を自転車で追いかけた	8	0.556	0.961
時間は夢を裏切らない夢も時間を裏切ってはならない	夢は時間を裏切らない時間も夢を決して裏切らない	13	0.458	0.835
三度目の正直	七転び八起き	6	0.000	0.550

※ジャロ・ウィンクラー距離は、Oracle の UTL_MATCH.JARO_WINKLER を使用して計測。
全体的に、レーベンシュタイン標準化よりも、ジャロ・ウィンクラー距離のほうが実感値に近いようです。とはいっても、以下の面で実感値から離れてしまいますね。
・「だ」「た」のように見た目が近いものも全く異なる文字と扱われる
・（この表には表現できていないが）「高」「髙」のような異体字も全く異なる文字として扱われる
・発音が近いかどうかも加味されない
アルファベット言語圏なら上記もアルゴリズムに入れやすそうですが、日本語など漢字圏は該当する文字が多すぎて、アルゴリズム化が難しそうです。

言語	ライブラリ等	メモ
Java	apache commons の StringUtils 内	getLevenshteinDistance, getJaroWinklerDistance 他、apache lucene にもある（あった？）
PHP	levenshtein()	標準（>=4.0.1）挿入、置換、削除のコストをそれぞれ定義できる。 Jaro-winkler は pg_similarity 拡張（非公式）が必要。
Oracle	UTL_MATCH パッケージ	標準でついている UTL_MATCH.EDIT_DISTANCE は、挿入コストが 2。
PostgreSQL	levenshtein	fuzzystrmatch 拡張。jaro-winkler はない？ pg_trgm 拡張に、n-gram 系関数あり。
Python	PyPI に editdistance, python-Levenshtein, jaro-winkler 等
JavaScript	Node.jsで js-levenshtein, fast-levenshtein, jaro-winkler 等

最後に

実感値としてはジャロ・ウィンクラー距離が近いですが、それでも日本語圏で適用しようとすると、なかなか実用には難しい気もしました（仕事で使うか検討したことはあるが、採用したことはないです）。電話番号などの入力ミスの検知には使えるかもしれません（でも個人情報の取り扱い上これも難しいか）。
一方、git CLI でコマンドを打ち間違いしたときに、 `The most similar commands are` とサジェストしてくれる機能は、レーベンシュタイン距離を使っているようです。
https://github.com/git/git/blob/821f583da6d30a84249f75f33501504d597bc16b/help.c#L670-L698