Levenshtein Mesafe Algoritması (Levenshtein Distance)

Yazan: Yrd. Doç. Dr. Şadi Evren ŞEKER

İki dizilim arasındaki benzerliği derecelendirmek için kullanılır. Pratikte arama sonuçlarında kelimeler arasındaki benzerliği derecelendirmek için kullanılmaktadır.

Basitçe, iki dizi, iki kelime, iki cümle gibi varlıklar arasındaki değiştirme ve ekleme işlemlerini tutar.

Örneğin

• Oyun- Ayan kelimeleri arasındaki mesafe 2 ‘dir çünkü ilk ve ikinci o harfleri a harfi ile deÄŸiÅŸmiÅŸtir.
• Arap – araba kelimeleri arasındaki mesafe 2’dir çünkü p harfi b ile deÄŸiÅŸmiÅŸ ve a harfi eklenmiÅŸtir.

Algoritma değişim değerini bulmak için iki boyutlu bir dizi (matris) üzerinde kelimelerin farklı olan harfleri için değer arttırımına gider.

ÖrneÄŸin karşılaÅŸtıracağımız dizgiler (string) “Cuma” ve “Pazar” kelimeleri olsun.

		C	U	M	A
	0	1	2	3	4
P	1	1	2	3	4
A	2	2	2	3	3
Z	3	3	3	3	4
A	4	4	4	4	3
R	5	5	5	5	4

Yukarıdaki tabloda, yeşil renkle gösterilen satır ve sütun, boş bir dizgi ile kelimenin karşılaştırılmasıdır. Örneğin boş bir kelime ile CUMA kelimesi karşılaştırılınca her har için ekleme yapılacak ve neticede CUMA kelimesinin uzunluğu olan 4 değerine ulaşılacaktır (satırın sonu 4 sayısı ile bitmiştir).

Yeşil satır ve sütunun altında ve sağında kalan alan ise teker teker harflerin karşılaştırıldığı bölümdür.

Örneğin C harfi ile başlayan sütundaki değerler, sadece C harfinden oluşan bir kelimenin PAZAR kelimesi ile karşılaştırılmasını adım adım gösterir. Buna göre M harfiyle başlayan sütundaki karşılaştırma CUM kelimesi ile PAZAR kelimesinin her harfinin karşılaştırılmasıdır. Bu sütundaki değerler (tabloda sarı renktedir) aşağıdaki şekilde okunabilir:

P-CUM : 3 , P harfini C ile değiştirip UM eklendiği için toplam 3 işlem gerekir

PA-CUM: 3, P harfi C ile, A harfi U ile deÄŸiÅŸtikten sonra M harfi eklenmiÅŸtir

PAZ-CUM : 3 , P harfi C ile, A harfi U ile ve Z harfi M ile deÄŸiÅŸmiÅŸtir, toplam maliyet 3’tür.

PAZA-CUM: 4, P harfi C ile, A harfi U ile ve Z harfi M ile deÄŸiÅŸmiÅŸtir, ilave olarak A harfi eklenmiÅŸtir.

PAZAR – CUM: 5, P harfi C ile, A harfi U ile ve Z harfi M ile değişmiştir ilave olarak A ve R harfi eklenmiştir.

Levenshtein mesafesi hesaplanırken, dizideki hesaplanmakta olan hücrenin üstündeki ve solundaki değerlerden faydalanılır. Herhangi bir hücre için aşağıdaki durum geçerlidir:

			Harf1
			…
		A	B
Harf2	…	C	D

D hücresinin değeri, satırdaki ve sütundaki kelimelerin karşılaştırmasını yaparken, Harf1 ve Harf2 harflerini karşılaştırır. Bu karşılaştırmada 3 ihtimal bulunur.

Harf1 ile Harf2 eşittir. Bu durumda D değerine A değeri konulur. Bunun sebebi, A değerinin daha önceki (Harf1 ve Harf2 karşılaştırmasından önceki kelime parçası) mesafeye yeni bir mesafe eklemiyor olmasıdır.

ÖrneÄŸin PARA ve YARA kelimelerini karşılaÅŸtırırken PA ve YA durumunda, Harf1 = Harf2 olur. Bu durumda PA-YA maliyeti 1’dir ve bu maliyet P ile Y nin deÄŸiÅŸmesinden gelen maliyettir, karşılaÅŸtırılan A deÄŸerleri için ilave bir maliyet olmaz.

		P	A
