Yazan : Şadi Evren ŞEKER
Algoritmanın gayesi, bir metin içerisinde verilen bir dizginin (string) aranmasıdır. Literatürde arama yapılan metin için T (ingilizcedeki Text (metin) kelimesinden gelmektedir) ve aranan kelime için P (ingilizcedeki Pattern (örüntü) kelimesinden gelmektedir) kullanılmaktadır.
Klasik bir arama, yukarıdaki temsili resimde gösterilmiştir.
Algoritmanın diğer metin arama algoritmalarından en büyük farkı, aranan dizgi (pattern) yerine aranılan metin (text) üzerinden işlem yapmasıdır.
Yukarıdaki şekilde gösterildiği gibi, üzerinde arama işleminin yapıldığı metinde bulunan herhangi bir x harfi için, aranılan metin üzerindeki (pattern) en solda olan harf bulunmaya çalışılır.
arama işlemine başlanan α değerinin ardından gelen harfler eşleştiği sürece, aranan kelimenin (pattern) sonuna kadar eşleştikçe arama işlemi devam eder. Şayet bu aşama uyuşmayan bir harf olursa, zaten aranan kelimenin olmadığı sonucuna varılabilir.
Ardından uyuşma olup olmadığına bakılmaksızın aranan kelimeyi ß değerine denk gelecek şekilde kaydırma işlemi yapılır. Bu kaydırmanın olması için kelimenin (pattern) kalan kısmında ikinci bir değerinin bulunmaması gerekir.
Örnek
Algoritmanın çalışmasını bir örnek üzerinden göstermeye çalışalım.
Yukarıdaki şekilde görüldüğü üzere, aranan kelime için (P) sağdan sola doğru bir numaralandırma yapılmakta ve bu numaralandırma üzerinden aşağıda gösterilen HpBc dizisi çıkarılır. Bu dizi üzerinden metin üzerinde arama yapılır.
Sırasıyla önce, A harfi aranır. Ardından C ve G harfleri aranır. Dikkat edilirse, kelimede üç kere geçen A harfi, dizide bir kere kullanılmaktadır.
Uyuşma oldukça aranan kelime kaydırılmaktadır.
Müsvette Kod (Pseudo Code)
Algoritmanın müsvette kodu aşağıdaki şekilde yazılabilir:
Horspool (P = p1p2…pm,T = t1t2…tn)
Önişleme Aşaması
For c Î ∑ Do d[c] ← m
For j Î 1…m-1 Do d[pj] ← m – j
Arama Aşaması
pos←0
While pos ≤ n-m Do
j ←m
While j > 0 And tpos+j = pj Do j ← j-1
If j = 0 bulundu: pos+1
pos ← pos +d[tpos+m]
End of while
Yukarıdaki algoritmada geçen değerlerin, örnek üzerindeki gösterimlerini adım adım anlatmaya çalışalım:
Yukarıdaki ilk adımda aranan ilk harf olan C harfi için öncelikle kümede olup olmadığı kontrolü yapılır. Bunun anlamı aranan kelimenin harflerinden birisi olmaması durumunda vakit kaybedilmemesidir.
İkinci adımda ise daha önce çıkardığımız HpBc[a] dizisine göre her harfin değerleri atanır.
Arama işleminin devamı aşağıdaki şekildedir:
GCATCGCAGAGAGTATACAGTACG
GCAGAGAG
pos ← 0 + d[t0+7] , pos ← 0 + d[A], pos ← 1
Yukarıda görüldüğü üzere, kelimenin ilk kontrolü için 1. pozisyonda bulunan A değeri aranmıştır. Ardından arama işlemi sonraki harf olan G için aşağıdaki şekilde devam eder:
GCATCGCAGAGAGTATACAGTACG
GCAGAGAG
pos ← 1 + d[t1+7] , pos ← 1 + d[G], pos ← 3
G harfi ile C harfinin tutuşmamasından dolayı aranan kelime (P) kaydırılmıştır.
GCATCGCAGAGAGTATACAGTACG
GCAGAGAG
pos ← 3 + d[t3+7] , pos ← 3 + d[G], pos ← 5
Benzer şekilde C ve G uyuşmamasından dolayı bir kere daha kaydırıyoruz.
GCATCGCAGAGAGTATACAGTACG
GCAGAGAG
While j > 0 And tpos+j = pj Do j ← j-1
If j = 0 pos+1’de bulundu
pos ← 5 + d[t5+7] , pos ← 5 + d[G], pos ← 7
Görüldüğü üzere aranan kelime ile uyuşma oldu. Algoritmamızın ilgili satırlarını çalıştırıyor ve bulunduğunu rapor ediyoruz.
GCATCGCAGAGAGTATACAGTACG
GCAGAGAG
pos ← 7 + d[t7+7] , pos ← 7 + d[A], pos ← 8
İkinci kere A harfini arıyoruz.
GCATCGCAGAGAGTATACAGTACG
GCAGAGAG
pos ← 8 + d[t8+7] , pos ← 8 + d[T], pos ← 16
Bulunan A harfi G harfi ile uyuşmadığı için atlıyoruz:
GCATCGCAGAGAGTATACAGTACG
GCAGAGAG
pos ← 16 + d[t16+7] , pos ← 16 + d[G], pos ← 18
pos > n-m // pos >23-7
while döngüsünden çık.
Son olarak kelimenin sonuna gelindiği halde aranan yazı bulunmadığı için algoritma sonlanıyor.
Algoritmanın Karmaşıklığı
Algoritmanın zaman karmaşıklığı aranan kelimenin boyu n ve aranılan kelimenin boyu m olmak üzere O(mn)’dir denilebilir. Çünkü en kötü durumda her aranılan kelime harfi için üzerinde arama yaptığımız her harfi karşılaştırmamız gerekebilir. Bu da her n harf için m adet karşılaştırmaya eşittir.
Merhaba, hocam good suffix tablosu nasıl oluşturuluyor?
Dizgi arama alagoritmaları (mesela bu yazıdaki horspool veya Boyer-Moore Algoritması gibi) aslında birer arama algoritmasıdır ve verilen bir dizginin içinde bir diğerini arar ve tutuşma durumuna göre aranan dizgiyi kaydırarak aramaya devam eder.
Bad character heuristic (kötü karakter sezgisi) veya good suffix table (iyi ek tablosu) gibi algoritmalar ise Sezgisel Algoritmalar (heuristic altorithms) olup amaçları arama uzayını makul miktarda azaltmaktır (admissible).
Bu iki sezgisel yaklaşım aslında dizgi arama algoritmaları üzerindeki birer iyileştirme olarak düşünülebilir, algoritma prensip olarak aynı şekilde çalışmakta ancak arama süresi kabul edilebilir miktarda azalmaktadır.
Dizgi arama algoritmasının alt seviyede çalışma mantığı, iki dizgiyi karşılaştırmak ve uyuşma sağlanamadığı noktada bir kaydırarak tekrar karşılaştırmaktır (kaba kuvvet yaklaşımı (brute force)) ancak bu yaklaşımın işlem süresi uzundur. Bunun yerine horspool algoritmasında olduğu gibi, iki dizginin uyuşmadığı anlaşıldığı anda karşılaştırma kesilir (bir uymayan örnek bulunması durumu) ve bu uyuşmazlığa göre kaydırma yapılarak çalışma süresi kısaltılmaya çalışılır.
Bu kaydırma miktarını belirlerken iki yaklaşımdan bahsedilebilir. Birincisi bad character heuristic (kötü karakter sezgisidir) ve yukarıdaki yazı bu sezgi üzerine kurulu olarak açıklanmıştır. Yani uyuşmayan bir örnek bulunduğunda Beta değeri bulunur ve beta değeri kadar kaydırma işlemi yapılır. Buradaki temel kural uyuşmayan örneği bulmak ve buna göre kaydırma yapmaktır.
Bu yaklaşımdan biraz daha karmaşık olan (kodlama açısından) ve literatürde good suffix heuristic olarak geçen yöntem ise, uyuşan dizgi miktarını bularak buna göre kaydırma yapmayı hedefler.
Bu işlemin (yani ne kadar alt dizginin uyuştuğunun ) tutulması ise hafıza karmaşıklığı yüksek bir işlemdir yani (bad character heuristic yaklaşımında uyuşmayan bir örnek bulabilmeniz için tek karakter tutmanız yeterlidir buna karşılık) good suffix yaklaşımında uyuşan bütün örneğin tutulması gerekir, işte bu yüzden bilginin tutulduğu bir veri yapısına ihtiyaç duyulur. Örneğin sizin sorunuza konu olan tablo kullanılması ve uyuşan kısımların bir tabloda tutularak kaydırma miktarlarının hesaplanması mümkündür.