4 Şubat 2013 Pazartesi

String Matching - Conclusions

Önceki postlarda üç farklı string matching algoritmasını inceledik ve bu algoritmaları implement ederek çeşitli durumlarda ortaya çıkan sonuçları gözlemledik. Bu gözlemler sayesinde algoritmaların etkinliklerini tespit etme şansını elde ettik. İncelediğimiz algoritmalar farklı etkinliklere ve karmaşıklıklara sahiptir. Aşağıda elde edilen sonuç bu konu hakkında daha detaylı bilgi vermektedir.

INPUT:

Text: Bu uygulamayı geliştirirken sizden beklediğimiz, .net (v_4.0) platformunda veritabanı olarak SQL kullanarak bir web uygulaması geliştirmeniz.

Aranan Pattern: "kullana"

OUTPUT:



Output verilerinden de anlaşılacağı gibi karşılaştırma sayısı açısından:

Brute-Force > Horspool > Boyer-Moore

İken çalışma zamanı açısından ise sonuçlar:

Boyer-Moore > Horspool > Brute-Force

Şeklindedir. Bu da algoritmaların etkinliklerinin artmasının her durumda işimize yaramadığını göstermektedir. Basit durumlarda basit algoritmaların kullanılması karşılaştırma sayısını arttırsa da karmaşıklığın az olması nedeniyle bu algoritmaların işlemesi daha kısa sürmektedir. Ayrıca bu algoritmalar karmaşık olmasının yanında daha fazla alan kullanmaktadırlar:

SBoyer-Moore>SHorspool>SBrute-Force

Fakat bu algoritmalar incelediğimiz text boyutlarının oldukça büyük olması durumunda ve text’in alfabesinin genişliğinin fazla olması durumunda işimize yaramaktadır. Böyle bir durumda Horspool ve Boyer-Moore gibi algoritmalar gereksiz karşılaştırmaların önüne geçerek kaydırma tablolarını oluşturmak için harcadığı zamanı ileride bu şekilde kurtarabilmektedir. Bu nedenle bu tür alanlarda daha etkin algoritmalar olan Horspool ve Boyer-Moore gibi algoritmaların kullanılması daha uygun olmaktadır.

String Matching - Boyer-Moore Algorithm


Boyer-Moore Algorithm

Bu algoritma Horspool algoritmasının geliştirilmiş halidir. Karşılaştırma yaptığımız pattern’in son karakterinin eşleştirilmesi başarısız olursa Horspool algoritmasındaki işlemin aynısı gerçekleştirilir. Fakat herhangi bir sayıda eşleşme olduktan sonra eşleşme başarısız olursa Horspool algoritmasından farklı davranır. Burada iki tablo ortaya çıkmaktadır. Horspool’dan gelen bad symbol shift ve farklı olarak gelen good-suffix shift. Boyer-Moore algoritması bu iki tabloyu değerlendirir ve bu tablolarda karşılık gelen değerlerden maksimum kaydırmayı sağlayacak olan durumu seçer. Bu seçim sayesinde Horspool algoritmasına göre daha büyük bir kayma sağlama şansı doğar.

Bu algoritmalar farklı karmaşıklıklara, çalışma zamanına ve alan kullanımına sahiptir. Bu nedenle bu algoritmalar belirli durumlarda diğerlerine göre daha etkin olabilmektedir.

String eşleştirme algoritmaları günümüzde birçok alanda kullanılmaktadır. Internet ve masaüstü uygulamaları, ofis uygulamaları, oyunlar vb. alanlarda kısaca tüm yazılım uygulamalarında string eşleştirme algoritmalarını kullanmaktayız. Bir programda Ctrl+F’e basarak ya da arama seçeneğine bir kelime girerek arama yaptığımızda bu algoritmalar kullanılmaktadır. Bu nedenle bu algoritmaların önemi bizim için büyüktür. Bu algoritmalar işlemlerimizi hızlandırır fakat bazı durumlarda bu işlem istediğimiz kadar hızlı gerçekleşmeyebilir. Bu nedenle farklı algoritmaların geliştirilmesiyle string eşleştirme işlemlerinin daha hızlı olması sağlanmaya çalışılmıştır.

