Knuth Morris Prat Algoritması (KMP Algorithm)

Yazan : Şadi Evren ŞEKER

Knuth-Morris-Prat algoritması bir kelimenin (yada bir metin parçasının) bir metin içerisinde aranmasını sağlayan algoritmadır. Basitçe bu algoritmada bir kelimenin aranan metinde bakılması ve bakıldığı yerde bulunamaması durumunda nerede olabileceği ile ilgili bir bilginin elde edilmesi hedeflenir.

Algoritma aranan kelimenin, aranan metinde bulunmaması durumunda, kelimenin içerisindeki harflerden yola çıkarak birden fazla ihtimali elemektedir.

Klasik bir metin arama işleminde aranan kelime metindeki bütün ihtimallerde denenir. (örneğin doğrusal arama (linear search) bu şekilde çalışır).  KMP algoritmasında ise aranan metindeki bütün ihtimaller denenmez. Bu durumu anlamak için bir örnek üzerinden algoritmayı inceleyelim:

KMP algoritmasının çalışması.

Örneğin metin olarak:

ŞABCDŞADEFABŞADI

Aranan kelime olarak da :

ŞADI

için KMP algoritmasının nasıl çalıştığını inceleyelim.

Öncelikle metin ve aranan kelime aşağıdaki şekilde ilk harflerinden karşılaştırılmaya başlanır:

ŞABCDŞADEFABŞADI

ŞADI

ilk iki harfin tutmasına karşılık 3. ve 4. harfler tutmamaktadır. Algoritma benzemeyen ilk harf olan 3. harfi bulunca geri kalanını benzetmeye çalışmaktan vaz geçer. Ayrıca bakmış olduğu harflerden hiçbirisi aradığı kelime olmadığı için metinde aradığı kelime boyu kadar kayarak yeniden arama yapar.

ŞABCDŞADEFABŞADI

    ŞADI

Yukarıdaki şekilde 4 harf kayarak D harfinden itibaren arama yapmaya başlar çünkü bir önceki aramada, ilk 4 harf arasında aranan kelimenin ilk harfi olan Ş harfinin bulunmadığını anlamış ve artık bu harflere bakmak gerekmediği sonucuna varmıştır.

4. harf olan D harfi ile başlayan metinde, aranan kelime olan ŞADI karşılaştırılmış ve görülmüştür ki metin uymmamaktadır. Ancak aranan metnin bir parçası olan ŞAD kısmı buradaki aranan harfler arasındadır. dolayısıyla algoritma bu sefer 1 harf kaydırarak ve Ş harflerini alt alta getirerek deneme yapar.

ŞABCDŞADEFABŞADI

     ŞADI

Karşılaştırma işlemi sonucunda ilk 3 harf tutmasına karşılık son harfte problem vardır ve karşılaştırılan harflerden hiç birisi aradığımız kelimenin baş harfi olan Ş ile başlamamaktadır. Bu durumda metinde 4 harf daha hareket edilerek bir sonraki karşılaştırma işlemi yapılır:

ŞABCDŞADEFABŞADI

         ŞADI

Karşılaştırmada başarı olmamasına karşılık son harf Ş harfidir ve dolayısıyla bu harfi yakalamak için 3 harf daha kaydırılır:

ŞABCDŞADEFABŞADI

            ŞADI

Bu kez başarı elde edilmiş ve aranan kelime bulunmuştur.

Yukarıdaki örnekte dikkat edilirse toplam 5 karşılaştırma işlemi yapılmıştır. Bu işlem doğrusal arama algoritması ile yapılsaydı 12 karşılaştırma gerekcekti. Bu anlamda KMP algoritmasının daha başarılı olduğu söylenebilir.

Algoritmanın performansı olarak O(n) değeri bulunabilir (n metnin boyutu olarak düşünülürse). Doğrusal arama ile aynı sonucun alındığı algoritma performansı için en kötü durum analizi yapıldığı ve en kötü durumda doğrusal arama ile aynı olacağı unutulmamalıdır.

Daha fazla bilgi için bir benzer algoritma olan boyer moore algoritmasına bakabilirsiniz.