Düzenleme mesafesi (Levenshtein mesafesi)

Telefonunuza recieve yazınca size receive önerir. Yakın olduğunuzu bilir, çünkü iki kelime arasında yalnızca birkaç düzenleme fark vardır. Bu yakınlığı, yani düzenleme mesafesini ölçmek, dinamik programlamanın klasik işlerinden biridir.

Kenarında yukarıdan aşağıya bir kelime, üst kenarında başka bir kelime, hücrelerinde sayılar ve sol üst köşeden sağ alt köşeye uzanan turuncu bir düzenleme yolu bulunan bir tablo
Kenarında yukarıdan aşağıya bir kelime, üst kenarında başka bir kelime, hücrelerinde sayılar ve sol üst köşeden sağ alt köşeye uzanan turuncu bir düzenleme yolu bulunan bir tablo

Problem

Bir düzenleme, bir kelimeyi tek bir harf kadar değiştirir: bir harf eklemek, bir harf silmek ya da bir harfi başka bir harfle değiştirmek. İki kelime arasındaki düzenleme mesafesi, birini diğerine dönüştüren en az düzenleme sayısıdır. cat ile cut arasındaki mesafe 1, cat ile cast arasındaki 1, cat ile act arasındaki ise 2'dir. Buna, 1965'te bu konuyu inceleyen Sovyet matematikçi Vladimir Levenshtein'ın adıyla Levenshtein mesafesi de denir.

Tablo

d[i][j], bir kelimenin ilk i harfi ile diğer kelimenin ilk j harfi arasındaki düzenleme mesafesi olsun. Bir kelimeyi hiçliğe dönüştürmek her harf için bir silme gerektirir, yani d[i][0] = i; bir kelimeyi sıfırdan oluşturmak her harf için bir ekleme gerektirir, yani d[0][j] = j. i. harf j. harfe eşitse d[i][j] = d[i − 1][j − 1] olur. Aksi hâlde d[i][j] = 1 + d[i − 1][j − 1] (değiştirme), d[i − 1][j] (silme) ve d[i][j − 1] (ekleme) değerlerinin en küçüğüdür.

Bir örnek

Tablo, kitten ve sitting için 7 satır ve 8 sütundan oluşur. Sağ alt hücre 3'tür ve oradan geriye doğru okumak şunu verir: k yerine s koy, i, t ve t harflerini koru, e yerine i koy, n harfini koru ve g ekle. Kitten, sitten, sittin, sitting: üç düzenleme; tablo daha kısa bir liste olmadığını kanıtlar.

Düzenlemeleri geriye doğru okumak

Sağ alt hücreden başlayın ve değerinin hangi komşudan geldiğini sorun. Harfler eşleşiyor ve hücre sol üst komşusuna eşitse harf korunmuştur: çapraz adım atın. Sol üst komşudan bir fazlaysa bu bir değiştirmedir; üstteki hücreden bir fazlaysa silme, soldaki hücreden bir fazlaysa eklemedir. Birkaç yol eşit çıkabilir ve her biri en kısa bir düzenleme listesi verir.

Tarihçe ve kullanım alanları

Levenshtein bu mesafeyi 1965'te hata düzelten kodlar üzerinde çalışırken tanıttı. Tablo yöntemi birkaç kişi tarafından yayımlandı; en bilineni 1974'te Robert Wagner ve Michael Fischer'ın yayımladığıdır, bu yüzden yönteme genellikle Wagner–Fischer algoritması denir. Bugün düzenleme mesafeleri yazım önerilerini sıralar, veri tabanlarında yazım hatası içeren isimleri eşleştirir, DNA ve protein dizilerini karşılaştırır ve konuşma tanımayı puanlar.

Kendiniz keşfedin

Uygulamayı açın ve Adım'a basın. Karşılaştırılan iki harf başlıklarda yanar; harfler aynıysa sol üst çaprazdaki mavi hücre kopyalanır, farklıysa üç mavi komşunun hepsine bakılır ve en küçüğüne bir eklenir. Sonunda turuncu yol köşeden geriye doğru ilerler ve düzenlemeler tablonun altında görünür.

Sık sorulan sorular

Düzenleme mesafesi bir metrik midir?

Evet. Hiçbir zaman negatif değildir, yalnızca eşit kelimeler için 0'dır, iki yönde de aynıdır ve üçüncü bir kelimeden geçmek onu asla kısaltamaz: d(a, c) ≤ d(a, b) + d(b, c). Bu da onu yakın eşleşmeleri aramak için kullanışlı kılar.

Damerau–Levenshtein mesafesi nedir?

Fazladan bir düzenleme türü içeren düzenleme mesafesidir: komşu iki harfin yer değiştirmesi. Frederick Damerau 1964'te ekleme, silme, değiştirme ve yer değiştirmenin birlikte yazım hatalarının %80'inden fazlasını kapsadığını buldu. Yer değiştirmeyle recieve ile receive arasındaki mesafe 2 yerine 1 olur.

Düzenleme mesafesi O(m·n)'den daha hızlı hesaplanabilir mi?

Pek değil. 2015'te Arturs Backurs ve Piotr Indyk, bir ε > 0 için O(n^(2 − ε)) zaman alan bir yöntemin, araştırmacıların çoğunun doğru olduğuna inandığı güçlü üstel zaman hipotezini çürüteceğini gösterdi. Yine de birbirine yakın kelimeler için tablonun köşegeni çevresindeki dar bir şerit yeterlidir.

Düzenleme mesafesi DNA karşılaştırmasında nasıl kullanılır?

Biyologlar aynı tabloyu sayılar yerine puanlarla kullanır: eşleşmeler puan kazandırır, değiştirmeler ve boşluklar ise harflere bağlı olarak puan kaybettirir. Bu, bütün diziler için 1970 tarihli Needleman–Wunsch algoritması, en iyi eşleşen parçalar için ise 1981 tarihli Smith–Waterman algoritmasıdır.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Düzenleme mesafesini deneyin