Y		1
A			1

Yukarıdaki tabloda görüldüğü üzere A-A karşılaştırmasının değeri üst çaprazdan okunmuştur.

Åžayet Harf1-Harf2 karşılaÅŸtırma sırasında, harfler birbirinden farklıysa, bu durumda yine çaprazdaki deÄŸer alınır ( yukarıdaki tabloda, D’nin deÄŸeri hesaplanırken A’nın deÄŸeri alınır) ve bu deÄŸere 1 eklenir.

Kısacası kelime boyları aynı olduğu sürece D değerinin hesabında A değeri kullanılır.

Şayet kelime boyları farklıysa, bu durumda Harf1 karşılığı olarak Harf2 bulunamayacak veya Harf2 karşılığı olarak Harf1 bulunamayacaktır. Her iki durum için de daha önceden bulunan ve kelimelerin son harflerinin karşılaştırmasına 1 eklenir.

Şayet Harf2 yok ve Harf1 varsa, bu durumda D değeri B+1 olarak hesaplanır.

Şayet Harf1 yok ve Harf2 varsa, bu durumda D değeri C+1 olarak hesaplanır.

Örneğin AS kelimesi ile ASİ kelimesini karşılaştırmak isteyelim:

		A	S
	0	1	2
A	1	0	1
S	2	1	0
Ä°	3	2	1

Yukarıdaki kırmızı ile gösterilen hücrenin değeri, 1 olarak bulunmuştur. Bunun sebebi değerin bir harf eklemesi ile 0 maliyetli AS-AS karşılaştırmasına yapılması ve hemen üzerinde bulunan hücreden alınarak 1 arttırılmasıdır.

Daha genel anlamda, bir hücrenin değeri hesaplanırken iki ihtimal bulunur.

Karşılaştırılan harfler eşittir ( bu durumda sol çaprazdaki değer kopyalanır)

Harfler farklıdır ( bu durumda, hücrenin solu, üstü ve sol çaprazındaki değerlere 1 eklenerek en küçük olanı alınır. )

Yukarıdaki bu algoritmanın kodlanmış hali aşağıda verilmiştir.

Kodun 5-12. satırları, basit bir şekilde verilen 3 sayıdan en küçüğünü döndüren minimum fonksiyonudur.

41-46. satırlar arasında, fonksiyonumuz olan LevenshteinMesafesini, 4 parametre ile çağırıyoruz. Bunlar sırasıyla, 1. Kelime, 2. Kelime, 1. Kelimenin boyu, 2. kelimenin boyudur.

Burada boyların 1 fazla verilme sebebi, boşluk karakteri ile de yapılacak olan karşılaştırmadandır.

Kodun 16-19. Satırları arasında, matrisimizin ilk satırına ve ilk sütununa (yazının başındaki ilk tabloda yeşil ile gösterilen satır ve sütun) ardışık sayıları döşüyoruz. Bunun anlamı, kelimelerin boş kelime ile karşılaştırılma değerini tutmaktır.

Ardına 20-34. Satırlar arasında ana döngümüz başlıyor ve bu döngüde, kelimelerin her harfi, diğer kelimenin her harfi ile karşılaştırılıyor. Bu karşılaştırma sırasında iki ihtimal bulunuyor, harfler eşittir veya değildir.

Harfler eşitse çaprazdaki değer kopyalanıyor. (bu işlem şu anda hesaplanan d[i][j] değerine d[i-1][j-1] değeri konularak 25. Satırda yapılıyor).

Harfler farklıysa, yukarıda da anlatıldığı üzere, hücrenin üstündeki (d[i][j-1]) solundaki (d[i-1][j]) veya sol çaprazındaki (d[i-1][j-1]) değerlerinden en küçüğüne 1 eklenerek hücreye yazılıyor (d[i][j]).

Sonuçta, matrisin sağ alt köşesindeki değer, iki kelime arasındaki mesafeyi belirliyor ve bu değeri 39. Satırda döndürüyoruz.

Algoritmanın karmaşıklığı, n ve m uzunluğunda iki kelime için, (n+1)x(m+1) işlem gerektirmesidir (+1 değerleri boş kelime ihtimalinden gelmektedir). Bu durumda algoritmanın hem yer hem de zaman karmaşıklığı O(nxm) olarak bulunur.

Kodu indirmek için tıklayınız.