Bu kısımda Boyer-Moore algoritmasını daha detaylı bir şekilde anlatacağız. Pattern’in en sağındaki karakterin text’teki ona karşılık konumdaki c karakteri ile eşleşmesi başarısız olursa, bu algoritma Horspool algoritması ile aynı şeyi yapmakdır. Önceden anlatıldığı şekilde tablodan elde edilen karakterlerin sahip oldukları değerler kadar pattern sağa kaydırılır.

İki algoritma k sayıda başarılı eşleştirmeden sonra(0 < k < m) eşleşmenin bozulması durumunda farklı davranırlar:
Bu durumda Boyer-Moore algoritması iki değişkene göre nasıl kaydırma yapacağına karar verir. İlki eşleşmenin bozulmasına neden olan text’teki c karakterinin karşısına denk gelen pattern’deki karakter ile belirlenir. Buna bad-symbol kaydırması denir. Bu kaydırmanın nedeni Horspool algoritmasındaki ile aynı nedendir. C karakteri pattern’de yoksa pattern’i c karakterini geçecek kadar sağa kaydırırız. Bu kaydırma t1(c) – k formülü ile hesaplanır. Buradaki t1(c) HHorspool algoritması kullanılarak hesaplanan tablodaki değerdir ve k da eşleştirilen karakter sayısıdır:
Örneğin bir text’te BARBER kelimesini ararsak ve text’teki S karakterinde eşleşme bozulana kadar son iki karakterde eşleşme sağlanacaktır. Pattern’i t1(S) – 2 = 6 – 2 = 4 pozisyon kaydırabiliriz:


Aynı formül eşleşmenin bozulmasına neden olan karakterin pattern’de bulunması durumunda da kullanılır ( t1(c) – k > 0). Örneğin bir text’te BARBER kelimesini ararsak ve A karakterinde eşleşme bozulana kadar ilk iki karakter eşleşmiştir. Bu durumda pattern’i t1(A) – 2 = 4 – 2 = 2 pozisyon kaydırırız.


t1(c) – k < 0 olması durumunda patterni 0 ya da negatif konumda kaydırmayacağımız kesindir. Bu durumda brüte-force taktiğindeki gibi pattern’i bir konum sapa kaydırabiliriz.

Özetlemek gerekirse Boyer-Moore algoritması ile hesaplanan d1 bad-symbol kaydırma tablosundaki değer pozitifse t1(c) – k, negatif veya sıfır ise de bu değer 1’dir. Bu aşağıdaki formül ile açıklanabilir.
d1 = max{t1(c) – k, 1}.
İkinci kaydırma türü pattern’deki son k > 0 başarılı eşleştirme ile belirlenmektedir. Pattern’deki k boyutundaki sonekleri suff(k) ile gösteriyoruz. Bu tip kaydırmaya da good-suffix kaydırma denmektedir. Bad-shift’te tek bir c karakterinin neden olduğu kaydırma burada 1 den m -1 e kadar olan soneklerin boyutlarının good-suffix kaydırma tablosunu doldurması ile gerçeklemektedir.

Öncelikle suff(k)’nın pattern’de başka bir konumda da olduğu durumu ele alalım. Bu durumda pattern’i d2 boyutu kadar yani suff(k)’nın sağdan 2. kez yer aldığı konum arasındaki ile en sağda yer aldığı konum arasındaki fark kadar kaydırırız. Örneğin ABCBAB patterni için bu uzaklıklar k = 1 ve 2 için 2 ve 4 olacaktır:


