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.

reverse_factoring_algo1

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

reverse_factoring_algo2

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.

reverse_factoring_algo3

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

reverse_factoring_algo4

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:

 

reverse_factoring_algo5

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:

reverse_factoring_algo6

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:

reverse_factoring_algo7

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:

reverse_factoring_algo8

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:

reverse_factoring_algo9

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

reverse_factoring_algo10

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.

reverse_factoring_algo11
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ı:

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.

Yorumlar

  1. Kağan

    Merhaba hocam bu resimde http://bilgisayarkavramlari.sadievrenseker.com/wp-content/uploads/2015/04/reverse_factoring_algo9-300×45.png dizgi2 deki G ile pencerenin sonundaki G karşılaştırıldı.Bunu anladım.Ancak neden siz “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:” böyle dediniz.Dizgi2 deki C ile pencerenin sondan birinci harfi olan A nın karşılaştırılması gerekmiyor mu?

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir