Bir diğer string arama algoritmalarından olan KMP algoritmasına bakacağız.

Örnek olarak;

txt =  "THIS IS A TEST TEXT"
pat = "TEST"
Output : 10

ve

txt =  "AABAACAADAABAAABAA"
pat = "AABA"
Output : 0, 9, 13

Bir önceki yazıda en kaba hali ile bir text içerisinde nasıl başka bir text aramasının yapılacağını incelemiştik. O algoritma O(m*(n-m+1)) karmaşıklığa sahipti. Bu algoritmanın en kötü durumda karmaşıklığı O(n)'dir.

KMP (Knuth Morris Pratt)

Kısaca yapılan iş şu şekilde yürümektedir. Ne zaman bir eşleşmeme duruöu olursa, elimizde daha önce elde ettiğimiz bilgileri kullanarak, deseni kaydırma ve benzetme işlemi yaparız. Dolayısı ile gereksiz karşılaştırmadan kaçtığımız için zaman karmaşıklığından kazanmış oluruz.

LPS için aşağıdaki örnelere bakın.

 “AABAACAABAA”, lps = [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
 “ABCDE”, lps = [0, 0, 0, 0, 0]
 “AAAAA”, lps = [0, 1, 2, 3, 4]
 “AAABAAA”, lps = [0, 1, 2, 0, 1, 2, 3]
 “AAACAAAAAC”, lps = [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

İşleyiş aşağıdaki kod ile daha iyi anlaşılacaktır.

 def KMP_search(text, pattern):
     lps = compute_lps_array(pattern)
     m, n, j = len(pattern), len(text), 0
     i = 0  # text indeksi
     while i < n:
         if pattern[j] == text[i]:
             i, j = i + 1, j + 1
         if j == m:
             print(i - j)
             j = lps[j - 1]
         elif i < n and pattern[j] != text[i]:
             # j eşleşme sonrası eşleşmeme
             if j != 0:
                 j = lps[j - 1]
             else:
                 i += 1


 def compute_lps_array(pattern):
     lps = [0] * len(pattern)
     # len_sp = son en uzun prefix suffix uzunluğu
     len_sp, i, len_pattern = 0, 1, len(pattern)

     while i < len_pattern:
         if pattern[i] == pattern[len_sp]:
             len_sp += 1
             lps[i] = len_sp
             i += 1
         elif len_sp != 0:
             len_sp = lps[len_sp - 1]
         else:  # len_sp == 0
             lps[i] = 0
             i += 1

     return lps

 if __name__ == '__main__':
     text = "ABABDABACDABABCABAB"
     pattern = "ABABCABAB"
     KMP_search(text, pattern)

Comments

comments powered by Disqus