String Matching - Brute Force

Brute Force

String eşleştirme günümüzde sıkça kullanılan bir uygulamadır, neredeyse tüm yazılım ortamlarında arama, karşılaştırma vb. sistemler bulunmaktadır. Bu sistemler aradığımız şeyi bulmamızı kolaylaştırmakta ve bu sayede daha hızlı çalışabilmemizi sağlamaktadır. Örneğin bir e-kitapta özel bir konu arıyor olalım. Küçük bir yazında bu işlem çok zor olmasa da boyut arttıkça ilgilendiğimiz konuyu bulmak çile haline gelmektedir. Burada devreye string eşleştirme algoritmaları devreye girer. Bu algoritmalar sayesinde ilgilendiğimiz konu ile ilgili keyword’leri kullanarak yazın içinde arama yapabilir ve o konuya hızlı bir şekilde ulaşabiliriz. Burada 2 değişken söz konusudur; pattern ve text. Text içinde pattern’in aranacağı pattern’e eşit ya da daha büyük boyutta olan değişkendir, pattern ise text’in içinde bulmak istediğimiz string dizisidir. Bu eşleştirme işlemlerini yapabilmek için çeşitli farklılıklara sahip algoritmalar bulunmaktadır. Bunlardan en basit olan algoritma Brute Force algoritmasıdır.

Brute-Force String Eşleştirme Algoritması

En basit string eşleştirme algoritmasıdır. Pattern, text’in başından başlayacak şekilde sağa doğru kaydırılarak karşılaştırmalar yapılır. Karşılaştırma pattern’in son harfinden başlar ve eşleşme sağlandıkça pattern’in ilk harfine doğru kaydırılır. Eğer herhangi bir karakterde eşleşme sağlanmazsa pattern bir birim sağa kaydırılır ve aynı işlem ta ki tam eşlenme sağlanana kadar tekrar eder. Eşleşme sağlanamadan text’in sonuna gelirse pattern text’te yok demektir.

Text adında n karakterli ve pattern adında m karakterli (m<=n) stringler verilmiş olsun. Burada problem bu text’te aradığımız pattern’in olup olmadığını bulmaktır. Daha net söylemek gerekirse text’te karşımıza çıkan ilk eşleşmenin en soldaki karakterinin index’ini bulmak istiyoruz. t_i = p₀, … , t_i+j = p_j, … , t_i+m-1 = p_m-1:

           

Birden fazla string eşleşmesi yapılmak isteniyorsa, text’in sonuna gelene kadar aramaya devam edilebilir.

Brute-Force algoritması oldukça açıktır: pattern’i text’İn ilk m karakteri ile hizala ve karşılıklı denk gelen karakterleri ta ki m karakter eşleşene kadar sağdan sola doğru kaydır. Eşleşme bozulursa pattern’i bir sağ pozisyona kaydır ve karakter karşılaştırmalarına devam et. Eşleşmeyla karşılaşabileceğimiz son konum n-m konumudur. Bu konumdan sonra eşleşmeyi sağlayabilmek için yeterli karakter yoktur.

ALGORITHM BruteForceStringMatch(T [0..n − 1], P[0..m − 1])

//Implements brute-force string matching

//Input: An array T [0..n − 1] of n characters representing a text and

// an array P[0..m − 1] of m characters representing a pattern

//Output: The index of the first character in the text that starts a

// matching substring or −1 if the search is unsuccessful

for i ←0 to n − m do

j ←0

while j <m and P[j ]= T [i + j ] do

j ←j + 1

if j = m return i

return −1

Bu algoritma neredeyse her karakter karşılaştırmasında pattern’i kaydırıyor. Worst case’de ise durum daha kötü, algoritma kaydırmayı yapmadan önce m tane karakteri karşılaştırmak zorunda kalabilir ve bu n – m  + 1 kere gerçekleşebilir. Bu nedenle algoritma worst case’de m(n – m + 1) karakter karşılaştırması yapmaktadır bu da algoritmanın karmaşıklığının O(nm) olduğu anlamına gelir. Fakat çoğu karşılaştırmada çok az bir karşılaştırmadan sonra kaydırmanın gerçekleşmesi beklenir. Bu nedenle avarage-case’imiz worst-case’e göre oldukça iyi olmalıdır. Birçok text’te yapılan aramalar karmaşıklığın lineer yani Θ(n) olduğunu göstermiştir.

for i ←0 to n − m do

Bu for döngüsü sayesinde text’te karşılaştırma yapılacak noktalarda kaydırma sağlanıyor. Karşılaştırma text dizisinin 0. konumundan başlayıp n – m konumuna kadar devam ediyor. Daha ilerisinin kontrol edilmesine gerek yok çünkü pattern’in bulunabileceği yeterli uzunluk bu noktadan sonra kalmıyor.

while j <m and P[j ]= T [i + j ] do

Bu while döngüsü sayesinde karşılaştırılan karakterlerin eşlenik olup olmadığına bakılıyor eşlenikse bir sonraki karaktere bakılıyor, eşlenme bozulursa döngüden çıkılıyor. Eğer eşlenme bozulmadan tüm pattern textte bulunursa j değişkeni pattern’in boyutuna eşit hale geliyor.

if j = m

j değişkeninin pattern’in boyutuna eşit olması aradığımız substring’in textte bulunduğu anlamına geliyor. Daha sonra bu substring’in bulunduğu konumun indexini return i ile döndürüyoruz.

Eşleşme bulunamadan n – m konumuna gelirsek bu aradığımız pattern’in text’te olmadığı anlamına geliyor. Bu durumda methodumuz -1 değerini döndürüyor.

Bu algoritmanın basit olması tasarımı sırasında sorun çıkma olasılığını azaltmaktadır. Fakat bu durumda etkinlik de azalmaktadır.

C# dili ile uygulanmış hali:

/// <summary>

/// Brute-force yaklaşımı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 BruteForceMatching(string pattern, string text)

{

    for (int i = 0; i <= text.Length - pattern.Length; i++) //Text ve pattern boyutunun farkı kadar dön

   {

       int j = 0;

       while (j < pattern.Length && pattern[j] == text[i + j]) //Harfler eşitse

       {

          j++;

       }

       if (j == pattern.Length) //Karşılaştırma sayısı pattern boyutuna eşitse eşleşme vardır

       {

          return i; // Eşleşme konumunu döndür

       }

    }

    return -1;

}