Suff(k) değeri eğer pattern’de başka bir konumda yoksa ne yapılacak? Çoğu durumda pattern’i boyutu kadar kaydırabiliriz. Örneğin DBCBAB patterni ve k = 3 için, pattern’i boyutu olan 6 değeri kadar kaydırabiliriz.
Fakat bu durumda pattern’i boyutu kadar kaydırmak her zaman doğru adım olmayabilir. Örneğin ABCBAB ve K = 3 değeri için pattern’i 6 kaydırmak text’te AB ile başlayan substringlerin pattern’in son 2 karakteri ile eşleşmesi durumunun gözden kaçırılmasına neden olabilir:

6 kaydırma işlemi DBCBAB için doğru fakat ABCBAB için doğru değil, çünkü ikinci pattern aynı AB substring’ine prefix ve suffix olarak sahiptir. K boyutunda soneke dayanan kaydırmalarda böyle bir durumdan kaçınmak için l boyutundaki aynı sonek ile uyuşan l < k boyutundaki en uzun prefixi bulmalıyız. Eğer böyle bir prefix varsa, d2 bu prefix ile sonek arasındaki farktan yola çıkarak hesaplanır. Örneğin aşağıda ABCBAB pattern’i için tam bir d2 değeri listesi bulunmaktadır.
Şimdi Boyer-Moore algoritmasını özetlemek gerekirse:

The Boyer-Moore algorithm

Adım 1 Verilen pattern ve text için bad-symbol kaydırma tablosunu oluştur.
Adım 2 Pattern’i kullanarak good-suffix kaydırma tablosunu oluştur.
Adım 3 Pattern’i text’in başlangıcı ile hizala.
Adım 4 Aşağıdaki işlemleri pattern’i text’te bulana kadar ya da text’in sonuna ulaşana kadar yap. Patterndeki son karakterden başlayarak texteki ve patterndeki denk gelen karakterleri m sayıda eşleştirme sağlanana kadar ya da k >= 0 sayıda eşleşme sağladıktan sonra eşleşmeyi bozan bir duruma denk gelene kadar karşılaştır. İkinci durumda bad-symbol tablosundaki c kolonundan t1(c) girdisini al. Burada c eşleşmeyi bozan karakterdir. k > 0 ise good-suffix tablosunda karşılık gelen d2 girdisini al. Pattern’i aşağıdaki formülden elde edilen şekilde kaydır:

k > 0 iken iki olası kaydırmadan maksimum olanı almak mantıklıdır. Bu iki kaydırma gözlemlere dayanmaktadır. Birincisi eşleşmeyi bozan karakter diğeri de pattern’in en sağdaki karakterlerinin eşleşen grubu hakkındadır. Bu da demektir ki pattern’i d1 ve d2 den daha az kaydırırsak herhangi bir eşleşme sağlayamayacağımız bir duruma gelmiş olacağımız kesindir. Amacımız pattern’i kayıpsız bir şekilde en büyük boyutta kaydırmak olduğu için bu iki sayıdan büyük olanı alırız.

ÖRNEK BAOBAB pattern’inin İngilizce karakterlerden ve space’den oluşan bir text’te arayalım. Bad-symbol kaydırma tablosu aşağıdaki gibidir:
Good-suffix tablosu da şu şekildedir:
Patterndeki B karakterinin textteki K karakteri ile karşılaştırmasısı olumsuz olacağı için algoritma t1(K) = 6 yı bad-symbol tablosundan alır ve pattern’i d1 = max{t1(K) – 0, 1} = 6 kadar sağa kaydırır. Yeni deneme iki karakteri başarılı bir şekilde eşleştirir. 3. Karakterdeki başarısızlıktan sonra algoritma t1(_) = 6 değerini bad-symbol tablosundan ve d2 = 5 değerini de good-suffix tablosundan alır. Pattern’i bu iki değerden maksimum olanı kadar sağa kaydırır. Max{d1, d2} = max { 6 – 2, 5} = 5. Bu durumda good-suffix tablosu daha ileri bir noktaya kaydırma yapmamızı sağlamıştır.

