文字列類似度計算機

Levenshtein距離（編集距離）は、1つの文字列を別の文字列に変換するために必要な最小の単一文字編集数です。3つの許可された操作は：挿入（文字を追加）、削除（文字を削除）、置換（1文字を別の文字に置き換える）です。例：「kitten」→「sitting」は3つの操作が必要：k→s、e→i、+g。1965年にこのアルゴリズムを説明したVladimir Levenshteinにちなんで命名されました。

類似度% = (1 − 編集距離 / max(len1, len2)) × 100。これにより最長文字列に対して距離が正規化されます。例：距離=2、最大長=8 → 類似度=(1−2/8)×100=75%。距離0は同一文字列（100%類似）を意味します。他の類似度指標にはJaro-Winkler（最初の文字の一致をより重視）とコサイン類似度があります。

Damerau-Levenshteinは第4の操作：転置（隣接する2文字を入れ替える）を追加することでLevenshteinを拡張します。例：「ab」→「ba」はLevenshtein距離2ですがDamerau-Levenshtein距離1（1つの転置）です。これはスペルチェックで重要です（「teh」→「the」）。このツールは標準Levenshtein（転置なし）を使用します。

スペルチェッカー：誤字から低い編集距離の単語を提案。DNA配列決定：変異と挿入を見つけるためにヌクレオチド配列を整列。バージョン管理：git diffは行レベルの変更を表示するために編集距離アルゴリズムを使用。不正検出：名前のバリエーションの検出（タイポスクワッティング、本人確認詐欺）。

Wagner-Fischerアルゴリズムは動的プログラミングを使用してLevenshtein距離を計算し、時間計算量O(m×n)、空間計算量O(m×n)です（m、nは文字列の長さ）。セル[i][j]が文字列1のi文字目と文字列2のj文字目の間の編集距離となる行列を構築します。空間はO(min(m,n))に最適化できます（2行を使用）。