Levenshtein Mesafesi algoritması, iki kelimenin birbirine dönüşümü için minimum ne kadar işlem yapılması gerektiğini hesaplayan bir algoritmadır. Hatalı kelimeleri veya birbirine yakın bilgilere sahip verileri bu algoritma ile ortaya çıkarabiliriz. Bu yazı içerisinde vereceğim örnekler ile neyden bahsettiğimi daha detaylı anlatmaya çalışacağım.
Nerelerde Kullanılır?
Levenshtein Mesafesi kullanım alanları için birçok örnek verebiliriz:
- Form doğrulama: Ad, soyad gibi alanlarda olası yazım hatalarını yakalayabilir.
- Veri temizliği: Veri tabanındaki benzer kayıtları gruplayabilir. Örn: benzer üyelik tespiti gibi.
- OCR sonrası düzeltme: Görüntüden alınan metindeki hataların belirlenmesinde kullanılabilir.
- Arama motorları: Hatalı yazılmış sorgulara öneriler sunar.
Nasıl Hesaplanır ve Örnekler
Levenshtein algoritması, dinamik programlama kullanır. Her iki string’e ait karakterler bir matrisin satır ve sütunlarına yerleştirilir. Bu matrisin her hücresinde, iki kelimenin o ana kadar olan kısmı arasındaki minimum dönüşüm maliyeti hesaplanır.
1.Örnek: Sarı ile renklendirdiğim alandaki minimum değer alınır, “s” ve “t” birbirinden farklı karakterler ise minimum değere 1 eklenerek, kesişen hücreye yazılır. Bu örneğin ilk adımı için hesaplarsak, minimum değerimiz sıfır olacak, “s” ve “t” birbirinden farklı olduğu için +1 yaptığımızda yeni hücreye yazacağımız değer 0+1 = 1 olacaktır. Aynı işlemi bir sağa geçerek yaptığımızda tabloda göründüğü gibi 2 sayısını elde ediyoruz. Hesaplama algoritmasını diğer hücreler içinde aynı şekilde uygulandığında 1.Örnek için bulacağımız sayı 4 olacaktır. Yani “shine” ve “train” kelimeleri arasındaki dönüşüm için minimum 4 işleme ihtiyaç var demektir.
2.Örnek: İlk örnekte bahsettiğim gibi, algoritmayı bu örnek için de uyguladığımızda minimum işlem sayısını 3 olarak buluruz.
Özet
Levenshtein Mesafesi, basit ama güçlü bir metin benzerliği algoritmasıdır. Hatalı girişleri yakalamak, öneriler sunmak veya veri temizliği yapmak isterseniz alternatif olarak bu algoritmadan faydalanabilirsiniz. Bu algoritma Elasticsearch ‘de de kullanılıyor, yakın zamanda bununla ilgili bir yazı da paylaşacağım.
Yeni bir yazıda görüşmek üzere 🙂
