Horspool Algoritması

Algoritmanın gayesi, bir metin İÇERİSİNDE Verilen Bir  dizginin (string)  aranmasıdır. Literatürde arama Yapılan metin Click T (ingilizcedeki Metin (metin) kelimesinden gelmektedir) aranan kelime Click P (ingilizcedeki Desen (örüntü) kelimesinden gelmektedir) kullanılmaktadır ettik.

Klasik bir arama, yukarıdaki resimde gösterilmiştir Temsili.

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 sekilde gösterildiği gibi, uzerinde arama isleminin Yapıldığı Metinde Bulunan HERHANGİ Bir X harfi İç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 İşlemi devam eder. Şayet bu aşama uyuşmayan bir harf olursa, zaten aranan kelimenin olmadigi sonucuna varılabilir.

Ardından uyuşma OLUP olmadığına bakılmaksızın aranan kelimeyi ß değerine denk gelecek sekılde kaydırma İşlemi Yapılır. Bu kaydırmanın Olması Click kelimenin (pattern) kalan kısmında ikinci Bir değerinin bulunmaması Gerekir.

Örnek

Algoritmanın CALISMASINI Bir örnek Üzerinden göstermeye çalışalım.

Yukarıdaki sekilde görüldüğü Üzere, aranan kelime Click (P) sağdan sola doğru Bir numaralandırma yapılmakta bu numaralandırma Üzerinden aşağıda gösterilen HpBc dizisi çıkarılır ve. Bu dizi Üzerinden metin uzerinde arama Yapılır.

Sırasıyla, bir kez harfi aranır. Ardından C G harfleri aranır ettik. Dikkat edilirse, kelimede üç kere Geçen A harfi, dizide bir kere kullanılmaktadır.

Uyuşma oldukca aranan kelime kaydırılmaktadır.

Müsvette Kod (Pseudo Code)

Algoritmanın müsvette kodu aşağıdaki sekılde yazılabilir:

Horspool (p = p 1 p 2 ... p m , T = t 1 t 2 t ... n )  

Önişleme Aşaması

Için c Î Σ Do d [ c ] ← m     

Için j Î 1 ... m -1 Do d [ p j ] ← m - j     

Arama Aşaması

Poz ← 0

Iken pos ≤ nm Do    

j  ← m

Iken j > 0 Ve t pos + j = p j     Do j ← j- 1        

Eğer j : = 0 Bulundu pos +1   

pos  ← pos + d [ t pos + m ]  

Süre sonu

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 olmadigi KONTROLÜ Yapılır. Eklendi bunun anlamı aranan kelimenin harflerinden birisi Olmaması durumunda vakit kaybedilmemesidir.

İkinci Adımda ISE Daha Önce çıkardığımız HpBc [a] dizisine Göre onu Harfin Değerleri atanır.

Arama isleminin devamı aşağıdaki şekildedir:

GCATCGC bir GAGAGTATACAGTACG

GCAGAGA G

     Poz  ← 0 + d [t 0 + 7 ], pos ← 0 + d [ A ], pos ← 1        

Yukarıda görüldüğü Üzere, kelimenin ilk KONTROLÜ Bir Değeri aranmıştır Bulunan 1. pozisyonda Click. Ardından arama İşlemi Sonraki harf Olan G Click aşağıdaki sekılde devam eder:

GCATCG CAG AGAGTATACAGTACG

GCAGA GAG

pos  ← 1 + d [t 1 + 7 ], pos ← 1   + d [ G ], pos ← 3.  

G harfi ile Cı harfinin tutuşmamasından Dolayı aranan kelime (P) kaydırılmıştır.

GCATCG CAGAG AGTATACAGTACG

GKRY GAGAG

pos  ← 3 + d [t 3 + 7 ], pos ← 3 + d [ G ], pos ← 5      

Benzer sekilde Cı G ziyaretinde uyuşmamasından Dolayı bir kere Daha kaydırıyoruz.

GCATC GCAGAGAG TATACAGTACG

