Levenshtein Distance algoritması, bizlere iki kelimenin birbirine dönüşümü için ne kadar işlem yapılması gerektiğini veren bir algoritmadır. Örneğin "kitap" ve "katip" kelimelerini ele alalım. "kitap" kelimesini "katip" kelimesine dönüştürmek için yapmamız gereken ilk işlem, 2. sıradaki "i" harfini "a" yapmaktır. Sonra ikinci işlem 4. sıradaki "a" harfini "i" yapmaktır. Yani "kitap" kelimesini "katip" kelimesine dönüştürmek için 2 işlem gerekir. Peki bu algoritma ne işe yarar?
Bu algoritma genelde arama motorlarında,kelime yazım yanlışını tespit eden programlarda kullanılır. Mesela biz Google üzerinde bir kelime ararken karşımıza çıkan "bunu mu demek istediniz?" ile bize gösterilen öneri ifadesi, bu algoritma sonucu tespit edilir. Yani bizim yazdığımız kelime ile Google tabanında bulunan kelimeler karşılaştırılır. Hangi kelime için dönüşüm sayısı az ise, o kelime bize önerilen kelimedir. Yani bu algoritma sonucunda elde ettiğimiz değer ne kadar küçükse, kelimeler birbirine o kadar benzerdir. Tabi sonuç 0 ise, kelimeler aynıdır demek oluyor.
Bu algoritma matrisler üzerinde çalışır. Şimdi örnek iki kelime üzerinde çalışalım. "kitap" ve "katip". Bu durumda önce şu şekilde bir yapı oluşturulur.
Daha sonra, sıra ile satir ve sütun karşılaştırması yapılır. İlk satır ve ilk sütunlar için karşılaştırma yapmamıza gerek yok, çünkü zaten değerler girilmiş. O yüzden 2. harfden itibaren karşılaştırmaya başlayacağız. "kitap" kelimesinin 2. harfi ile "katip" kelimesinin 2. harfini karşılaştıralım.
Gördüğünüz gibi bu harfler eşit değil. Bu durumda kırmızı kutuya yerleştirmemiz gereken sayıyı şu şekilde belirliyoruz. Kırmızı renkli kutunun sol,sol-üst,ve üst kutularındaki değerlere 1 ekleyip en küçük olanı kırmızı kutuya yazıyoruz. Bu durumda bu kutuya 1 yazmamız gerekir. Şimdi "kitap" kelimesinin 2. harfi ile "katip" kelimesinin 3. harfini karşılaştıralım. Bu iki harf de eşit olmadığı için, bir önceki adımı aynen uyguluyoruz. Tablonun son hali bu şekilde.
Şimdi "kitap" kelimesinin 2. harfi ile "katip" kelimesinin 4. harfini karşılaştıralım. Bu iki harf eşit olduğu için, burada yapacağımız işlem farklı. Burada, bu iki harfin kesiştiği kutunun sol-üst tarafında bulunan kutudaki değeri alıyoruz ve kesişim kutusuna koyuyoruz. Tablo bu şekli almış oluyor böylece
Tüm bu işlemleri, satır ve sutunları bitirene kadar yaptığımızda tablomuz şu şekilde olacaktır.
Kırmızı ile işaretlediğim kutu, sonucumuz olacaktır. Yani "kitap" ve "katip" kelimelerini birbirine dönüştürmek için 2 işlem yapmamız gerekiyormuş.
Şimdi bu algoritmanın Java ile uygulanmasını sağlayan kodu vereyim
Bu algoritma genelde arama motorlarında,kelime yazım yanlışını tespit eden programlarda kullanılır. Mesela biz Google üzerinde bir kelime ararken karşımıza çıkan "bunu mu demek istediniz?" ile bize gösterilen öneri ifadesi, bu algoritma sonucu tespit edilir. Yani bizim yazdığımız kelime ile Google tabanında bulunan kelimeler karşılaştırılır. Hangi kelime için dönüşüm sayısı az ise, o kelime bize önerilen kelimedir. Yani bu algoritma sonucunda elde ettiğimiz değer ne kadar küçükse, kelimeler birbirine o kadar benzerdir. Tabi sonuç 0 ise, kelimeler aynıdır demek oluyor.
Bu algoritma matrisler üzerinde çalışır. Şimdi örnek iki kelime üzerinde çalışalım. "kitap" ve "katip". Bu durumda önce şu şekilde bir yapı oluşturulur.
Daha sonra, sıra ile satir ve sütun karşılaştırması yapılır. İlk satır ve ilk sütunlar için karşılaştırma yapmamıza gerek yok, çünkü zaten değerler girilmiş. O yüzden 2. harfden itibaren karşılaştırmaya başlayacağız. "kitap" kelimesinin 2. harfi ile "katip" kelimesinin 2. harfini karşılaştıralım.
Gördüğünüz gibi bu harfler eşit değil. Bu durumda kırmızı kutuya yerleştirmemiz gereken sayıyı şu şekilde belirliyoruz. Kırmızı renkli kutunun sol,sol-üst,ve üst kutularındaki değerlere 1 ekleyip en küçük olanı kırmızı kutuya yazıyoruz. Bu durumda bu kutuya 1 yazmamız gerekir. Şimdi "kitap" kelimesinin 2. harfi ile "katip" kelimesinin 3. harfini karşılaştıralım. Bu iki harf de eşit olmadığı için, bir önceki adımı aynen uyguluyoruz. Tablonun son hali bu şekilde.
Şimdi "kitap" kelimesinin 2. harfi ile "katip" kelimesinin 4. harfini karşılaştıralım. Bu iki harf eşit olduğu için, burada yapacağımız işlem farklı. Burada, bu iki harfin kesiştiği kutunun sol-üst tarafında bulunan kutudaki değeri alıyoruz ve kesişim kutusuna koyuyoruz. Tablo bu şekli almış oluyor böylece
Tüm bu işlemleri, satır ve sutunları bitirene kadar yaptığımızda tablomuz şu şekilde olacaktır.
Kırmızı ile işaretlediğim kutu, sonucumuz olacaktır. Yani "kitap" ve "katip" kelimelerini birbirine dönüştürmek için 2 işlem yapmamız gerekiyormuş.
Şimdi bu algoritmanın Java ile uygulanmasını sağlayan kodu vereyim
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class string { | |
| public static int compare(String kelime1,String kelime2){ | |
| // Levenshtein distance algoritması | |
| // İki string benzerlik oranı karşılaştırması | |
| int[][] dizi = new int[kelime1.length()][kelime2.length()]; | |
| for(int i = 0;i<dizi.length;i++){ | |
| dizi[i][0] = i; | |
| } | |
| for(int i = 0;i<dizi[0].length;i++){ | |
| dizi[0][i] = i; | |
| } | |
| for(int i = 1;i<dizi.length;i++){ | |
| for(int j = 1;j<dizi[i].length;j++){ | |
| if(kelime1.charAt(i) == kelime2.charAt(j)){ | |
| dizi[i][j] = dizi[i-1][j-1]; | |
| }else{ | |
| dizi[i][j] = Math.min(dizi[i-1][j]+1,Math.min(dizi[i][j-1]+1,dizi[i-1][j-1]+1)); | |
| } | |
| } | |
| } | |
| return dizi[kelime1.length()-1][kelime2.length()-1]; | |
| } | |
| public static void main(String[] args) { | |
| int sonuc = compare("kitap","katip"); | |
| System.out.println("Sonuc: "+sonuc); | |
| } | |
| } |
Yorumlar
Yorum Gönder