レーベンシュタイン距離 (編集距離) とは、一方の文字列を他方の文字列に変換するために必要な、文字の挿入・削除・置換の最小操作回数です。1965 年にロシアの数学者ウラジーミル・レーベンシュタインが提唱しました。

例えば「kitten」と「sitting」のレーベンシュタイン距離は 3 です (k→s、e→i、n の後に g を挿入)。この指標はスペルチェック、あいまい検索、DNA 配列比較などに広く応用されています。文字列アルゴリズムの書籍で計算方法を学べます。

計算には動的計画法 (DP) を使用し、時間計算量は O(mn) (m, n は各文字列の長さ) です。大規模なデータセットでは近似アルゴリズムが使われることもあります。

文字数カウントの観点では、レーベンシュタイン距離は 2 つのテキストの類似度を文字単位で定量化する指標であり、文字数の差異を測る基本的な手法です。自然言語処理基礎の書籍も参考になります。