KMP Dize Eşleştirme Algoritması Nedir?
KMP (Knuth-Morris-Pratt) algoritması, bilgisayar bilimlerinde bir metin (T) içinde belirli bir desenin (P) tüm görünümlerini verimli bir şekilde bulmak için kullanılan bir dize arama algoritmasıdır. Geleneksel ilkel yöntemlere göre daha hızlıdır, çünkü desenin kendisi hakkında önceden bilgi kullanarak gereksiz karşılaştırmaları önler.
KMP algoritması, desenin (P) ön ek-son ek özelliklerini analiz ederek oluşturulan bir ön işleme adımı (LPS dizisi) ile metin (T) içinde desen aramasını optimize eder. Bu ön işleme, eşleşme sırasında geri adım sayısını azaltarak algoritmanın hızını artırır.
Adım adım çözümlü örnekler
Metin T = "ABABDABACDABABCABAB" ve Desen P = "ABABCABAB" için KMP algoritmasını kullanarak deseni bulunuz.
1. LPS dizisini hesapla: P = "ABABCABAB" için LPS = [0, 0, 1, 2, 0, 1, 2, 3, 4]. 2. Metin üzerinde desen araması yap: LPS dizisini kullanarak eşleşmeleri takip et. Eşleşmeyen karakterlerde desenin LPS değerine göre kaydır. 3. Sonuç: Desen, metnin 10. indeksinden başlayarak bulunur.
Metin T = "AAAAABAAABA" ve Desen P = "AAAA" için KMP algoritmasını kullanın.
1. LPS dizisini hesapla: P = "AAAA" için LPS = [0, 1, 2, 3]. 2. Metin üzerinde desen araması yap: Eşleşme sırasında, desenin tamamı eşleştiğinde LPS dizisi kullanılarak sonraki olası eşleşme bulunur. 3. Sonuç: Desen, metnin 0. ve 1. indekslerinden başlayarak iki kez bulunur.
Bilgi kartları
Mini test
S1.KMP algoritmasının ön işleme adımı neyi hesaplar?
S2.LPS dizisinin amacı nedir?
S3.KMP algoritması hangi durumda en verimlidir?
Sık yapılan hatalar
KMP algoritması, her eşleşmeyen karakterde deseni hep bir pozisyon kaydırır. — Doğrusu: KMP algoritması, LPS dizisindeki bilgilere dayanarak deseni akıllıca kaydırır, bu da gereksiz karşılaştırmaları önler.
LPS dizisi, metnin kendisi üzerinde hesaplanır. — Doğrusu: LPS dizisi, yalnızca aranan desen (P) üzerinde hesaplanır.
Sıkça sorulan sorular
KMP algoritması 'greedy' bir algoritma mıdır?
Hayır, KMP 'greedy' bir algoritma değildir. 'Greedy' algoritmalar her adımda yerel olarak en iyi seçimi yaparken, KMP desenin yapısını analiz ederek daha global bir optimizasyon sağlar.
KMP algoritması 'boyutlu analiz' (dimensional analysis) ile ilgilimi midir?
Hayır, KMP dize eşleştirme ile ilgilidir ve boyutlu analizden farklı bir alana aittir. Boyutlu analiz genellikle fizik ve mühendislikte birimlerin tutarlılığını kontrol etmek için kullanılır.
KMP algoritması hangi durumlarda ilkel yöntemlerden daha kötü performans gösterebilir?
Genellikle KMP, ilkel yöntemlerden daha iyi performans gösterir. Ancak, desenin çok kısa olduğu ve metinde hiç tekrar eden yapı bulunmadığı çok özel durumlarda, ön işleme maliyeti nedeniyle fark belirgin olmayabilir veya çok az olabilir.