レーベンシュタイン距離
実際的な距離の求め方を例示すれば、「kitten」を「sitting」に変形する場合には、以下に示すように最低でも 3 回の手順が必要とされるので、2単語間のレーベンシュタイン距離は 3 となる。
「kitten」
「sitten」(「k」を「s」に置換)
「sittin」(「e」を「i」に置換)
「sitting」(「g」を挿入して終了)
上の変形では挿入・削除・置換のそれぞれのコストを1に設定したが、これらのコストには別々の値を割り振る事も可能である。例を挙げれば、挿入・削除のみを許可し、置換を禁止するタイプのレーベンシュタイン距離は、挿入・削除にコスト1、置換にコスト2が割り振られるレーベンシュタイン距離と等価である。この場合、「kitten」と「sitting」の間のレーベンシュタイン距離は5となる。