KMP (Knuth Morris Pratt) Arama Algoritması

0
1576

Merhabalar bu yazımızda bir arama algoritması olan KMP( Knuth Morris Pratt ) Algoritmasından bahsedeceğim. Arama algoritmaları çeşitli özelliklere sahiptirler. Kimisi çok hızlı olması, kimisi hızdan ziyade doğruluk bakımından birbirlerinden farklılık göstermektedir. KMP algoritması ise dengede bir algoritmadır. Diğer arama algoritmalarının temelini oluşturur ve KMP tablosu olarak göreceğimiz tabloyu kullanmaktadır.

KMP’nin hedefinde aranılacak kelimenin metinde bulunup, bulunmadığına bakılır ve bu durumlarda neler yapılacağı vardır. Klasik arama yöntemlerinde bütün ihtimaller denenir ve sonuca varılması hedeflenir ancak bu durum uzun bir süre ve bellek kaybı anlamına gelmektedir. KMP ise bu ara işlemlerin bazılarını yapmayarak süreyi kısaltarak ve bellek kaybının önüne geçerek bir arama işlemi gerçekleştirir. Bu ara işlemleri yapmama durumunu aranacak olan kelimeden yola çıkarak hesaplar.

KMP Özellikleri

  • KMP algoritmasının çalışması için öncelikle ön işlem olarak bir KMP tablosu oluşturmak gerekmektedir.
  • Arama işlemini soldan sağa doğru yapar.
  • Ön işlem zaman karmaşıklığı yani tablo oluşturma işlemi O(m) , arama zaman karmaşıklığı ise O(m+n) olur.
  • Genellikle DNA gibi çok fazla farklı karakter bulundurmayan metinlerde arama çok hızlı iken , doğal konuşma dili tarzındaki metinlerde ise biraz yavaş kalmaktadır.
  • Araştırmalar sonucunda Türkçe dil yapısında İngilizce dil yapısına göre daha etkili sonuçlar verdiği hesaplanmıştır.

KMP Çalışma Yapısı

Bu işlemleri bir örnek üzerinden değerlendirirsek daha açıklayıcı olacağını düşündüğüm için bir örnek problem üzerinden ilerleyeceğim.

Öncelikle ön işlem aşamasını yapmamız gerekmektedir. Bu da tablo oluşturmamız anlamına geliyor. Bu yüzden bazı terimlere ve formüllere ihtiyacımız var.

Terimler
\(i=kelime\) \( işaretçisi\)
\(Shifting(kaydırma)=i-prefix[i]\)
\(prefix=ön\) \(ek\)
\(suffix=son\) \(ek\)\(pattern=\) \(aranacak\) \(kelime\)

Örnek Soru

  • “ACAACACAACABACA” metininde ACABACA kelimesini KMP algoritmasıyla bulunuz.

Tablo Oluşturma İşlemi

Adım-1

  • Kelime: ACABACA
  • i = 1 : A
  • Prefix : Yok
  • Suffix : Yok

SONUÇ: 0

i 1 2 3 4 5 6 7
Pattern[i] A C A B A C A
Prefix[i] 0

 


Adım-2

  • Kelime: ACABACA
  • i = 2 : AC
  • Prefix : A
  • Suffix : C

SONUÇ:0

i 1 2 3 4 5 6 7
Pattern[i] A C A B A C A
Prefix[i] 0 0

 


Adım-3

  • Kelime: ACABACA
  • i = 3 : ACA
  • Prefix : A , AC
  • Suffix : A , CA

SONUÇ:1(A)

i 1 2 3 4 5 6 7
Pattern[i] A C A B A C A
Prefix[i] 0  0  1

 

 


Adım-4

  • Kelime : ACABACA
  • i = 4 : ACAB
  • Prefix : A , AC , ACA
  • Suffix : B , AB , CAB

SONUÇ:0

i 1 2 3 4 5 6 7
Pattern[i] A C A B A C A
Prefix[i] 0  0  1  0

 


Adım-5

  • Kelime: ACABACA
  • i = 5 : ACABA
  • Prefix : A , AC , ACA , ACAB
  • Suffix : A , BA , ABA , CABA

SONUÇ:1(A)

i 1 2 3 4 5 6 7
Pattern[i] A C A B A C A
Prefix[i] 0  0  1  0 1

 


Adım-6

  • Kelime: ACABACA
  • i = 6 : ACABAC
  • Prefix : A , AC , ACA , ACAB , ACABA
  • Suffix : C , AC , BAC , ABAC , CABAC

SONUÇ:2(AC)

i 1 2 3 4 5 6 7
Pattern[i] A C A B A C A
Prefix[i] 0  0  1  0 1 2

 


Adım-7

  • Kelime: ACABACA
  • i = 7 : ACABACA
  • Prefix : A , AC , ACA , ACAB , ACABA , ACABCA
  • Suffix : A , CA , ACA , BACA , ABACA , CABACA

SONUÇ:3(ACA)

i 1 2 3 4 5 6 7
Pattern[i] A C A B A C A
Prefix[i] 0  0  1  0 1 2 3

 

Artık tablomuzu oluşturduğumuza göre ön işlem kısmı bitmiş ve arama bölümüne geçebiliriz.

Arama İşlemi

METİN A C A A C A C A A C A B A C A
A C A B A C A
–>1 A C A B A C A
–>1 A C A B A C A
–>2 A C A B A C A
–>2 A C A B A C A
  –>1 A C A B A C A

 

Bu arama işlemini de yaptıktan sonra aradığımız kelimeyi bulmuş oluyoruz. Yeşil olanlar eşleşmenin sağlandığı karakterler kırmızı olanlar ise hatalı eşleşmeleri temsil etmektedir. Birinci sütundaki okla gösterilmiş sayılar ise kaç karakter kayacağını göstermektedir. Bu kaydırma işlemini ise yukarıdaki tablo ve formüller sayesinde yapmaktayız.

Örnek C Kodu

#include <stdlib.h>
#include <string.h>

void failure(char* pattern, int* f);
int kmp(char* t, char* p);

int* init_array(int size) {
  int* arr = (int*)malloc(size * sizeof(int));
  int i;
  for(i = 0; i < size; i++) {
    arr[i] = 0;
  }

  return arr;
}

int main(void) {
  char* pattern = "abacab";
  char* text = "bbacbabcbabcbabbabcbabcbacbbbacbacbacbacbacbabacab";

  int match = kmp(text, pattern);

  printf("Match at: %d\n", match);

  return 0;
}

int kmp(char* t, char* p) {
  int m = strlen(p);
  int n = strlen(t);

  int* f = init_array(m); 
  int i = 0;
  int j = 0;

  while (i < n) {
    if (t[i] == p[j]) {
      if (j == m - 1) {
        return i - j;
      }
      else {
        i += 1;
        j += 1;
      }
    }
    else {
      if (j > 0) {
        j = f[j-1];
      }
      else {
        i += 1;
      }
    }
  }

  return -1;
}

void failure(char* p, int* f) {
  f[0] = 0;
  int i = 1;
  int j = 0;
  int m = strlen(p);
  while (i < m) {
    if (p[i] == p[j]) {
      f[i] = j + 1; // j+1 matches up to the current character.
      i += 1;
      j += 1;
    }
    else if (j > 0) {
      j = f[j - 1];
    }
    else {
      f[i] = 0;
      i += 1;
    }
  }
}

 

CEVAP VER

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.