Sıradaki deneme B karakterini eşleştirir. Fakat boşluk karakteri nedeniyle eşleşme bozulur. Algoritma t1(_) = 6 değerini bad-shift tablosundan ve d2 = 2 değerini de good-suffix tablosundan alır. Pattern max{d1, d2} = max { 6 – 1, 2} = 5 kadar sağa kaydırılır. Bu durumda bad-shift tablosu daha ileri gitmemizi sağlamıştır. Son deneme de pattern’i text’te 6 tane başarılı karşılaştırmadan sonra bulur.
Pattern’in ilk bulunduğu noktayı tespit etmek için Boyer-Moore algorimasının worst-case etkinliği lineerdir. Bu algoritma özellikle geniş alfabelerde oldukça hızlıdır.  Birçok insan doğal dil benzeri stringlerde bu algoritmanın daha basit sürümerini tercih eder. Ör: Horspool.

/// <summary>
/// Bad-shift tablosunu oluşturur
/// </summary>
/// <param name="pattern">Text'te aranacak kelime</param>
/// <returns>BadShift tablosunu döndürür</returns>
private static int[] BuildBadCharacterShift(string pattern)
{
     int[] badCharacterShift = new int[352];

     for (int c = 0; c < badCharacterShift.Length; ++c) //Her karaktere pattern lenght'ini ata
         badCharacterShift[c] = pattern.Length;
     for (int i = 0; i < pattern.Length - 1; ++i) //Patternde olan karakterlere sondan başlayarak karşılaşılan ilk konuma göre shift değerini ata
        badCharacterShift[pattern[i]] = pattern.Length - i - 1;

    badShift = badCharacterShift;
    return badCharacterShift; //BadShift tablosunu döndür
}

Burada Horspool algoritmasındaki kaydırma tablosuna benzer şekilde bad-shift tablosu oluşturuluyor.

private static int[] FindSuffixes(string pattern)
{
    int f = 0, g;

    int patternLength = pattern.Length;
    int[] suffixes = new int[pattern.Length + 1]; //Sonek dizisi initialize ediliyor

    suffixes[patternLength - 1] = patternLength; //Son elemana patterin boyutu atanıyor
    g = patternLength - 1;
    for (int i = patternLength - 2; i >= 0; --i) //Pattern boyutu - 1 kadar dönülüyor
    {
       if (i > g && suffixes[i + patternLength - 1 - f] < i - g) //Karakter patternde tekrar ediyor mu
           suffixes[i] = suffixes[i + patternLength - 1 - f];
       else
       {
           if (i < g)
               g = i;
           f = i;
       while (g >= 0 && (pattern[g] == pattern[g + patternLength - 1 - f])) //Karakter kendinden önceki karakterle eşitse
       --g;
       suffixes[i] = f - g; //Farkı tabloya ata
       }
    }

    return suffixes; //Sonek tablosunu döndürüyor
}
Bu algoritma sayesinde good-suffix tablosunun oluşturulmasında kullanılacak sonekleri belirliyoruz.

/// <summary>
/// Good-shift tablosunu oluşturur
/// </summary>
/// <param name="pattern">Text'te aranacak kelime</param>
/// <param name="suff">Sonek tablosu</param>
/// <returns>GoodShift tablosunu döndürür</returns>
private static int[] BuildGoodSuffixShift(string pattern, int[] suff)
{
    int patternLength = pattern.Length;
    int[] goodSuffixShift = new int[pattern.Length + 1];

    for (int i = 0; i < patternLength; ++i) //Tüm elemanlara pattern boyutunu ata
         goodSuffixShift[i] = patternLength;
    int j = 0;
    for (int i = patternLength - 1; i >= -1; --i)
        if (i == -1 || suff[i] == i + 1) //Karakter dizisi tekrar ediyor mu?
             for (; j < patternLength - 1 - i; ++j)
                 if (goodSuffixShift[j] == patternLength) //Daha düşük sonuç varsa ata
                     goodSuffixShift[j] = patternLength - 1 - i;
             for (int i = 0; i <= patternLength - 2; ++i) //Tabloyu doldur
                 goodSuffixShift[patternLength - 1 - suff[i]] = patternLength - 1 - i;

    goodShift = goodSuffixShift;
    return goodSuffixShift; //GoodShift tablosunu döndür
}
Good-suffix algoritması değişken olarak pattern ve suff[]’ı alıyor. Bu değerleri kullanarak good-suffix tablosu belirleniyor.


