Etiket: metin arama algoritmaları

Bad Character algoritması

Bu yazı ve algoritma dizisinde de metin arama algoritmalarından Boyer-Moore algoritmasını öğrenmeye çalışacağım. Diğer bazı metin arama algoritmalarında olduğu gibi bu algortimada da aranan metin her adımda tek adım kaydırılmıyor, aksine aranan metnin özelliğine göre kaydırma miktarları optimize ediliyor. Boyer-Moore algoritmasının şimdiye kadar öğrendiğim algoritmalara göre iki farklı özelliği var. Birincisi, aranan metin ve ana metin karşılaştırması sağdan sola doğru yapılıyor. İkincisi de kaydırma miktarını bulmak için iki değişik alt algoritma kullanılıyor. Bu yazıda bu iki algoritmadan biri olan Bad Character algoritmasını anlamaya çalışacağım.

Bu algoritma için aşağıdaki animasyonu programlamaya çalıştım.

Bad Character Rule

Bu animasyon başlatıldığında henüz hazırlanmamış bir tablo ve tablonun üzerinde seçilmiş bir aranan metin gösteriliyor. Tabloda normalde bir metinde olabilecek bütün karakterler olmalı (küçük harfler, büyük harfler, rakamlar vb.) ama sadece fikri gösterebilmek için tabloyu küçük tuttum. Animasyonda ana metni kullanmadım çünkü bu algoritma için ana metin değil aranan metne herhangi bir konumda uymayan bir karakter önemli. Bunu da aranan metnin üzerinde hesaplanacak konumda gösterilen bir karakterle göstermeye çalıştım.

Animasyonda aranan metin olarak

 NNAAMAN

dizisini kullandım. Her tablo seçilen aranan metne göre ayrı oluşturulması gerekiyor. Tabloyu şöyle düşünmeye çalıştım. Aranan metinde ana metni sağdan sola doğru karşılaştırdığımızda ana metindeki ilk uyumsuz karakteri en soldaki sütundan buluyoruz. Ardından bu uyumsuzluğun aranan metindeki hangi pozisyonda olduğunu da birinci satırdan okuyoruz. Algoritma bittiğinde bu tablo bize o karakter ve o konum için aranan metni sağa doğru kaç karakter kaydırabileceğimizi söyleyecek.

Bu tabloyu hazırlamak aslında çok kolay ama bu şekliyle tablo oldukça fazla yer tutmakta, çünkü olası her karakter için tabloda yer harcanıyor ama bu ilk versiyon için bu basit yöntemi anlamak yeterliydi benim için. Literatürde bu sorunla ilgili çeşitli çözümler var ve ileride onlara da bakabilirim.

Tablodan sırayla her satırdaki harf için olası her pozisyonu alıyorum ve bu harfi aranan metnin üzerinde o pozisyonda gösteriyorum. Eğer seçtiğim harfler aranan metindeki harf aynı ise tabloda bu noktaya “-” işareti koyuyorum, çünkü bu algoritma sadece uyumsuzluk varken kullanılıyor. Eğer uyumsuzluk varsa aranan metinde sola doğru harfleri tek tek kontrol ediyorum. Seçilen harfle aynı harfi ilk bulduğum konuma kadar aranan metni sağa doğru kaydırabilirim, çünkü aradaki her durumda bir uyumsuzluğun çıkacağı kesin. Eğer bir harfi uyumsuzluğun çıktığı konumdan sonra bir daha bulamazsam da aranan metni uyumsuzluktan bir sonraki konuma kadar kaydırabilirim. Bu şekilde her karakter ve konum için aranan metni ne kadar kaydırmam gerektiğini tabloya işliyorum. Bu şekilde bu basit algoritma da tabloyu oluşturmuş oluyor.

Failure Function

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.

  1. 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.
  2. İ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.

Simulasyon

Rabin-Karp algoritması

Bu yazıda metin içinde yazı aramada kullanılan bu algoritmayı basitçe tanıtıp simülasyonunu göstereceğim. Basit yazı arama algoritmasında her adımda aradığımız yazıyı metin üzerinde kaydırıp tek tek aynı pozisyonda aynı harflerin olup olmadığına bakmıştık. Yani aradığımız yazıyı bulana kadar her adımda ilk farklı harfe rastlayana kadar her harfi defalarca karşılaştırmıştık.

Bu algoritmada aynı harfleri defalarca karşılaştırma sorununa ilginç bir çözüm sunuluyor. Rolling hash denen bu algoritmayı daha önceki yazımda ele alıp simülasyonunu vermiştim. Kabaca aynı yazı parçalarının hash değerleri aynı olmalıdır fikrinden yola çıkılarap geliştirilmiş bir algoritma bu rabin-karp algoritması. Tabii ki her adımda kaydırılmış yazı parçalarının hash değerlerini tekrar tekrar her harfi kullanarak hesaplamamak için rolling hash kullanılıyor. Metinde aranan parça ile aynı hash değerini veren bir parça bulunduğunda bu parçanın harflerini tek tek karşılaştırmak gerekiyor çünkü farklı metin parçaları aynı hash değerlerini üretebilir.

Simülasyonda da bunu yapıyorum. Her kaydırmadan kontrol edilen metin parçası gri renkle işaretleniyor. İlk adımda hash değeri bütün harf değerleri üzerinden hesaplanıyor. Ardından her kaydırmada rollin hash algoritması kullanılarak yeni parçanın hash değeri daha hızlı hesaplanıyor. Eğer bir yerde aynı hash değerleri bulunursa bu sefer o alt parçanın bütün harfleri aranan yazının harfleriyle tek tek karşılaştırılıyor. Eğer harfler aynı ise bu harf yeşile boyanıyor, değilse kırmızı. Bütün harfler yeşil ise o zaman aradığımız yazıyı bulduk demektir ve algoritma sonlanıyor.

Bu linkten simülasyonu kullanabilirsiniz.