Levenshtein Mesafesi ile arama sonuçlarını iyileştirme

Google aramalarıyla hayatımıza giren şeylerden bir tanesi de "Bunu mu demek istediniz?" ifadesidir. Kulağa ne kadar da kullanıcı dostu ve olağan bir bir fonksiyon gibi geliyor değil mi? Ama işi aslı pek de öyle değil. Atla deve değil ya canım misalindeki atla deve tam olarak bu arama optimizasyonundaki iyileştirmeler oluyor. Google'ın tam olarak nasıl bir algroitma kullandığı -bildiğim kadarıyla- ticari sır olarak saklansa da, bu işe yarayabilecek yöntemlerden birisi olan Levenshtein algoritmasından bahsetmek istiyorum.

Levenshtein Mesafesi ile iki kelime arasında ekleme, çıkarma, düzenleme yapmak için gerekli olan mesafeyi bir matrise dönüştürüp, en kısa yolu bulmak için kullanılmakta. Adını da Sovyet matematikçi Vladimi Levenshtein'dan alıyor.

Olayın matris hesabına girmeden basit bir şekilde şöyle izah edeyim; kullanıcılarınızın olduğu bir tablo düşünün. Özel bir kütüphane kullanmadan '%$term%' ile elde edebileceğiniz sonuçlar oldukça sınırlıdır. "murt" diye bir arama değişkenitle "Murat"ı bulamazsınız. Haliyle kullanıcının girişlerine toleranssız bir sonuç elde edersiniz ki çoğu zaman bu istenen bir şey değil. Elbette birebir arama terimiyle örtüşen sonuçlara da ihtiyaç duyacağınız durumlar olabilir, ama genel hatlarıyla bir nevi tolerans mekanizmasına ihtiyacınız olur. İşte bu noktada Levenshtein Mesafesini kullanmak birçok problemi çözebilir.

Giriş yapılan terimi -ki bizim örneğimiz murt- bir matrise çevirdikten sonra aramanın yapılacağı kolon verileri de bir matrise çevirip, bunlar arasındaki öğelerin (harflerin) iki boyutlu olarak olması gereken haline olan uzaklığını değerlendirip durduk yere kullanıcıya "sonuç bulunamadı" sayfasını göstermemiş olursunuz. Kullanıcı "murt" ifadesini arattığında her ne kadar "murat" yazmak istemiş olsa da sonuçlar arasında "Mert"i de görecektir ki yapılan yazım hatasına göre oldukça makul bir öneri olarak değerlendirebiliriz. Hatta Mert sonucu Murat'tan önce bile görüntülenebilir ama kullanıcı istediğini almış oluyor.

Bunu MySQL için kullanıcı tanımlı bir fonksiyon (UDF) olarak ekleyip, sorgularımızda kullanmamız mümkün. Sağladığı avantajların yanısıra sunucuya getireceği yükü de hatırlatarak kodu sizinle paylaşayım:

create
    definer = root@localhost function levenshtein(s1 varchar(255), s2 varchar(255)) returns int deterministic
BEGIN
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
    DECLARE s1_char CHAR;
-- max strlen=255
    DECLARE cv0, cv1 VARBINARY(256);
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;
    IF s1 = s2 THEN
        RETURN 0;
    ELSEIF s1_len = 0 THEN
        RETURN s2_len;
    ELSEIF s2_len = 0 THEN
        RETURN s1_len;
    ELSE
        WHILE j <= s2_len DO
                SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
            END WHILE;
        WHILE i <= s1_len DO
                SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1;
                WHILE j <= s2_len DO
                        SET c = c + 1;
                        IF s1_char = SUBSTRING(s2, j, 1) THEN
                            SET cost = 0; ELSE SET cost = 1;
                        END IF;
                        SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
                        IF c > c_temp THEN SET c = c_temp; END IF;
                        SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
                        IF c > c_temp THEN
                            SET c = c_temp;
                        END IF;
                        SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
                    END WHILE;
                SET cv1 = cv0, i = i + 1;
            END WHILE;
    END IF;

    RETURN c;

END;

 Yukarıdaki kodu direkt bir SQL sorgusu olarak çalıştırırsanız, kullandığınız veritabanı için bir UDF olarak veritabanına eklenir ve bu aşamadan sonra  levenshtein(s1 varchar(255), s2 varchar(255)) kullanımınıza hazır hale gelmekte. Yalnız dikkat ederseniz, sonuç bir integer olarak döndürülecektir. O integer da yapılan sorgunun varolan veriye oluşturulan matrise göre uzaklığını ifade ediyor.

Bu uzaklığı Laravel'de (Laravel olması şart değil, ben orada kullandığım için örneği Eloquent üzerinden vermek istiyorum, yoksa istediğiniz her platformda kullanabilirsiniz) arama sonuçlarını alıp, mesafeye göre sıralamak mümkün.

Örneğin bir request ile arama terimi olan term'i aldığımızı varsayalım.

            $results = User::selectRaw('id, surname, email, name, levenshtein(name, ?) AS name_distance', [$this->term]) // 'murt' aramasına göre isim ve Levenshtein mesafesini seçtik
                ->orderBy('name_distance', 'asc') // Mesafeye göre artan sırada sırala
                ->limit(5) // İlk 5 sonucu al
                ->get(); // Kullanıcı modellerinin koleksiyonunu döndür

Veritabanı tablomuzdan 'id, name, surname, email' ile birlikte dikkat ederseniz ham sorgu içinde levenstein() fonksiyonunu çağırabiliyoruz çünkü artık MySQL ne yapmak istediğimizi biliyor. Birden çok alanda bunu yapma ihtimaliniz için name ile örneklendirip sorgumuzu bir array içine aldım ki projenizde eklemek istediğinzi başka alanlar için de kolaylıkla arama kriterlerinizi genişletebilesiniz. Blade içinde bu sonuçları alıp istediğiniz kullanabilirsiniz. Belki canlı aramalar için de kullanırsınız. Bundan sonrası size kalmış.

Yalnız şunu tekrar hatırlatmak istiyorum, bu fonsiyonu her çağırdığınızda yukarıda verdiğim kod katarını seçmiş olduğunuz tablo içinde koşacağı için sunucuya getireceği muhtemek yükü iyi düşünün. Gerçekte böyle bir fonksiyona ihtiyacanız varsa ve donanımınız da yeterince güçlüyse, kod sizin, sunucu sizin, klavye sizin.