Knuth–Morris–Pratt

Kaba kuvvet aramanın israfı, uyuşmazlıktan önce yapılan eşleşmeleri unutmasıydı. Rabin–Karp bu israfı karma ile azalttı ama örüntünün yapısını hiç kullanmadı.

Knuth–Morris–Pratt algoritmasının fikri şudur: eşleşen kısım zaten biliniyorsa, örüntünün kendi iç tekrarları kaç konumun güvenle atlanabileceğini söyler.

Gözlem

ABABCABAB örüntüsü metinle karşılaştırılırken ilk dört karakterin (ABAB) eşleştiği, beşincinin uyuşmadığı düşünülsün. Metnin o bölümünde ABAB olduğu kesin olarak bilinir.

Kaba kuvvet bir konum kayar ve metnin BAB… bölümünü baştan sınar. Oysa ABAB’ın AB öneki, aynı zamanda AB sonekidir; dolayısıyla iki konum kayarak örüntünün ilk iki karakterini yeniden sınamadan devam edilebilir. Ara konumlar denenmeye değmez, çünkü oradaki karakterlerin ne olduğu zaten biliniyor.

Genel kural: eşleşen önekin hem öneki hem soneki olan en uzun parça korunur, gerisi atılır.

Önek İşlevi

Önek işlevi $\pi$, örüntünün her öneki için “hem öz önek hem sonek olan en uzun parçanın uzunluğunu” verir. “Öz” burada parçanın tamamın kendisi olamayacağı anlamındadır.

def onek_islevi(oruntu: str) -> list[int]:
    """pi[i]: oruntu[0..i] parçasının en uzun öz önek-sonek uzunluğu."""
    pi = [0] * len(oruntu)
    k = 0
    for i in range(1, len(oruntu)):
        while k > 0 and oruntu[i] != oruntu[k]:
            k = pi[k - 1]                  # daha kısa bir aday öneke geri çekil
        if oruntu[i] == oruntu[k]:
            k += 1
        pi[i] = k
    return pi


print(onek_islevi("ABABCABAB"))       # [0, 0, 1, 2, 0, 1, 2, 3, 4]
print(onek_islevi("AABAACAABAA"))     # [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
print(onek_islevi("ABCDE"))           # [0, 0, 0, 0, 0]

Değerler doğrudan okunur: ABABCABAB örüntüsünün tamamının en uzun önek-sonek örtüşmesi 4’tür (ABAB), dördüncü karakterine kadarki ABAB parçasınınki 2’dir (AB), hiç tekrar içermeyen ABCDE için hepsi sıfırdır.

Hesabın kendisi, örüntüyü kendisinde aramaktır: k değişkeni o ana kadar eşleşen önek uzunluğunu tutar ve uyuşmazlıkta daha kısa bir adaya geri çekilir. Maliyet $O(m)$’dir — gerekçesi aramadakiyle aynıdır ve bir sonraki bölümde verilir.

Arama

Arama, aynı geri çekilme mantığını metin üzerinde uygular. Metin imleci hiçbir zaman geri gitmez; yalnızca örüntü imleci geri çekilir.

def kmp(metin: str, oruntu: str) -> tuple[list[int], int]:
    """(konumlar, karakter karşılaştırma sayısı)"""
    pi = onek_islevi(oruntu)
    konumlar: list[int] = []
    k = 0
    sayac = 0
    for i, karakter in enumerate(metin):
        while k > 0 and karakter != oruntu[k]:
            sayac += 1
            k = pi[k - 1]
        sayac += 1
        if karakter == oruntu[k]:
            k += 1
        if k == len(oruntu):
            konumlar.append(i - len(oruntu) + 1)
            k = pi[k - 1]                  # örtüşen sonraki geçişi kaçırma
    return konumlar, sayac


metin = "ABABDABACDABABCABAB"
oruntu = "ABABCABAB"
print(kmp(metin, oruntu))                  # ([10], 23)
print(kmp("ABABAB", "AB"))                 # ([0, 2, 4], 6)
print(kmp("A" * 30 + "B", "A" * 10 + "B")) # ([20], 51)

Son satır belirleyicidir: kaba kuvvetin 231 karşılaştırma yaptığı girdide KMP 51 yapar. Karesel davranış tamamen ortadan kalkmıştır.

Eşleşme bulunduktan sonra k = pi[k-1] ataması, örtüşen geçişlerin kaçırılmamasını sağlar. ABABAB içinde ABAB arandığında 0 ve 2 konumlarının ikisi de bulunur.

Maliyet

Önişleme $O(m)$, arama $O(n)$, toplam $O(n + m)$ — en kötü durumda. Ek alan $O(m)$’dir (önek işlevi tablosu).

Gerekçe amortize bir akıl yürütmedir; Karmaşıklık Hesaplama Yöntemi dersindeki toplam maliyet yöntemi burada doğrudan uygulanır.