private static int BoyerMooreMatching(string pattern, string text)
{
     int[] m_badCharacterShift = BuildBadCharacterShift(pattern); //Bad-shift tablosunu oluşturan methodu çağır
     int[] m_suffixes = FindSuffixes(pattern);
            int[] m_goodSuffixShift = BuildGoodSuffixShift(pattern, m_suffixes); //Good-shift tablosunu oluşturan methodu çağır

            int index = 0;

            while (index <= textLength - patternLength) //Text'in karşılaştırılacak son noktasına gelinmediyse
            {
                int unmatched;
                for (unmatched = patternLength - 1; //Key comparison
                  unmatched >= 0 && (pattern[unmatched] == text[unmatched + index]);
                  --unmatched
                )
                if (unmatched < 0) //Pattern bulunduysa
                {
                    return index; //Eşleşme konumunu döndür
                }
                else //Eşleşme sağlanamadıysa good ve bad shift tablolarındaki max değere göre indexi kaydır
                    index += Math.Max(m_goodSuffixShift[unmatched],
                      m_badCharacterShift[text[unmatched + index]] - patternLength + 1 + unmatched);
      }
      return -1; //Eşleşme yoksa
}

21 Ocak 2013 Pazartesi

String Matching - Horspool's Algorithm


Horspool’s Algorithm

Bu konuda brute force string matching algoritmasına alternatif olarak kullanabilecek daha etkin bir algoritma olan Horspool Algoritması açıklanmaktadır.

Brute-Force’a benzer şekilde pattern’in son harfinden başlanarak soldan sağa doğru pattern ve text’te karşılıklı denk gelen harfler karşılaştırılır. Eğer pattern’deki tüm karakterlerin eşleşmesi sağlanırsa substring 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 herhangi bir eşleşmeyi kaçırma olasılığını riske atmadan yapabileceğimiz en büyük olası kaydırmayı yapmak isteriz. Horspool algoritması burada pattern’in son karakterine karşılık gelen (c) karakterine bakarak kaydırma yapar. Burada dört olasılık söz konusudur. Bu durumlardan ilerideki sayfalarda bahsedilecek.

BARBER pattern’ini bir text’te aradığımızı düşünelim.
Pattern’in son elemanı olan R ile başlayarak sağdan sola doğru hareket ediyoruz ve text ile pattern’de karşılık gelen karakterleri karşılaştırıyoruz. Eğer pattern’deki karakterlerin tümü eşleşirse substring bulunmuş demektir.

Eşleşme olmazsa pattern’i sağa kaydırmamız gerekir. Bu durumda herhangi bir eşleşmeyi kaçırma olasılığını riske atmadan yapabileceğimiz en büyük olası kaydırmayı yapmak isteriz. Horspool algoritması burada pattern’in son karakterine karşılık gelen (c) 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şılaştı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 ve o son karakter değilse örn. örnekteki B harfi. Kaydırma c harfinin patternde görüldüğü en sağ noktaya denk gelecek şekilde gerçekleştirilmelidir, bu şekilde patterndeki c harfi ile text’teki c harfi eşleşmiş olur ve diğer karakteler de eşit mi diye bakılır.


Durum 3: c karakteri patterndeki son karakterse fakat pattern’in diğer m – 1 karakterinde bu c karakteri yoksa örn. örnekteki R harfi. Bu durumda, Durum 1’e benzer şekilde pattern boyutu kadar kaydırma yapılır.


