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 t₁(c) – k formülü ile hesaplanır. Buradaki t₁(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 t₁(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 ( t₁(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 t₁(A) – 2 = 4 – 2 = 2 pozisyon kaydırırız.

t₁(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 d₁ bad-symbol kaydırma tablosundaki değer pozitifse t₁(c) – k, negatif veya sıfır ise de bu değer 1’dir. Bu aşağıdaki formül ile açıklanabilir.

d₁ = max{t₁(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 d₂ 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, d₂ bu prefix ile sonek arasındaki farktan yola çıkarak hesaplanır. Örneğin aşağıda ABCBAB pattern’i için tam bir d₂ 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 t₁(c) girdisini al. Burada c eşleşmeyi bozan karakterdir. k > 0 ise good-suffix tablosunda karşılık gelen d₂ 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 d₁ ve d₂ 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 t₁(K) = 6 yı bad-symbol tablosundan alır ve pattern’i d₁ = max{t₁(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 t₁(_) = 6 değerini bad-symbol tablosundan ve d₂ = 5 değerini de good-suffix tablosundan alır. Pattern’i bu iki değerden maksimum olanı kadar sağa kaydırır. Max{d₁, d₂} = 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 d₂ = 2 değerini de good-suffix tablosundan alır. Pattern max{d₁, d₂} = 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

}