レーベンシュタイン距離
スペルチェッカー等において、二つの文字列がどの程度に類似しているかを具体的な値として示す一つの方法である。さらなる応用として注目を浴びつつあるのがバイオインフォマティクス分野での活用であり、DNA配列同士の類似性を判断するために応用されている。これはDNAが挿入・欠失・置換の3様式によって変化していくことの反映である。異なる生物種が持つ同様の遺伝子を同定したり、またそれらの距離を測ることで種が分岐してから経過した時間を推定するなどを実現している。
Bitapアルゴリズムが、レーベンシュタイン距離がある値以下のパターンを検出するアルゴリズムとして知られている。agrepという実装がある。