Durum 4: c karakteri patterndeki son karakterse ve pattern’in diğer m – 1 karakterinde bu karakter tekrar ediyorsa örn. örnekteki R harfi. Bu durumda, Durum 2’ye benzer şekilde patternde c’nin bulunduğu en sağ konuma göre kaydırma yapılır. Bu sayede text’teki c karakteri ile pattern’deki aynı karakter hizalanmış olur.


Bu örnek sağdan sola şeklinde gerçekleştirilen karakter karşılaştırmalarının brute-force 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 getiriyor. Kaydırma boyutlarını önceden hesaplayıp bir tabloya atabiliriz. Tablo text’te karşımıza çıkabilecek tüm olası karakterleri içerecektir; doğal dil text’leri için boşluk, noktalama işaretleri ve diğer özel karakterler gibi. Tablo, folmül ile bulunan kaydırma boyutunu gösterecektir.

Örneğin BARBER pattern’i için, E, B, R ve A karakterleri sırasıyla 1, 2, 3 ve 4 olacaktır. Diğer tüm tablo girdileri 6’ya eşit olacaktır.

Aşağıda kaydırma tablosunun hesaplanması için basit bir algoritma verilmiştir. Tablodaki tüm girdileri pattern’in boyutu olan m değeri başlangıç değeri olarak yüklenir ve pattern soldan sağa doğru devamındaki aşamayı m – 1 kere tekrar edecek şekilde taranır; patterndeki j. karakter için (0 <= j <= m – 2) onun tablodaki girdisini m – 1 – j ile değiştir. Bu da karakterin pattern’in son karakterine olan uzaklığıdır. Algoritma pattern’i soldan sağa taradığı için son üstüne yazma en sağdaki karakterde gerçekleşecektir.

ALGORITHM ShiftTable(P [0..m 1])
//Fills the shift table used by Horspool’s and Boyer-Moore algorithms
//Input: Pattern P[0..m 1] and an alphabet of possible characters
//Output: Table[0..size 1] indexed by the alphabet’s characters and
// filled with shift sizes computed by formula
for i 0 to size 1 do Table[i]m
for j 0 to m 2 do Table[P[j ]]m 1j
return Table


Algoritmayı şu şekilde özetleyebiliriz:

Adım 1 Verilen m boyutlu pattern ve pattern ve text’te kullanılan alfabe için kaydırma tablosunu yukarda anlatıldığı gibi oluştur
Adım 2 Pattern’i text’in başına hizala
Adım 3 Bunu eşleşen bir substring bulana kadar ya da text’in sonuna gelene kadar tekrarla. Tüm m karakteri eşleşene kadar ya da eşleşme bozulana kadar pattern’deki son karakterden başlayarak, pattern’de ve text’de denk gelen karakterleri karşılaştır. Eşleşme bozulursa c karakteri için kaydırma tablosunda denk gelen sayıyı al ve pattern’i bu sayı kadar sağa kaydır.

ALGORITHM HorspoolMatching(P [0..m 1], T [0..n 1])
//Input: Pattern P[0..m 1] and text T [0..n 1]
//Output: The index of the left end of the first matching substring
// or 1 if there are no matches
ShiftTable(P [0..m 1])          //generate Table of shifts
i m 1                                //position of the pattern’s right end
while i n 1 do
k0                            //number of matched characters
while k m 1 and P[m 1k]= T [i k] do
kk + 1
if k = m return i m + 1
else i i + Table[T [i]]
return 1

ÖRNEK Horspool algoritmasının tam uygulamasına örnek vermek gerekirse; İngilizce harflerden ve boşluktan(alt çizgi ile gösterilen) oluşan bir text’te BARBER kelimesini arayacak olalım. Öncelikle kaydırma tablosunu önceden belirttiğimiz formül ile aşağıdaki gibi doldururuz.

Arama işlemi ise aşağıdaki gibi gerçekleşir.

Horspool algoritmasının worst-key etkinliği O(nm)’dir. Fakat rastgele textler için bu karmaşıklık Θ(n)’dir ve brute-force sınıfı ile aynı 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 sayılır.

