Aslında yazı arama algoritmalarında devam etmek istiyordum ama önce sıradaki algoritmada kullanılan bir teknikle ilgili yazmaya karar verdim. Bu tekniğin adı rolling hash. Rolling hash aslında bir tür hash değeri hesaplama algoritmasıdır. Hash nedir ve yazı aramada hash değeri nasıl işimize yarayabilir?
Hash fonksiyonu, değişken uzunluklu veri kümelerini, sabit uzunluklu veri kümelerine haritalayan algoritma veya alt programdır. Vikipedide verilen tanım bu. Bunu basitçe bir alt metni kullanarak hesapladığımız bir sayı olarak düşünebiliriz.
Bir sonraki metin algoritmasında kısaca metin içinde aradığımız parçanın harflerini tek tek kaydırarak karşılaştırmak yerine ana metinde aradığım alt metinle aynı uzunluktaki parçaların hash değerlerini aradığımız metnin hash değerleriyle karşılaştırmayı deneyeceğim.
Önce metinlerde kullanabileceğim basit bir hash fonksiyonu tanımlamaya çalışayım. Örneğin aradığım metnin harf değerlerini toplamakla başlayabilirim.
Aradığım metin ABC ise harflerin ASCII değerlerini toplamayı düşünebilirim. A = 65, B = 66 ve C = 67 olduğuna göre hash(ABC) = 65 + 66 + 67 = 198 olur. Oldukça kolay olan bu algoritmanın bir dezavantajı var ama. hash(ABC) = hash(CBA) olacaktır. Daha doğrusu basitçe harf değerlerini toplamak aradığım harflerin sırası değiştiğinde de aynı hash değerini hesağlayacağından arama işlemlerinde çok faydalı olmayabilir. Aslında tanıma dikkatli baktığımızda hash değerlerinin farklı harflerden oluşan diziler için de aynı olabileceğini görebiliriz, çünkü bu hash fonksiyonu asla birebir olmayacaktır. Harf dizisi sayısı hesapladığımız sayılardan fazladır, demek ki bazı diziler ne yaparsak yapalım aynı hash değerlerine sahip olacaktır. Yine de elimizden geldiğince bu çakışmaları azaltmakta fayda var.
Harflerin pozisyonlarına göre değişik değerler üretebilmeleri için bu harflerin değerlerini harfin konumuna göre değişik sayılarla çarpıp toplayacağım. Çarptığım sayıları da bir tabanın kuvvetleri olarak seçeceğim. Bu seçim bu yazının konusu olan rolling hash hesabında oldukça faydalı olacak. Bu yazıda bu iş için en uygun sayıların nasıl bulunacağına girmeyeceğim. Sadece kabaca algoritmanın bir simulasyonunu vereceğim. Yazıda ve simulasyonda taban olarak 7 sayısını kullanacağım.
Bu durumda \(hash(ABC) = 65\cdot {7^0} + 66\cdot{7^1} + 67\cdot{7^2} = 65 + 66\cdot{7} + 67\cdot{49} = 65 + 462 + 3283 = 3810 \) olur. Harflerin yerlerini değiştirdiğimde de \(hash(CBA) = 67\cdot {7^0} + 66\cdot{7^1} + 65\cdot{7^2} = 67 + 66\cdot{7} + 65\cdot{49} = 65 + 462 + 3185 = 3714 \) sonucu çıkıyor. Demek ki bu yöntem harf sıralamasındaki değişikliklerde daha iyi bir performans sağlıyor. Tabii ki buna rağmen çakışmalar olabilir ama önemli olan bu ihtimalin azalması.
Ana metin içinde aramayı yaparken aradığımız metin uzunluğundaki parçaların hash değerlerini hesaplamamız gerekecek. İyi de bu hash değerleri metni bir kaydırıp bütün harfleri tek tek karşılaştırmaktan nasıl daha iyi olabilir ki? Her kaydırmadan sonra daha çok çarpma ve toplama yapmamız gerekiyor ve sonuçta zaten hash değerleri aynı çıksa bile çakışma riski nedeniyle iki diziyi yine harf harf karşılaştırmamız gerekecek. Bu yöntemin daha iyi olabilmesi için hash değeri hesaplamayı çok daha kolay bir hale getirmem gerekecek.
Metnimiz ABCD olsun ve aradığımız metin de üç harf uzunluğunda olsun. Kontrol etmemiz gereken iki tane alt dizi olacak. ABC ve BCD. Şimdi bunların hash değerlerine bakalım.
\(hash(ABC) = 65\cdot {7^0} + 66\cdot{7^1} + 67\cdot{7^2} = 65 + 66\cdot{7} + 67\cdot{49} = 65 + 462 + 3283 = 3810 \)
\(hash(BCD) = 66\cdot {7^0} + 67\cdot{7^1} + 68\cdot{7^2} = 66 + 67\cdot{7} + 68\cdot{49} = 66 + 469 + 3332 = 3867 \)
Kaydırma adımına bakarsak ilk diziden A harfi çıkarılıyor ve yerine D harfi ekleniyor. Bu adımı ilk hesaplana hash değeri ile beraber kullanırsak şöyle bir hesaplama çıkarabiliriz. Önce çıkarılan harfin değerini önceki hash değerinden çıkaralım:
\(3810 – 65 = 3745 \)
ABC dizisindeki harfler bir sonraki dizide BC şeklinde bir harf sola kaydığına göre basamak değerleri de ona göre kayacak. İlk hesapta B’nin basamak değeri \(7^1 = 7 \) iken ikinci hesapta basamak değeri \(1 \) olacak. C’nin basamak değeri de ilk hesapta \(7^2 = 49\) iken ikinci hesapta \(7 \) olmakta. Yani kaydırma sırasında düşen harfi çıkardıktan sonra kalan harflerin değerleri öncekinin yedide biri oluyor, yani kalan sayısı 7’ye böleceğim.
\(3745 : 7 = 535 \)
Şimdi yeni hash değerini bulmak için sadece kaydırma sonunda diziye eklenen harfin değerini toplamak kaldı. Yeni eklenen harfin basamak değeri her zaman \(7^2=49 \) olduğundan son işlemimiz
\(535 + 68\cdot49 = 535 + 3332 = 3867\) olur. Bu da normal hesapladığımızda çıkan sonuca eşittir.
Simulasyon linkine geçmeden önce bu algoritmanın istediğimiz performansı vermesi için tabii ki aradığımız metin parçasının uzun olması gerektiğini ekleyeyim. Çünkü her durumda yapılması gereken işlem sayısı aynı. Bir çıkarma, bir bölme, bir çarpma ve bir toplama ve bir kuvvet alma. Bu işlemlerin toplamdaki yükü aranan dizinin boyu uzadıkça azalacaktır. Simulasyona geçmeden önce bir de tanımdaki sabit uzunluklu kısmına dikkat çekmek istiyorum. Buraya kadar anlattığım yöntemde hash değeri sonuçta keyfi uzunlukta bir harf dizisinin oluşturduğu polinomun değeri olacağından bu haliyle sabit bir uzunluğa sahip olmayacaktır. Bu sorunu gidermek için sonucu seçtiğimiz bir sayıya göre modulo işlemi yaparak bulabiliriz. Böylece hash değerimiz her zaman sınırlı olacaktır. Simulasyonda şimdilik bu modulo işlemini kullanmadım ama ileride bunu da ekleyebilirim.
Simulasyonda her kaydırma işleminden sonra diziden çıkarılan harf kırmızı ile diziye yeni eklenen harf ise yeşil renkle gösterilmiştir.
