Levenshtein Mesafesi
Levenshtein Distance Metric · Ayrıca şöyle bilinir: edit distance, Damerau-Levenshtein distance
Levenshtein mesafesi, aynı zamanda düzenleme mesafesi olarak da adlandırılır, bir dizeyi diğerine dönüştürmek için gereken tek karakterli düzenlemelerin (ekleme, silme, değiştirme) minimum sayısını ölçer. Vladimir Levenshtein tarafından 1966'da tanıtılan bu metrik, gerçek bir metriktir (tüm mesafe özelliklerini sağlar) ve hesaplamalı dilbilim, yazım denetimi, DNA dizisi karşılaştırması ve kayıt eşleştirme alanlarında temeldir. 0 (özdeş dizeler) ile daha uzun dizenin uzunluğu arasında değişir.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
Ne zaman kullanılır
Levenshtein mesafesi, düzenlemelerin anlamlı işlemler olduğu dizeleri veya ayrık sembol dizilerini karşılaştırmak için idealdir: yazım denetimi, ad eşleştirme, DNA dizisi karşılaştırması ve yaklaşık dize eşleştirme. Gerçek bir metrik gerektiğinde ve O(n*m) hesaplamayı tolere edebildiğinizde kullanın. Uzun dizeler veya çok sayıda karşılaştırma için yaklaşımları veya özel algoritmaları (örneğin, indeksleme için BK-ağaçları) düşünün.
Güçlü yönler & sınırlılıklar
- Gerçek metrik: üçgen eşitsizliği dahil tüm mesafe aksiyomlarını sağlar
- Sezgisel işlem semantiği: eklemeler, çıkarmalar, değiştirmeler anlamlı düzenlemelerdir
- NLP, biyoinformatik ve kayıt eşleştirmede iyi kurulmuş ve yaygın olarak kullanılmaktadır
- Varyantlar (Damerau-Levenshtein, ağırlıklı düzenleme mesafesi) işlevselliği genişletir
- Hesaplamalı olarak pahalı: n ve m uzunluğundaki dizeler için O(n*m) zaman ve alan
- Fonetik veya anlamsal benzerliği hesaba katmaz; tüm değiştirmeleri eşit şekilde ele alır
- Sürekli veriler için uygun değildir; ayrık, sembol tabanlı veriler gerektirir
- Tek bir büyük uyumsuzluktan ziyade birçok küçük uyumsuzluktan etkilenebilir
SSS
Levenshtein ve Hamming mesafesi arasındaki fark nedir?
Hamming mesafesi yalnızca eşit uzunluktaki dizelerde çalışır ve farklı pozisyonların sayısını sayar. Levenshtein mesafesi herhangi bir uzunluktaki dizelerde çalışır ve minimum düzenleme işlemlerini (eklemeler, çıkarmalar, değiştirmeler) sayar. Levenshtein daha geneldir.
Levenshtein mesafesi büyük/küçük harfe duyarlı mıdır?
Varsayılan olarak evet. 'Kedi' ve 'kedi' kelimelerinin Levenshtein mesafesi 1'dir (bir değiştirme). Büyük/küçük harfe duyarsızlık isteniyorsa karşılaştırmadan önce büyük/küçük harfi normalleştirin.
Farklı düzenleme işlemleri için özel maliyetler kullanabilir miyim?
Evet. Ağırlıklı (veya kısıtlı) düzenleme mesafesi, eklemeler, çıkarmalar ve değiştirmeler için farklı maliyetlere izin verir. Alanlara özgü mesafe hesaplamaları için bu maliyetleri dinamik programlama matrisi hesaplamasında belirtin.
Uzun diziler için Levenshtein mesafesini nasıl optimize ederim?
Alandan tasarruf sağlayan uygulamalar kullanın (tam matris yerine yalnızca iki satırı saklayın). Metin içinde arama yapmak için BK-ağaçları veya diğer indeks yapılarını kullanın. Tam mesafeler gerekmiyorsa yaklaşık algoritmaları (örneğin, erken sonlandırmalı yaklaşık eşleştirme) düşünün.
Kaynaklar
- Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 10, 707-710. link ↗
- Damerau, F. J. (1964). A technique for computer detection and correction of spelling errors. Communications of the ACM, 7(3), 171-176. DOI: 10.1145/363958.363994 ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Levenshtein Distance Metric. ScholarGate. https://scholargate.app/tr/decision-making/levenshtein-distance
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Dinamik Zaman BükmeKarar verme↔ karşılaştır