C# dili ile uygulanmış hali:

/// <summary>
/// Horspool algoritması için shift tablosunu oluşturur
/// </summary>
/// <param name="text">Kontrol edilecek text</param>
/// <param name="pattern">Text'te aranacak kelime</param>
/// <returns>Shift tablosuna uygun verileri atar</returns>
private static void ShiftMyTable(string pattern, string text)
{
   bool baskaVar = false;
           
   ShiftTable = new Hashtable(); // Tablo initialize edilir
   for (int i = 0; i < text.Length; i++)
   {
       if (!ShiftTable.ContainsKey(text[i])) //Text'teki değişken tabloya daha önceden eklenmemişse
       {
           if (!pattern.Contains(text[i].ToString())) //Text'teki harf patternde yoksa
               ShiftTable.Add(text[i], pattern.Length); //O harf için pattern'in lenght'ini tabloya yaz
           else
           {//Text'teki harf patternde varsa
               for(int j = pattern.Length - 2; j >= 0; j--)
               {
                  if (pattern[j] == text[i])
                  {
                      baskaVar = true;
                      ShiftTable.Add(text[i], pattern.Length - j - 1); //Sondan başlayarak o harfin patterndeki konumuna göre tabloya değeri atar
                      break;
                  }
               }
               if (baskaVar == false)
                  ShiftTable.Add(text[i], pattern.Length);
               else
                  baskaVar = false;}}}}

Yukarıdaki algoritma Horspool Algoritması için kullanılan kaydırma tablosunu oluşturan algoritmanın C#’ta implement edilmiş halidir. Bu method parametre olarak pattern ve text değişkenlerini almaktadır.

for (int i = 0; i < text.Length; i++)
Text’teki tüm karakterler için kaydırma değeri belirleniyor.

if (!ShiftTable.ContainsKey(text[i]))
Text’teki karakter daha önceden tabloya eklenmişse tekrar eklenmesi gerekmemesi için kullanılan koşul.

if (!pattern.Contains(text[i].ToString()))
Eğer text’teki karakter patternde yoksa o karakter için tabloda m değeri yani pattern’in boyutu atanmaktadır. Karakter patternde varsa karakterin konumunu sağdan başlayarak hesaplıyoruz ve bulduğumuz değer karakterin kaydırma tablosundaki değer oluyor.

/// <summary>
/// Horspool algoritmasını kullanarak verilen text'te pattern eşleşmesi olup olmadığını bulur ve eşleşme varsa eşleşmenin konumunu döndürür
/// </summary>
/// <param name="text">Kontrol edilecek text</param>
/// <param name="pattern">Text'te aranacak kelime</param>
/// <returns>Pattern eşleşmesinin konumunu döndürür</returns>
private static int HorspoolMatching(string pattern, string text)
{

      ShiftMyTable(pattern, text); //Shift tablosunun hesaplanması için method çağrılıyor
      int i = pattern.Length - 1;
      while (i <= text.Length - 1) //index lenght'ten kısa ise döngüye giriliyor
         {
            int k = 0;
            while (k <= pattern.Length - 1 && pattern[pattern.Length - 1 - k] == text[i - k]) //Key comparison; karşılaştırılan harfler eşitse girilir
            {
                k++;
            }
            if (k == pattern.Length) //Pattern bulunduysa
            {
               return i - pattern.Length + 1; //Eşleşmenin konumu döndürülüyor
            }
            else
            {
               i = i + Convert.ToInt32(ShiftTable[text[i]].ToString()); // Eşleşme olmadıysa shift tablosuna göre index shift ediliyor
            }}
      return -1; //pattern eşleşmesi yoksa -1 döndürülüyor
}

Algoritma parametre olarak pattern ve text’i alıyor. 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 pattern kaydırma tablosuna göre sağa kaydırılıyor ve karşılaştırmaya devam ediliyor.