Levenshtein Mesafe Hesaplayıcı

Levenshtein Mesafe Hesaplayıcı

Bu örnek, String Tools içindeki Levenshtein mesafesi hesaplamayı gösterir ve klasik “kitten” ile “sitting” karşılaştırmasıyla hazır gelir. İki dize gir ve birini diğerine dönüştürmek için gereken minimum tek karakterlik düzenleme sayısını gör.

Nasıl Çalışır

Levenshtein mesafesi dinamik programlama kullanır. Her hücrenin alt dizeler arasındaki düzenleme mesafesini temsil ettiği bir matris kurulur. Algoritma, her konumda üç işlemi değerlendirerek matrisi doldurur:

Matrisin sağ alt hücresindeki son değer Levenshtein mesafesidir.

“kitten” ile “sitting” Örneği

Klasik örnek 3 düzenleme gerektirir:

1. kitten → sitten (k yerine s koy)
2. sitten → sittin (e yerine i koy)
3. sittin → sitting (sona g ekle)

Mesafe = 3.

Zaman ve Alan Karmaşıklığı

Algoritma O(m x n) zaman ve alanda çalışır; burada m ve n iki dizenin uzunluklarıdır. Çoğu pratik metin karşılaştırmasında (1000 karakter altı) bu işlem tarayıcıda anında tamamlanır.

Varyasyonlar

Birkaç algoritma Levenshtein’i belirli kullanım durumları için değiştirir:

• Damerau-Levenshtein dördüncü işlem olarak transpozisyonu (bitişik karakterleri takas etme) ekler
• Ağırlıklı Levenshtein işlemlere farklı maliyetler atar (örneğin değiştirme, eklemeden pahalıdır)
• kısıtlı düzenleme mesafesi hangi işlemlere izin verildiğini sınırlar

Nasıl Kullanılır

1. İlk dizeyi giriş alanına gir
2. İkinci dizeyi ikinci alana gir
3. Düzenleme mesafesi sonuç alanında görünür
4. Araç ayrıca adım adım dönüşümü gösterir

Sık Sorulan Sorular

Mümkün olan en büyük mesafe nedir?

En büyük mesafe uzun dizenin uzunluğudur; bu, bir dize tamamen boşken her karakteri eklemen gerektiğinde olur. Uzunlukları m ve n olan iki dizede mesafe en fazla max(m, n) olur.

Büyük-küçük harf duyarlılığı sonucu nasıl etkiler?

Karşılaştırma büyük-küçük harfe duyarlıdır. Hello ile hello arasındaki mesafe 1’dir (H/h farkı). Büyük-küçük harf duyarsız karşılaştırma için önce iki dizeyi de küçük harfe çevir.

Bunu DNA dizisi karşılaştırması için kullanabilir miyim?

Evet. Levenshtein mesafesi biyoinformatikte DNA veya protein dizileri arasındaki benzerliği ölçmek için yaygın kullanılır. Her karakter bir nükleotidi veya amino asidi temsil eder; düzenleme mesafesi diziler arasındaki mutasyon sayısını yansıtır.