GCAGAGAG

Iken j > 0 Ve t pos + j = p j Do j ← j-1        

Eğer j = 0 pos + 1'de Bulundu   

pos  ← 5 + d [t 5 + 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 bulunduğunu rapor Ediyoruz ettik.

GCATCGCAGAGAGT bir TACAGTACG

GCAGAGA G

pos  ← 7 + d [t 7 + 7 ], pos ← 7   + d [ A ], pos ← 8  

İkinci kere A harfini arıyoruz.

GCATCGCAGAGAGTA T ACAGTACG

GCAGAGA G

pos  ← 8 + d [t 8 + 7 ], pos ← 8   + d [ T ], pos ← 16  

Bir harfi G harfi ile uyuşmadığı Click atlıyoruz Bulunan:

GCATCGCAGAGAGTATACAGTAC G

GCAGAGA G

pos  ← 16 + d [t 16 + 7 ], pos ← 16   + d [ G ], pos 18 ←  

pos> nm // pos> 23-7

döngüsünden cik iken.

Oğlu Olarak kelimenin Sonuna gelindiği halde aranan yazı bulunmadığı Click algoritma sonlanıyor.

Algoritmanın Karmaşıklığı

Algoritmanın zaman karmaşıklığı aranan kelimenin boyu n ziyaretinde aranılan kelimenin boyu m olmak Üzere O (mn) 'dir denilebilir. Çünkü en kötü DURUMDA onu aranılan kelime harfi Click uzerinde arama Yaptığımız onu harfi karşılaştırmamız gerekebilir. Bu da onu n harf Click m adet karşılaştırmaya eşittir.

 Brute-Force'a Benzer sekilde pattern'in oğlu harfinden başlanarak soldan saga ve yukagbıdan doğru desen ziyaretinde text'te karşılıklı denk gelen harfler karşılaştırılır. Eger pattern'deki Tüm karakterlerin eşleşmesi sağlanırsa alt dize bulunmuş demektir. Bu DURUMDA arama durdurulabilir VEYA Başka eşleşme var mı diye Aramaya devam Edilebilir.

Eşleşme olmazsa pattern'i Sağa kaydırmamız Gerekir. Bu DURUMDA HERHANGİ Bir eşleşmeyi kaçırma olasılığını riske atmadan yapabileceğimiz En Büyük olasi kaydırmayı yapmak isteriz. Horspool algoritması burada son karakterine karsilik gelen (c) 'pattern'in karakterine bakarak kaydırma yapar. Burada dört Olasılık söz konusudur. Bu durumlardan ilerideki sayfalarda bahsedilecek.

BERBER pattern'ini Bir text'te aradığımızı düşünelim.

Pattern'in oğlu elemanı Olan R ile başlayarak sağdan sola doğru hareket ediyoruz ziyaretinde metin ile pattern'de karsilik gelen Karakterleri karşılaştırıyoruz. Eger pattern'deki karakterlerin tümü eşleşirse alt dize bulunmuş demektir.

Eşleşme olmazsa pattern'i Sağa kaydırmamız Gerekir. Bu DURUMDA HERHANGİ Bir eşleşmeyi kaçırma olasılığını riske atmadan yapabileceğimiz En Büyük olasi kaydırmayı yapmak isteriz. Horspool algoritması burada son karakterine karsilik gelen (c) 'pattern'in karakterine bakarak kaydırma yapar.

Burada dört durum söz konusudur.

Durum 1 : c harfi pattern'de yoksa Örn. örnekteki S harfi. . Bu DURUMDA pattern'i BOYUTU Kadar Sağa kaydırabiliriz (Bu boyuttan Küçük Bir karşılastırma gerçekleştirirsek pattern'i karşılaştırdığımız KONUMDA pattern'de olmayan Bir c harfi ile denk getirmiş oluruz):

Durum 2 : Patternde c harfi Varsa o oğul karakter değilse orn ettik. örnekteki B harfi. Kaydırma Cı harfinin patternde görüldüğü en Sağ Noktaya denk gelecek sekilde gerçekleştirilmelidir, bu sekilde patterndeki Cı harfi ile text'teki Cı harfi eşleşmiş olur ziyaretinde Diğer karakteler de Eşit mi diye bakılır.

Durum 3:  c karakteri patterndeki oğlu karakterse göster Fakat pattern'in Diğer m - 1 karakterinde bu c karakteri yoksa Örn. örnekteki R harfi. Bu DURUMDA, makarnalık 1'e Benzer sekilde desen BOYUTU Kadar kaydırma Yapılır.

Durum 4 : c karakteri patterndeki oğlu karakterse pattern'in Diğer m A.Ş. - 1 karakterinde bu karakter tekrar ediyorsa Örn. örnekteki R harfi. Bu DURUMDA, Durum 2'ye Benzer sekilde patternde c'nin bulundugu tr Sağ Konuma Göre kaydırma Yapılır. Bu sayede text'teki c karakteri ile pattern'deki Cardio karakter hizalanmış olur. 

Bu örnek sağdan sola şeklinde gerçekleştirilen karakter karşılaştırmalarının kaba kuvvet algoritmasındaki gibi her Adımda Bir kaydırmadan öteye gidebileceğini Bize açıkça göstermektedir. Her turda patterndeki Tüm karakterlerin Kontrol Edilmesi bu algoritmanın üstünlüğünü Ortadan kaldırırdı. Neyse ki girdi Geliştirme fikri tekrar eden karşılaştırmaları gereksiz hale daha zor hale getiriyor. Kaydırma boyutlarını Önceden hesaplayıp Bir tabloya atabiliriz. Tablo text'te karşımıza çıkabilecek Tüm want Karakterleri içerecektir; doğal dil text'leri Click boşluk, noktalama işaretleri ziyaretinde Diğer Özel karakterler gibi. Tablo, folmül ile Bulunan kaydırma boyutunu gösterecektir.

Örneğin ERKEK pattern'i İçin, E, B, R3 4 OLACAKTIR ziyaretinde bir Karakterleri sırasıyla 1, 2, ve,. Diğer Tüm tablo Girdileri 6'ya Eşit OLACAKTIR.

Aşağıda kaydırma tablosunun hesaplanması Click Basit bir algoritma verilmiştir. Tablodaki Tüm Girdileri pattern'in BOYUTU Olan m Değeri Başlangıç ​​Değeri Olarak yüklenir desen ziyaretinde soldan Sağa doğru devamındaki aşamayı m - 1 kere tekrar EDECEK sekilde taranır; patterndeki j. karakter Click (0 <= j <= m - 2) ONUN tablodaki girdisini m - 1 - j ile Change Language. Bu da karakterin pattern'in oğul karakterine Olan uzaklığıdır. Algoritma pattern'i soldan saga ve yukagbıdan taradığı oğlu Click için üstüne yazma tr sağdaki karakterde gerçekleşecektir.

ALGORİTMA  ShiftTable (P  [0 ..M  -  1] )

// Horspool en ve Boyer-Moore algoritması tarafından kullanılan kaydırma tablosunu doldurur

// Girdi: Pattern  P [0 ..M  -  1] olası karakterleri ve bir alfabe

// Çıktı:  Tablo [0 ..size  -  1] alfabe karakterleri ve endeksli

// Formülle hesaplanan vardiya boyutları ile dolu

için  i  ← 0  için  boyut  -  1  do  Masa [ i ] ← m

için  j  ← 0  için  m  -  2  do  Tablo [ P [ j  ]] ← m  -  1 -  j

Dönüş  Tablosu

Algoritmayı şu sekılde özetleyebiliriz:

Adım 1  Verilen m boyutlu model ziyaretinde text'te Kullanılan alfabe Click kaydırma Tablosunu yukarda anlatıldığı gibi oluştur desen ziyaretinde

Adım 2  Pattern'i text'in Başına Hizala

Adım 3  Bunu Eşleşen Bir alt dize bulana Kadar ya da text'in Sonuna Kadar gelene tekrarla. Tüm m karakteri eşleşene Kadar ya da eşleşme bozulana Kadar pattern'deki oğlu karakterden başlayarak, ziyaretinde pattern'de text'de denk gelen Karakterleri karşılaştır. Eşleşme bozulursa Cı karakteri Click kaydırma tablosunda denk gelen sayıyı ark ziyaretinde pattern'i bu sayı Kadar Sağa kaydır.

ALGORİTMA  HorspoolMatching (P  [0 ..M  -  1] , T  [0 ..N  -  1] )

// Girdi: Pattern  P [0 ..M  -  1] ve metin  T  [0 ..N  -  1]

// Çıktı: ilk eşleşen alt dizenin sol ucunda indeksi

// Veya  - 1 eşleşme varsa

ShiftTable (P  [0 ..M  -  1] )           oluşturmak //  Tablo  kaymaların

i  ← m  -  desenin sağ ucunun 1 // pozisyonu

ise  i  ≤  n  -  1  do

k ← eşleşen karakter 0 // sayısı

ise  k  ≤  m  -  1  ve  P [ m  -  1 -  k ] =  T  [ i  -  k ]  do

k ← k  +  1

eğer  k  =  m  dönüş  i  -  m  +  1

Başka  i  ← i  +  Masa [ T  [ i ]]

dönmek  - 1

ÖRNEK  Horspool algoritmasının tam uygulamasına örnek vermek gerekirse; İngilizce harflerden Boşluktan ziyaretinde (alt çizgi ile gösterilen) OLUŞAN Bir text'te ERKEK kelimesini arayacak olalım. Öncelikle kaydırma Tablosunu Önceden belirttiğimiz formül ile aşağıdaki gibi doldururuz.

Arama İşlemi imkb aşağıdaki gibi gerçekleşir.

Horspool algoritmasının kötü anahtar etkinligi O (nm) 'dir. Fakat BBC muhabirine rastgele textler Click met karmaşıklık  Θ (n) 'dir kaba kuvvet ziyaretinde sınıfı ile Cardio etkinliğe Sahip olsa da Horspool algoritması açıkça görülmektedir ki ona göre Daha hızlıdır. Hatta bu algoritma kendinin Daha Karmaşık hali Olan Boyer-Moore algoritması Kadar etkin'ait sayılır.

C # dili ile uygulanmış hali:

///  <summary>

///  Horspool algoritması Click vardiya Tablosunu oluşturur

///  </ summary>

///  <param name = "text"> Kontrol edilecek, metin </ param>

///  <param name = "desen"> Text'te Arancak kelime </ param>

///  <döner> Shift tablosuna Uygun'un Verileri atar </ döner>

Özel  static  void  ShiftMyTable ( dize  deseni,  dize  metni)

{

   bool  baskaVar =  false ;

           

   ShiftTable =  new  Hashtable ();  // Tablo edilir başlatılamadı

   için  ( int  i = 0; i <text.Length; i ++)

   {

       eğer  (! ShiftTable.ContainsKey (metin [i]))  // Text'teki Değişken tabloya Daha Önceden eklenmemişse

       {

           eğer  (! pattern.Contains (metin [i] .ToString ()))  // Text'teki harf patternde yoksa

               ShiftTable.Add (metin [i] pattern.Length);  // O harf Click pattern'in lenght'ini tabloya yaz

           başka

           { // Text'teki harf patternde Varsa

               için ( int  J = pattern.Length - 2, J> = 0; j--)

               {

                  eğer  (pattern [j] == metin [i])

                  {

                      baskaVar =  true ;

                      ShiftTable.Add (metin [i], pattern.Length - j - 1);  // Sondan başlayarak O Harfin patterndeki konumuna Göre tabloya Değeri atar

                      kırmak ;

                  }

               }

               eğer  (baskaVar ==  false )

                  ShiftTable.Add (metin [i], pattern.Length);

               başka

                  baskaVar =  false ;}}}}

Yukarıdaki algoritma Horspool algoritması Click Kullanılan kaydırma Tablosunu olusturan algoritmanın C # 'Edilmiş halidir uygulamak ta. Bu yöntem Parametre Olarak desen metin değişkenlerini almaktadır ettik.

için  ( int  i = 0; i <text.Length; i ++)

Text'teki Tüm karakterler Click kaydırma Değeri belirleniyor.

eğer  (! ShiftTable.ContainsKey (metin [i]))

Text'teki karakter Daha Önceden tabloya eklenmişse tekrar eklenmesi gerekmemesi Click Kullanılan koşul.

eğer  (! pattern.Contains (metin [i] .ToString ()))

Eger text'teki karakter patternde yoksa o karakter Click tabloda m Değeri yani pattern'in BOYUTU atanmaktadır. Karakter patternde Varsa karakterin konumunu sağdan başlayarak hesaplıyoruz ziyaretinde bulduğumuz Değer karakterin kaydırma tablosundaki Değer oluyor.

///  <summary>

///  Horspool algoritmasını kullanarak Verilen text'te desen eşleşmesi OLUP olmadığını bulur ziyaretinde eşleşme Varsa eşleşmenin konumunu Dondurur

///  </ summary>

///  <param name = "text"> Kontrol edilecek, metin </ param>

///  <param name = "desen"> Text'te Arancak kelime </ param>

///  <döner> Pattern eşleşmesinin konumunu Dondurur </ döner>

Özel  static  int  HorspoolMatching ( dize  deseni,  dize  metni)

{

      ShiftMyTable (desen, metin);  // Shift tablosunun hesaplanması Click yöntemi çağrılıyor

      int  i = pattern.Length - 1;

      ise  (i <= text.Length - 1)  // göstergesi lenght'ten Kısa ISE döngüye giriliyor

         {

            int  k = 0;

            ise  (- 1 && desen [pattern.Length - 1 - - k] == metin [i k] k <= pattern.Length)  ; // Anahtar karşılaştırma karşılaştırılan harfler eşitse Girilir

            {

                k ++;

            }

            Eğer  (k == pattern.Length)  // Desen bulunduysa

            {

               geri  i - pattern.Length + 1;  // Eşleşmenin Hakkinda Konumu döndürülüyor

            }

            başka

            {

               i = i +  dönüştürme , .ToInt32 (. ShiftTable [metin [i]] ToString ())  // Eşleşme tablosuna Göre endeksi vardiya çıkacağı kayması olmadıysa

            }}

      geri  -1;  // desen eşleşmesi yoksa -1 döndürülüyor

}

Algoritma Parametre Olarak desen text'i alıyor, ve. DAHA SONRA kaydırma tablosu oluşturuluyor. Eşleşme sağlanırsa k değişkeninin Değeri artıyor. k değişkeni m değerine ulaşırsa bu pattern'i textte bulduğumuz anlamına geliyor. Farkı bir durum olursa desen kaydırma tablosuna Göre Sağa kaydırılıyor ziyaretinde karşılaştırmaya devam ediliyor.

2-3-4 Ağaçları (2 3 4 trees)

2-3-4 ağacı, B-ağaçlarının (B-Trees) özel bir halidir. Bu ağacın özelliği, düğüm boyutunun (node size) 3 ile sınırlı olmasıdır. Ağaç ayrıca sürekli olarak dengeli bir ağaç garantisi verir (balanced tree). 2-3-4 ağaçları, kırmızı siyah ağaçlarının (red-black trees) , eş şekillisi (isomorphic) olarak da düşünülebilir.

2-3-4 ağacının ismi, ağaçtaki düğümlerin değişik durumlarda değişik numaralar almasından kaynaklanmaktadır. Yani bir düğüm 2,3 veya 4 durumunda olabilir. Bu durumlara göre farklı uygulamalar söz konusudur.

2 düğümü: 2 adet çocuk düğümü gösteren gösterici (pointer) ve bir veriden oluşur

3 düğümü: 3 adet çocuk düğümü gösteren gösterici (pointer) ve iki veriden oluşur

4 düğümü: 4 adet çocuk düğümü gösteren gösterici (pointer) ve üç veriden oluşur

Ekleme işlemini bir örnek üzerinden anlamaya çalışalım

50, 27, 97, 52, 19, 11, 111

Bu sırayla verilen değerleri sırasıyla ağaca ekleyelim:

İlk sayı olan 50’nin eklenmesi sonucunda ağaçta tek bir düğüm ve bu düğümde tek bir veri bulunuyor. Bu tip düğüme 2 düğümü ismi verilmektedir ve iki çocuğu da boştur (null).

İkinci eklenen değer 27’dir. Ağacımızda tek düğüm bulunduğundan ve bu düğüm 2 tipinde olduğundan, düğümde yeni değeri alacak yer bulunmaktadır. Bu yere yeni gelen değer yerleştirilir. Elbette düğümlerin içerisinde sıra bulunması gerektiği için, 27 değeri, 50 değerinin soluna yerleştirilmiştir. Bu kural bundan sonraki ekleme işlemlerinde de geçerli olacaktır. Yani düğüm içerisindeki değerler kendi aralarında sıralı olacak ve herhangi bir değerin solundaki çocuklarının değeri, kendi değerinden küçük ve sağındaki değeri kendi değerinden büyük olacaktır.

Ardından gelen ekleme değeri, 97’dir. Bu değer düğüme eklenince, aşağıdaki gibi bir yapı elde edilir:

Yukarıdaki bu yeni yapı, bizim 2-3-4 ağacımızdaki 4 tipindeki yapıdır ve kabul edilebilir bir durumdur. Ancak bir sayı daha eklenince yapı bozulacaktır. Nitekim sıradaki sayımız olan 52’nin eklendiğini düşünelim:

Şimdiye kadar öğrendiklerimize göre, yukarıdaki gibi bir yapı olması beklenir. Ancak yukarıdaki yapı 2-3-4 ağacı tarafından kabul edilemez (2,3 veya 4 tipinde bir düğüm değildir). Dolayısıyla bu yapının kabul edilir bir şekle indirgenmesi gerekir.

Yukarıdaki yeni şekilde, ağaç 50 ve 27 değerlerini taşıyan iki adet 2 tipinde düğüm ve bir adet 52 ve 97 değerlerini taşıyan 3 tipinde düğüme indirgenmiştir. Bu düğümlerin tamamı 2-3-4 ağacı tarafından kabul edilir düğümlerdir.

Ekleme işlemine 19 sayısı ile devam edelim.

Yukarıdaki şekilde görüldüğü üzere, 19 sayısı, 50’den küçük olduğu için kökteki bu değerin solundaki düğüme yerleştirilmiştir.

11 sayısı eklendikten sonra, bu sayı da daha önceden olduğu gibi, 50’nin solundaki düğüme sıralı olarak eklenir.

Benzer şekilde 111 sayısının eklenmesi de kök değerin sağına yapılır:

Son olarak ağacın 3 düğümü olarak taşıyamayacağı bir örneği göstermek için, örneğin 120 sayısını ağaca eklemeye çalışalım:

Normalde 120 sayısının ekleneceği yer, yukarıdaki şekilde gösterildiği gibi ağacın sağ koludur. Ancak bu durum 2-3-4 ağacı tarafından kabul edilemez çünkü herhangi bir düğüm yapısına uygun değildir.

Çözüm olarak daha önceden 52 sayısının eklendiği örnekte olduğu gibi düğümleri indirgiyoruz.

Bu işlemden sonra kök düğümünü güncelleyerek sonuçta çıkacak olan ağacı elde ediyoruz

Ağacımız son halinde 2-3-4 ağacı kurallarına uygun düğümlerden oluşmaktadır.