Levenshtein Uzaklığı
Levenshtein uzaklığı, bir karakter dizisini (string) başka bir karakter dizisine dönüştürmek için gereken en az işlem sayısını ölçen bir yöntemdir. Bu hesaplamada üç temel işlem dikkate alınır:
- Karakter ekleme
- Karakter silme
- Bir karakteri başka bir karakterle değiştirme
Levenshtein uzaklığı, özellikle yazım denetimi sistemleri, arama motorları, doğal dil işleme uygulamaları ve veri eşleştirme işlemlerinde yaygın olarak kullanılır. İki kelime veya metin parçası arasındaki benzerliği sayısal olarak ifade etmeye yardımcı olur.
Örneğin bir yazım denetleyicisi, kullanıcının girdiği hatalı bir kelimeyi sözlükteki kelimelerle karşılaştırırken Levenshtein uzaklığından yararlanabilir. Uzaklık ne kadar küçükse, iki kelimenin birbirine o kadar benzer olduğu kabul edilir.
Levenshtein uzaklığı hesaplanırken bir matris oluşturulur. Bu matrisin her hücresi, bir alt diziyi başka bir alt diziye dönüştürmek için gereken en düşük işlem maliyetini gösterir. Matris adım adım doldurularak iki string arasındaki minimum düzenleme maliyeti elde edilir.
Hamming uzaklığından farklı olarak, Levenshtein uzaklığı farklı uzunluklardaki string'lere de uygulanabilir. Bu özelliği sayesinde daha geniş bir kullanım alanına sahiptir.
Uygulamalı Bir Örnek
\( s \) ve \( t \) string'lerini ele alalım:
$$ s = "kitten" $$
$$ t = "sitting" $$
Amacımız bu iki sözcük arasındaki Levenshtein uzaklığını bulmaktır. Başka bir ifadeyle, "kitten" sözcüğünü "sitting" sözcüğüne dönüştürmek için gereken en az düzenleme işlemi sayısını hesaplayacağız.
- Değiştirme
İlk adımda \( k \) harfini \( s \) ile değiştiririz: $$ "kitten" \rightarrow "sitten" $$ - Değiştirme
Daha sonra \( e \) harfini \( i \) ile değiştiririz: $$ "sitten" \rightarrow "sittin" $$ - Ekleme
Son olarak kelimenin sonuna \( g \) harfini ekleriz: $$ "sittin" \rightarrow "sitting" $$
Görüldüğü gibi dönüşüm toplam üç işlemle tamamlanmaktadır: iki değiştirme ve bir ekleme. Bu nedenle "kitten" ile "sitting" arasındaki Levenshtein uzaklığı 3'tür.
Bu işlemi sistematik olarak hesaplamak için boyutu \( (m+1) \times (n+1) \) olan bir matris oluşturulur. Burada \( m \), "kitten" sözcüğünün uzunluğunu (6), \( n \) ise "sitting" sözcüğünün uzunluğunu (7) temsil eder.
Matrisin ilk satırı ve ilk sütunu, boş bir string'den bir string'e veya bir string'den boş bir string'e dönüşüm maliyetlerini gösterebilmek için eklenir.
| "" | s | i | t | t | i | n | g | |
|---|---|---|---|---|---|---|---|---|
| "" | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| k | 1 | |||||||
| i | 2 | |||||||
| t | 3 | |||||||
| t | 4 | |||||||
| e | 5 | |||||||
| n | 6 |
\( (0, j) \) hücresi, boş string'i "sitting" sözcüğünün \( j \)'ye kadar olan alt dizisine dönüştürmenin maliyetini gösterir. Bu yüzden ilk satırdaki değerler 0'dan 7'ye kadar düzenli olarak artar.
\( (i, 0) \) hücresi ise "kitten" sözcüğünün \( i \)'ye kadar olan alt dizisini boş string'e dönüştürmenin maliyetini gösterir. Bu durumda da ilk sütundaki değerler 0'dan 6'ya kadar artar.
Her \( (i, j) \) hücresini doldururken üç olasılığı karşılaştırırız:
- "kitten" dizisinden bir karakter silmek. Bu durumda üstteki hücrenin maliyetine \( +1 \) eklenir.
- "kitten" dizisine bir karakter eklemek. Bu durumda soldaki hücrenin maliyetine \( +1 \) eklenir.
- Karakterler farklıysa bir karakteri değiştirmek. Bu durumda çapraz hücrenin maliyetine \( +1 \) eklenir. Karakterler aynıysa çapraz hücredeki değer ek maliyet olmadan alınır.
Bu kurala göre matrisi adım adım dolduralım:
| "" | s | i | t | t | i | n | g | |
|---|---|---|---|---|---|---|---|---|
| "" | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| k | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| i | 2 | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
| t | 3 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
| t | 4 | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
| e | 5 | 5 | 4 | 3 | 2 | 2 | 3 | 4 |
| n | 6 | 6 | 5 | 4 | 3 | 3 | 2 | 3 |
Örneğin boş string'i "s", ardından "si", sonra "sit" gibi daha uzun alt dizilere dönüştürmek için her adımda bir karakter eklenir. Bu nedenle ilk satırdaki maliyet her sütunda 1 artar.
Aynı mantık ilk sütun için de geçerlidir. "k", "ki", "kit" ve devamındaki alt dizileri boş string'e dönüştürmek için her adımda bir karakter silinir. Bu yüzden maliyet her satırda 1 artar.
- \( (1,1) \) hücresi, "k" harfini "s" harfine dönüştürmenin maliyetini gösterir. Bunun için yalnızca bir değiştirme işlemi yeterlidir. Bu nedenle değer 1'dir (\( k \rightarrow s \)).
- \( (2,2) \) hücresi, "ki" dizisini "si" dizisine dönüştürmenin maliyetini gösterir. İkinci karakter zaten aynı olduğu için (\( i \)) ek bir işlem gerekmez ve maliyet 1 olarak kalır.
- \( (3,3) \) hücresi, "kit" dizisini "sit" dizisine dönüştürmenin maliyetini gösterir. Üçüncü karakter de aynı olduğu için (\( t \)) değer yine 1'dir.
- \( (4,4) \) hücresi, "kitt" dizisini "sitt" dizisine dönüştürmenin maliyetini gösterir. Dördüncü karakter de eşleştiği için (\( t \)) maliyet değişmez ve 1 olarak kalır.
- \( (5,5) \) hücresi, "kitte" dizisini "sitti" dizisine dönüştürmenin maliyetini gösterir. Bu kez \( e \) karakterinin \( i \) karakteriyle değiştirilmesi gerekir. Bu nedenle toplam maliyet 2 olur.
- \( (6,6) \) hücresi, "kitten" dizisini "sittin" dizisine dönüştürmenin maliyetini gösterir. Altıncı karakter aynı olduğu için (\( n \)) maliyet 2 olarak kalır.
- \( (6,7) \) hücresi, "kitten" dizisini "sitting" dizisine dönüştürmenin maliyetini gösterir. Son adımda kelimenin sonuna bir \( g \) karakteri eklenir. Böylece maliyet 3'e çıkar.
Bu işlemler tamamlandığında matrisin sağ alt köşesindeki hücreye ulaşılır. Bu hücre, iki string arasındaki toplam minimum dönüşüm maliyetini verir.
Sağ alt köşedeki \( (6,7) \) hücresinde yer alan değer 3'tür. Bu, "kitten" sözcüğünü "sitting" sözcüğüne dönüştürmek için gereken en az işlem sayısının 3 olduğu anlamına gelir.
Sonuç, daha önce sezgisel olarak bulduğumuz değerle aynıdır: 1 değiştirme (\( k \rightarrow s \)), 1 değiştirme (\( e \rightarrow i \)) ve 1 ekleme (\( g \)).
Levenshtein Uzaklığından İndüklenen Topoloji
Levenshtein uzaklığı yalnızca string'ler arasındaki benzerliği ölçmek için kullanılan pratik bir araç değildir. Aynı zamanda string'ler kümesi üzerinde bir metrik uzay yapısı da tanımlar. Bunun nedeni, bir uzaklık fonksiyonunun sağlaması gereken temel metrik özellikleri karşılamasıdır.
- Negatif olmama ve ayırt etme özelliği: İki string \( x \) ve \( y \) arasındaki Levenshtein uzaklığı her zaman sıfır ya da pozitif bir değerdir. Ayrıca \( D_L(x, y) = 0 \) ancak ve ancak \( x = y \) olduğunda mümkündür. Çünkü bir string'i kendisine dönüştürmek için hiçbir işlem gerekmez.
- Simetri: Levenshtein uzaklığı simetriktir. Yani \( D_L(x, y) = D_L(y, x) \). \( x \)'i \( y \)'ye dönüştüren her işlem dizisi, ters yönde de karşılık gelen işlemlerle ifade edilebilir. Ekleme işlemi ters yönde silmeye, silme işlemi ters yönde eklemeye karşılık gelir. Değiştirme işlemi ise iki yönde de uygulanabilir.
- Üçgen eşitsizliği: Levenshtein uzaklığı üçgen eşitsizliğini sağlar. Yani \( D_L(x, z) \leq D_L(x, y) + D_L(y, z) \). Başka bir deyişle, \( x \)'ten doğrudan \( z \)'ye gitmenin maliyeti, \( x \)'ten önce \( y \)'ye, sonra \( y \)'den \( z \)'ye gitmenin toplam maliyetinden büyük olamaz. Çünkü bu iki dönüşüm art arda uygulanarak \( x \)'ten \( z \)'ye geçerli bir dönüşüm elde edilir.
Bu özellikler sayesinde Levenshtein uzaklığı, string'ler üzerinde bir metrik yapı oluşturur.
Bir metrik tanımlandığında, buna bağlı olarak bir indüklenen metrik topoloji de tanımlanabilir. Bu topolojide temel fikir, birbirine Levenshtein uzaklığı bakımından yakın olan string'leri aynı açık kümeler içinde toplamaktır.
Bir \( r \) yarıçapı ve bir \( x \) string'i verildiğinde, merkezi \( x \) olan açık yuvar şu şekilde tanımlanır: \( x \)'e Levenshtein uzaklığı \( r \)'den küçük olan tüm \( y \) string'lerinin kümesi.
$$ B(x, r) = \{ y \mid D_L(x, y) < r \} $$
Bu topolojide açık kümeler, bu açık yuvarların birleşimleriyle elde edilir.
Bu bakış açısı özellikle string'ler arasındaki "yakınlık" kavramının önemli olduğu durumlarda yararlıdır. Örneğin otomatik yazım düzeltmede, yazılan bir sözcüğe Levenshtein uzaklığı küçük olan sözlük sözcükleri olası düzeltmeler olarak önerilebilir.
Bu nedenle Levenshtein uzaklığı, string'leri yalnızca karşılaştırmakla kalmaz; onları bir metrik uzayın elemanları gibi ele almamıza ve aralarındaki yakınlık ilişkisini topolojik açıdan incelememize de olanak sağlar.
Uygulamalı Bir Örnek
Şimdi üç karakterli string'lerden oluşan küçük bir \( X \) kümesini ele alalım:
$$ X = \{"cat", "bat", "cut"\} $$
Bu küme üzerinde, her string'i merkez alarak \( r = 2 \) yarıçaplı açık yuvarlar oluşturalım.
$$ B(x, r) = \{ y \mid D_L(x, y) < r \} $$
Burada \( r = 2 \) seçildiği için, bir açık yuvara yalnızca merkezdeki string'e uzaklığı 2'den küçük olan elemanlar girer. Başka bir ifadeyle, uzaklığı 0 veya 1 olan string'ler açık yuvarın içinde yer alır.
Not: \( r = 2 \) yarıçaplı açık yuvar, merkez string'den en fazla bir düzenleme işlemi uzaklıktaki string'leri içerir. Bunun nedeni açık yuvarlarda sınırın dahil edilmemesidir. Bu nedenle koşul "2'den küçük" olarak yazılır: $$ B(x, 2) = \{ y \mid D_L(x, y) < 2 \} $$ Eğer sınırı da dahil eden kapalı yuvar tanımlanmak istenirse koşul "2'den küçük ya da 2'ye eşit" olur. Bu durumda merkez string'den en fazla 2 düzenleme uzaklığındaki tüm string'ler kümeye dahil edilir: $$ C(x, 2) = \{ y \mid D_L(x, y) \le 2 \} $$
Şimdi \( X \) içindeki her string için \( r = 2 \) yarıçaplı açık yuvarları hesaplayalım:
- Merkezi "cat" olan açık yuvar $$ B("cat", 2) = \{"cat", "bat", "cut"\} $$ Çünkü "cat" sözcüğü kendisine sıfır işlemle, "bat" ve "cut" sözcüklerine ise yalnızca birer karakter değiştirme işlemiyle dönüştürülebilir.
- Merkezi "bat" olan açık yuvar $$ B("bat", 2) = \{"bat", "cat"\} $$ Çünkü "bat" sözcüğü kendisine sıfır işlemle, "cat" sözcüğüne ise bir karakter değiştirme işlemiyle dönüştürülebilir. Buna karşılık "cut" sözcüğüne ulaşmak için iki karakter değiştirme işlemi gerekir. Bu nedenle "cut", \( B("bat", 2) \) içinde yer almaz.
- Merkezi "cut" olan açık yuvar $$ B("cut", 2) = \{"cut", "cat"\} $$ Çünkü "cut" sözcüğü kendisine sıfır işlemle, "cat" sözcüğüne ise bir karakter değiştirme işlemiyle dönüştürülebilir. "bat" sözcüğü ise iki değiştirme işlemi gerektirdiği için bu açık yuvara dahil değildir.
\( B("cat", 2) \), \( B("bat", 2) \) ve \( B("cut", 2) \) kümeleri, \( X \) üzerinde Levenshtein uzaklığından indüklenen metrik topolojinin temel açık yuvarları olarak düşünülebilir.
Bu temel açık yuvarların keyfi birleşimleri alınarak daha büyük açık kümeler elde edilir.
Örneğin \( B("bat", 2) \) ile \( B("cut", 2) \) kümelerinin birleşimini alalım:
$$ B("bat", 2) \cup B("cut", 2) $$
\( B("bat", 2) = \{"bat", "cat"\} \) ve \( B("cut", 2) = \{"cut", "cat"\} \) olduğuna göre:
$$ B("bat", 2) \cup B("cut", 2) = \{"bat", "cat"\} \cup \{"cut", "cat"\} $$
$$ B("bat", 2) \cup B("cut", 2) = \{"cat", "bat", "cut"\} $$
Böylece \( \{"cat", "bat", "cut"\} \) kümesi de bu topolojide açık bir küme olur.
Bu basit örnek, Levenshtein uzaklığının yalnızca iki string arasındaki düzenleme maliyetini vermekle kalmadığını gösterir. Aynı zamanda bir string kümesi üzerinde metrik topoloji kurmaya ve açık kümeleri temel açık yuvarların birleşimleriyle tanımlamaya da olanak tanır.
Aynı yöntem, daha büyük string kümeleri ve farklı yarıçap değerleri için de uygulanabilir.
