Bu seferki algoritma aslında yine başka bir algoritmada kullanılan bir parça olacak. Basit metin arama algoritmasında bulmak istediğimiz metin parçasını ana metin üzerinde her adımda bir karakter kaydırarak üst üste gelen harflerin aynı olup olmadığına bakıyorduk. Bu yazıda bakacağımız algoritma her adımda bir karakter kaydırma sorununa bir çözüm bulmaya çalışacak.
Aradığımız metin parçasındaki harflerin özelliklerini kullanarak bazen birden fazla karakter kaydırma imkanını elde edebiliriz. Yani karakterleri karşılaştırırken fark olan ilk konuma kadar olan karakterlere göre birer karakter kaydırmanın bu başlangıç kısmında bir eşitlik yaratamayacağından emin olabilirsek bundan faydalanarak kaydırma adımını hızlandırabiliriz. Hedefimiz şu: Arama metnindeki ilk uyumsuzluğun konumuna göre kaç adım sıçrama yapmamız gerektiğini söyleyen bir tablo bulmak istiyoruz. Dolayısıyla normal arama işleminde yine karakterleri tek tek kontrol edeceğiz ama ilk farkta bu tablo bize bir sonraki arama için ne kadar sıçrama yapmamız gerektiğini (şansımız iyi giderse birden fazla) söyleyecek.
Wikipediadan aldığım bazı örnekleri vereyim şimdi.
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
Burada ana metin S ile aradığımız metin de W ile gösterilmekte. Burada i = 3 indeksli karakter ilk uyumsuzluğun olduğu yer. Şimdi W ile gösterilen karakter dizisini birer birer sağa kaydıracağım ama bu sırada S karakter dizisinde algoritmanın henüz görmediği yerlere X koyacağım. Bu X koyulu yerlere karşılık gelecek W karakterlerini de kullanmaya gerek olmayacak çünkü bu karakterleri henüz görmediğimizden buralarda eşitlik olup olmadığını bilmiyoruz.
1 2 m: 01234567890123456789012 S: ABCXXXXXXXXXXXXXXXXXXXX W: ABC i: 0123456
İlk kaydırmadan sonra ilk konumda (i = 1) bir eşitsizlik var. Daha bakmaya gerek yok, bir kere daha kaydıralım.
1 2 m: 01234567890123456789012 S: ABCXXXXXXXXXXXXXXXXXXXX W: ABC i: 0123456
Yine W parçasının başı yukarıdaki S dizisinin bilinen kısmının sonuyla uyuşmadı. Demek ki bu diziyi iki adım kaydırmak da işe yaramayacak. O zaman aramaya 3 adım kaydırarak devam etmek lazım.
Bu örnekten sonra iki şeye dikkat çekmek istiyorum.
- Aradığımız şey aslında W dizisinin başındaki bir dizinin (önek) yine W dizisinin sonundaki bir diziyle (sonek) uyuşup uyuşmadığı. İlk X nerede olursa olsun oraya kadar S dizisiyle yine aynı konuma kadarki W dizileri aynı olduğundan yukarıdaki fikri kullanabiliriz.
- İlk bakışta yine her adımda W dizisinin bir önekini bir kaydırıp kontrol ediyoruz gibi görünüyor ve böylece aramada yine her seferinde W dizisini bir karakter kaydırıp basit arama algoritmasına döneceğiz gibi geliyor ama aslında bunu sadece örnek olarak verdim. İleride bu tabloyu aramadan önce sadece arama metnini kullanarak bir kereliğine oluşturabileceğimizi göreceğiz.
Örnek:
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
Burada ilk uyumsuzluk i = 6 konumunda oluşmuş. O zaman ana metinle aranan metin arasında i = 5 noktasına göre tam uyum vardır. O zaman aranan metnin o noktasına kadarki önekiyle ilgileneceğiz.
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABXXXXXX W: ABCDAB i: 012345
Şimdi aranan metni birer kaydırdığımızda kendi önekiyle yine kendi soneki arasındaki uyumlara bakalım.
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABXXXXXX W: ABCDAB i: 012345
i = 0 noktasında uyumsuzluk var. Yine kaydırmamız lazım.
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABXXXXXX W: ABCDAB i: 012345
Uyumsuzluk devam ediyor. Yine kaydıracağız.
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABXXXXXX W: ABCDAB i: 012345
Hala uyum bulunamadı. Kaydırmaya devam ediyoruz.
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABXXXXXX W: ABCDAB i: 012345
Burada sonunda aranan W metninin iki karakterlik öneki ile yine W nin (tabii ki 6 karakterlik kısmı için, bu uzunluk en baştaki ilk uyumsuz nokta ile belirleniyor) iki karakterlik soneki arasında bir uyum bulundu. Demek ki tablomuzda ilk uyumsuzluk 6. konumda bulunursa 4. konuma kadar kaydırılmalı diye bir kayıt bulunmalı. Algoritma bu uyumsuzlukla karşılaştığında birer birer kaydırmak yerine hemen 4 karakter kaydırarak aradaki kontrolleri gönül rahatluğıyla atlayabilir.
Burada bir gözlemden daha bahsedeyim. Sağa doğru birer birer kaydırırken ilk uyumlu önnek, sonek çiftini bulduğumuzda kaydırmayı kesmemiz lazım. Yani en uyumlu olan en uzun önek, sonek çiftini arıyoruz. Bunun nedeni de aslında kolayca anlaşılabilir. Aranan metni kaydırdıkça bu metnin en son kısmı hep X ile gösterdiğimiz bölüme kayıyor, yani bu bölümde de uyumun devam etme hatta aranan metnin tamamının bulunma şansı var. Dolayısıyla bulunan ilk önek, sonek uyumunda durulmalı ki bu ihtimal gözden kaçırılmadan kontrol edilebilmeli.
Bir küçük nokta daha var ama onu zaten farketmişsinizdir. Önek ve soneklerin uyumuna bir kere kaydırdıktan sonra bakıyoruz. Kaydırmadan bakarsak her zaman uyumlu olurlar ve bu durumda algoritmamız kaydırmaya gerek yok diye saçma bir düşünceye kapılabilir.
Aşağıdaki linkten animasyon sayfasına girerek bu tablonun başta ana metne ihtiyaç duymadan nasıl hazırlandığını görebilirsiniz. Yani tabloyu arama algoritmasının en başında üretebiliriz ve sonra ana metinle beraber kolaylıkla kullanabiliriz. Bu kullanımı da başka bir yazı ve animasyonda göstereceğim.
Tablonun üzerindeki kısım önce indeks listesiyle başlıyor. İkinci satır ana metnin o ana kadar uyum sağlanmış kısmını gösteriyor. Bu farazi bir ana metin tabii ki, bütün işlemi aslında aranan metinde yapmama rağmen bu ana metin kısmını da göstermek istedim. Aranan metindeki uyumsuzluğun olduğu ilk nokta dolaylı olarak da ana metni o noktaya kadar belirlediği böylece daha kolay anlaşılır belki. Üçüncü satır aranan metnin tamamını gösteriyor. Son satır ise simulasyon sırasında kaydırılan kısmı gösteriyor. Yukarıdaki örneklerdeki W kısmı (ana metinle tam uyum sağlayan kısmı tabii ki) yani.
Tablonun başlık satırı indekslerden oluşuyor, yani yukarıdaki örneklerdeki i satırı. İkinci satır önek ve soneklerdeki en uzun uyumlu karakter dizisini gösteriyor. Son satır da algoritmanın indeks numaralı pozisyondaki uyumsuzluk için arama metnini kaç karakter kaydetmesi gerektiğini gösteriyor. Dikkat ederseniz index – maksimum uzunluk = kaydırma miktarı gibi bir eşitlik de var.