hkucuk

Knuth-Morris-Pratt (KMP) Algoritması

21 Nisan 2023 • ☕️ 3 dk okuma • 🏷 bilgisayar, yazılım, arama

Yazar tarafından şu dillere çevrildi: English


Knuth-Morris-Pratt (KMP) algoritması, bir metin içinde verilen bir deseni (pattern) arama amacıyla kullanılan etkili bir dize arama algoritmasıdır. Özellikle büyük metinlerde veya metin koleksiyonlarında hızlı bir şekilde desen aramak için tercih edilen bir algoritmadır. KMP algoritması, özellikle veri sıkıştırma, metin düzenleme, veritabanı sorgulamaları ve genel olarak metin işleme alanlarında kullanılır.

KMP algoritmasının temel prensibi, normalde yapılan tüm karşılaştırmaları bir araya getirerek desen ve metin arasındaki ilişkileri kullanmaktır. Bu sayede gereksiz karşılaştırmaları önler ve daha hızlı bir arama sağlar. KMP algoritması, çalışma zamanı bakımından kötü durumlarda bile lineer zaman karmaşıklığına (O(m + n)) sahip olabilir, burada “m” desenin uzunluğunu, “n” metnin uzunluğunu ifade eder.

KMP algoritmasının çalışma adımları şunlardır:

  1. Deseni ve metni hazırla:

    • Desen: Aranacak dizeyi temsil eder.
    • Metin: Deseni içinde arayacağımız ana dizeyi temsil eder.

  2. Prefix Fonksiyonunu Hesapla:

    • Prefix fonksiyonu (veya başlangıç fonksiyonu), desen içindeki her bir pozisyona karşılık gelen en uzun önek (prefix) uzunluklarını hesaplar. Bu, desen içinde tekrar eden alt dizelerin tespit edilmesine yardımcı olur.

  3. Deseni Metin Üzerinde Kaydırarak Arama:

    • Deseni metin üzerinde sola doğru kaydırarak arama yapılır.
    • Eşleşen karakterlerde kayma yapılırken, eşleşmeyen karakterlerde prefix fonksiyonundan gelen bilgiler kullanılarak ilerleme sağlanır. Bu, gereksiz karşılaştırmaların önüne geçer.

Bu adımlar sayesinde KMP algoritması, desen-metin eşleştirmelerini hızlı bir şekilde bulabilir ve performansı artırabilir. KMP algoritması, Brute Force (Kaba Kuvvet) yöntemine göre daha hızlıdır ve genellikle büyük veri kümesinde dize aramak gerektiğinde tercih edilen bir çözümdür.

Karmaşıklık

  • Time: O(|m| + |n|)
  • Space: O(|m|)

GoLang’de Knuth-Morris-Pratt Algoritması uygulaması:

package main

import (
	"fmt"
)

func computePrefixFunction(pattern string) []int {
	length := len(pattern)
	prefixFunc := make([]int, length)
	
	prefixLen := 0
	i := 1
	
	for i < length {
		if pattern[i] == pattern[prefixLen] {
			prefixLen++
			prefixFunc[i] = prefixLen
			i++
		} else {
			if prefixLen != 0 {
				prefixLen = prefixFunc[prefixLen-1]
			} else {
				prefixFunc[i] = 0
				i++
			}
		}
	}
	
	return prefixFunc
}

func kmpSearch(text, pattern string) []int {
	prefixFunc := computePrefixFunction(pattern)
	
	textLen := len(text)
	patternLen := len(pattern)
	
	i, j := 0, 0
	indices := []int{}
	
	for i < textLen {
		if pattern[j] == text[i] {
			i++
			j++
		}
		
		if j == patternLen {
			indices = append(indices, i-j)
			j = prefixFunc[j-1]
		} else if i < textLen && pattern[j] != text[i] {
			if j != 0 {
				j = prefixFunc[j-1]
			} else {
				i++
			}
		}
	}
	
	return indices
}

func main() {
	text := "ababcababcabcabc"
	pattern := "abcabc"
	
	indices := kmpSearch(text, pattern)
	
	if len(indices) == 0 {
		fmt.Println("Desen metinde bulunamadı.")
	} else {
		fmt.Println("Desen metinde bulundu, başlangıç indeksleri:", indices)
	}
}

Bu örnek, KMP algoritmasının temel mantığını Go dilinde uygulamaktadır. computePrefixFunction fonksiyonu, desen için önek fonksiyonunu hesaplar. kmpSearch fonksiyonu ise KMP algoritmasının desen arama işlemini gerçekleştirir. main fonksiyonunda ise örnek bir metin ve desen üzerinde algoritma çalıştırılmış ve sonuçları yazdırmıştır. Bu kodu kullanarak istediğiniz metin ve desende KMP algoritmasını deneyebilirsiniz.

Program çalıştırıldığında çıktısı aşağıdaki gibi olacaktır.

Desen metinde bulundu, başlangıç indeksleri: [7 10]

Programın çalışır haline şuradan erişilebilir.

Kaynaklar