k değişkeni her turda en çok bir artar; $n$ tur boyunca toplam artış en çok $n$’dir. İç döngünün her turu k’yi en az bir azaltır ve k hiç negatif olmaz. Dolayısıyla iç döngü toplam en çok $n$ kez çalışabilir. İç döngü tek tek bakıldığında $O(m)$ görünse de, tüm arama boyunca toplam maliyeti doğrusaldır.

Ölçüt	Kaba kuvvet	Rabin–Karp	KMP
Önişleme	Yok	$O(m)$	$O(m)$
En kötü arama	$O(nm)$	$O(nm)$	$O(n)$
Ek alan	$O(1)$	$O(1)$	$O(m)$
Metinde geri dönüş	Var	Yok	Yok

Son satır pratik bir sonuç doğurur: metin imleci geri gitmediği için algoritma, tamamı bellekte olmayan bir akış üzerinde çalışabilir. Karakterler geldikçe işlenir, geri sarma gerekmez.

Özdevinir Görünümü

Önek işlevi, aslında bir sonlu otomatın (finite automaton) sıkıştırılmış hâlidir. Durumlar “şu ana kadar örüntünün kaç karakteri eşleşti” bilgisini tutar; her karakter için bir geçiş tanımlanır ve son durum bir eşleşme bildirir.

Geçişler önceden hesaplanırsa, arama sırasında geri çekilme döngüsü de ortadan kalkar: her metin karakteri için tam olarak bir tablo okuması yapılır.

def otomat(oruntu: str, abece: str) -> list[dict[str, int]]:
    pi = onek_islevi(oruntu)
    m = len(oruntu)
    gecis: list[dict[str, int]] = [{} for _ in range(m + 1)]
    for durum in range(m + 1):
        for karakter in abece:
            if durum < m and karakter == oruntu[durum]:
                gecis[durum][karakter] = durum + 1      # ilerle
            elif durum == 0:
                gecis[durum][karakter] = 0              # başa dön
            else:
                gecis[durum][karakter] = gecis[pi[durum - 1]][karakter]
    return gecis


def otomatla_ara(metin: str, oruntu: str, abece: str) -> list[int]:
    gecis = otomat(oruntu, abece)
    m, durum = len(oruntu), 0
    konumlar: list[int] = []
    for i, karakter in enumerate(metin):
        durum = gecis[durum][karakter]
        if durum == m:
            konumlar.append(i - m + 1)
    return konumlar


print(otomatla_ara("ABABDABACDABABCABAB", "ABABCABAB", "ABCD"))    # [10]

Bedel bellektedir: tablo $O(m\sigma)$ yer kaplar ve abece büyükse bu ciddi bir maliyettir. Önek işlevi ise $O(m)$ yer kaplayıp aynı davranışı amortize olarak üretir. İki yaklaşım arasındaki seçim, abece büyüklüğü ile arama sıklığına bakılarak yapılır.

Dönemsellik

Önek işlevi, arama dışında bir bilgiyi de doğrudan verir: bir dizginin en küçük dönemini.

Uzunluğu $m$ olan bir dizgi için $p = m - \pi[m-1]$ değeri en küçük dönem uzunluğudur. $m$, $p$’ye tam bölünüyorsa dizgi o parçanın tekrarından oluşur.

def en_kucuk_donem(dizgi: str) -> tuple[int, bool]:
    pi = onek_islevi(dizgi)
    p = len(dizgi) - pi[-1]
    return p, len(dizgi) % p == 0


for ornek in ("ABABAB", "ABCABCABC", "ABCD", "AAAA"):
    print(ornek, en_kucuk_donem(ornek))

# ABABAB (2, True)
# ABCABCABC (3, True)
# ABCD (4, True)
# AAAA (1, True)

ABCD için dönem uzunluğun kendisidir: tekrar yoktur. Bu hesap, sıkıştırmada ve dizgi denkliği sorularında kullanılır; aynı tablo iki farklı işe yarar.

Özet

• KMP, eşleşen önekin önek–sonek örtüşmesini kullanarak uyuşmazlıkta kaç konumun atlanabileceğini belirler.
• Önek işlevi her önek için en uzun öz önek–sonek uzunluğunu verir ve $O(m)$’de hesaplanır.
• Aramada metin imleci hiç geri gitmez; yalnızca örüntü imleci geri çekilir.
• Toplam maliyet $O(n + m)$’dir; gerekçe, k değişkeninin toplam artışını sınırlayan amortize akıl yürütmedir.
• Metinde geri dönüş olmaması, algoritmayı akış verisi için uygun kılar.
• Aynı tablo, bir dizginin en küçük dönemini de verir.

Sonraki Adım

KMP, örüntüyü baştan sona eşleştirir ve metnin her karakterine en az bir kez bakar. Sonraki ders ters yönden eşleştiren bir yaklaşımı ele alacak: örüntünün sonundan başlayan karşılaştırma, uyuşmazlık anında metnin bazı karakterlerine hiç bakmadan atlamayı mümkün kılar ve pratikte doğrusalın altında davranış üretir.