Ters Parça Algoritması (Reverse Factor Algorithm)

Yazan : Şadi Evren ŞEKER

Algoritma iki dizgiyi (string) karşılaştırmak için kullanılır. Basitçe bir dizgide aranan daha kısa dizginin öncelikle aşağıdaki şekilde karşılaştırılması ile başlanır. Ardından şayet uyum sağlanıyorsa bulundu olarak sonuç döndürülür, şayet uyum sağlanmıyorsa iki ihtimal vardır, dizgilerin karşılaştırılan kısımlarından uyan en uzun eke kadar kaydırma yapılır veya hiç uyuşma yoksa aranan dizgi kadar kaydırma yapılır.

Öncelikle bu kaydırma durumunu anlayalım. Uzun olan dizginin kısa olan dizgi kadarlık ilk kısmı aşağıdaki şekilde karşılaştırılacak.

Diyelim ki aradığımız uyum bulundu, o zaman bulduk diyerek sonucu döndürebiliriz.

Diyelim ki aradığımız uyum bulunamadı, o zaman acaba en azından bir kısmı uyuyor mu diye bakarak uyan kısmına kadar kaydırıyoruz.

Şayet hiç uymuyorsa, kısa olan dizgi kadar kaydırarak kalanını aramaya devam ediyoruz.

Algoritmanın mahareti, bu iki dizgiden bir kısmının uyup uymadığını nasıl bulduğunda saklı. Bunun için bir ek ağacı (suffix tree) oluşturuluyor ve bu ağaç kullanılarak hızlı bir şekilde iki dizginin ne kadarlık kısmının uyduğu tespit edilebilir. Biz de bir örnek üzerinde bu karşılaştırmayı yapalım. Bunun için öncelikle iki örnek dizgiyi aşağıdaki şekilde alalım:
Dizgi 1 : GCATCGGCGAGAGTATACAGTACG
Dizgi 2 : GCAGAGAG , boyutu 8 harf

Yapacağımız karşılaştırma öncesi, dizgi 2 için bir otomat oluşturuyoruz (sonlu durum otomatı (finite state machine). Otomat oluştururken aslında bizim Dizgi 1 içerisinde aramak istediğimiz dizgi 2 ihtimallerinin bir kümesini kabul eden otomat oluşturma hedefimiz var. Yani öncelikli olarak baktığımız dizgi2’nin tamamının (8 harfinin de ) içerilmesi, şayet bulamıyorsak, dizgi2’nin bir alt kümesi olan ve ilk 7 harfinin içerildiği bir durum bulmak (yani 1 kere yana kaydırılmış hali olarak düşünülebilir). Dolayısıyla otomatı oluşturacağımız alt küme L(S) ile gösterilecek olursa aşağıdaki şekildedir:

L(S) = { GCAGAGAG, GCAGAGA, GCAGAG, GCAGA, GCAG, GCA, GC, G, {} }

Kümenin sonunda ayrıca bir boş küme elemanı bulunmakta ve hiçbir harfin uymaması durumunu ifade etmektedir. Yukarıdaki kümedeki elemanları kabul eden sonlu durum otomatı (Finite state machine) aşağıdaki şekilde çizilebilir:

 

Dizgi de tekrar eden bazı alt dizgiler olduğu için yukarıdaki şekilde bir otomat oluşturuldu. Şimdi bu otomat kullanılarak bir ek ağacı (suffix tree) oluşturulabilir:

Yukarıdaki ek ağacı bizim dizgi karşılaştırmalarımızda kullanacağımız ve ne kadarlık son kısmın benzediğini bulmamıza yarayacak ağaç. Ağaç üzerinde her düğüme (node) birer numara verilmiş ve ayrıca ağacın yapraklarının altına da o yaprağa kadar izlenen yoldaki dizginin uzunluğu yazılmıştır.

Şimdi örnek olarak bir karşılaştırma durumunu ele alalım. Örneğin karşılaştırma işlemi aşağıdaki gibi dizgi1’in 6. Karakterinden itibaren dizgi 2’yi karşılaştırıyor olalım:

Yapacağımız işlem, pencereye dahil olan kısmı itibariyle (pencere boyutumuz dizgi 2’nin boyutu yani 8) en son karakter ile dizgi2’yi karşılaştırmak. Yani aslında karşılaştırılan ilk harfler aşağıdaki şekilde:

Ardından ek ağacındaki bir sonraki harfi yani aslında penceredeki sondan ikinci karakter ile dizgi2’nin ikinci karakterini aşağıdaki şekilde karşılaştırıyoruz ve bu işlem uyuşma olduğu sürece devam ediyor:

Sonuçta uyuşma olmayan noktaya erişildiğinde duruyoruz ve uyuşma olduğu kadar kaydırma işlemi yapıyoruz:

Aslında yukarıda dizgi üzerinde anlatılan bu işlem yapılırken ağaç üzerinde aşağıdaki şekilde bir yol izlenmiş ve 6 numaralı bitiş durumu ile otomat sonlandırılmıştır.

Algoritmanın ön işleme süresi, yani ek ağacını oluşturma süresi dizgi 2’nin boyutu ile orantılıdır ve bu boyut m ise karmaşıklığı O(m) olacaktır. Ardından arama süresindeki algoritma karmaşıklığı ise dizgi1’in boyutu ile orantılı olarak O(mn) olarak bulunacaktır.

Diğer Dizgi Arama Algoritmaları:

• Horspool Arama Algoritması
• Knuth-Morris Prat arama algoritması
• Boyer-Moore Arama algoritması
• Kaba Kuvvet Metin Arama Algoritması (Brute Force Text Search, Linear Text Search)
• DFA Metin Arama Algoritması

Kaynaklar
• Algorithms for finding patterns in strings, A. V. Aho, Handbook of Theoretical Computer Science, Vol. A, Elsevier, Amsterdam, 1990, pp.255-300.
• The myriad virtues of suffix trees, Apostolico, A., Combinatorial Algorithms on words, NATO Advanced Science Institutes, Series F, Vol. 12, 1985, pp.85-96
• The Boyer-Moore-Galil string searching strategies revisited, Apostolico, A. and Giancarlo, R., SIAM, Comput. 15, 1986, pp98-105.
• Average running time of the Boyer-Moore-Horspool algorithm, Baeza-Yates, R. A. and Regnier, M. Theoret. Comput. Sci., 1992, pp.19-31.
• Analysis of algorithms and Data Structures, Banachowski, L., Kreczmar, A. and Rytter, W., Addison-Wesley. Reading, MA,1991.
• Speeding up on two string matching algorithms,
• Presentation of Prof. R. C. T. Lee and L. C. Chen ,Algorithmica, Vol.12, 1994, pp.247-267, CROCHEMORE, M., CZUMAJ, A., GASIENIEC, L., JAROMINEK, S., LECROQ, T., PLANDOWSKI, W. and RYTTER, W.