レーベンシュタイン距離（レーベンシュタインきょり、）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される。名称は、1965年にこれを考案したロシアの学者 () にちなむ。レーベンシュタイン距離は、同じ文字数の単語に対する置換編集に使われているハミング距離の一般化であると見なすことが可能である。レーベンシュタイン距離の更なる一般化として、例えば一回の操作で二文字を変換する等の方法が考えられる。実際的な距離の求め方を例示すれば、「codice_1」を「codice_2」に変形する場合には、以下に示すように最低でも 3 回の手順が必要とされるので、2単語間のレーベンシュタイン距離は 3 となる。上の変形では挿入・削除・置換のそれぞれのコストを1に設定したが、これらのコストには別々の値を割り振る事も可能である。例を挙げれば、挿入・削除のみを許可し、置換を禁止するタイプのレーベンシュタイン距離は、挿入・削除にコスト1、置換にコスト2が割り振られるレーベンシュタイン距離と等価である。この場合、「codice_1」と「codice_2」の間のレーベンシュタイン距離は5となる。レーベンシュタイン距離を計算するためには、一般的に動的計画法によるアルゴリズムが用いられている。長さ formula_1 と長さ formula_2 の文字列間の距離を求めるには formula_3 の二次元行列が使われ、計算時間は formula_4 と非常に効率がよい。このアルゴリズムの要諦は、の2点から帰納的に求めることができるという点である。以下に、文字数 lenStr1 の文字列 str1 と、文字数 lenStr2 の 文字列 str2 間のレーベンシュタイン距離を求める擬似コードを示す。スペルチェッカー等において、二つの文字列がどの程度に類似しているかを具体的な値として示す一つの方法である。さらなる応用として注目を浴びつつあるのがバイオインフォマティクス分野での活用であり、DNA配列同士の類似性を判断するために応用されている。これはDNAが挿入・欠失・置換の3様式によって変化していくことの反映である。異なる生物種が持つ同様の遺伝子を同定したり、またそれらの距離を測ることで種が分岐してから経過した時間を推定するなどを実現している。Bitapアルゴリズムが、レーベンシュタイン距離がある値以下のパターンを検出するアルゴリズムとして知られている。agrepという実装がある。

出典:wikipedia