Rabin–Karp

Kaba kuvvet arama, her pencerede karakterleri tek tek karşılaştırıyordu. Bu dersin fikri karşılaştırmayı bambaşka bir işleme çevirir: metnin her penceresini bir sayıya indirgemek ve sayıları karşılaştırmak.

Sayı karşılaştırması tek işlemdir. Sorun, her pencerenin sayısını hesaplamanın $O(m)$ sürmesidir — bu hâliyle hiçbir kazanç yoktur. Çözüm, sayıyı sıfırdan hesaplamamak.

Yuvarlanan Karma

Pencere bir karakter sağa kaydığında, yeni karma değeri eskisinden sabit sayıda işlemle elde edilebiliyorsa yönteme yuvarlanan karma (rolling hash) denir.

Kullanılan karma, karakterleri bir sayı tabanının basamakları gibi ele alır. Taban $b$ ve asal modül $q$ için, uzunluğu $m$ olan bir pencerenin değeri:

$$H = \left(\sum_{i=0}^{m-1} s_i \cdot b^{\,m-1-i}\right) \bmod q$$

Pencere sağa kaydığında en soldaki karakterin katkısı çıkarılır, kalan bir basamak kaydırılır ve yeni karakter eklenir:

$$H' = \big((H - s_{\text{sol}} \cdot b^{\,m-1})\cdot b + s_{\text{yeni}}\big) \bmod q$$

Üç işlem, uzunluktan bağımsız: güncelleme $O(1)$’dir.

Gerçekleştirim

def rabin_karp(metin: str, oruntu: str,
               taban: int = 256, modul: int = 1_000_003) -> tuple[list[int], int, int]:
    """(konumlar, karma eşleşmesi sayısı, doğrulanan karakter sayısı)"""
    n, m = len(metin), len(oruntu)
    if m > n:
        return [], 0, 0

    ust = pow(taban, m - 1, modul)          # b^(m-1) mod q
    karma_o = karma_m = 0
    for i in range(m):                      # ilk pencere ve örüntü
        karma_o = (karma_o * taban + ord(oruntu[i])) % modul
        karma_m = (karma_m * taban + ord(metin[i])) % modul

    konumlar: list[int] = []
    esleme, dogrulama = 0, 0
    for kaydirma in range(n - m + 1):
        if karma_m == karma_o:              # aday: karmalar eşit
            esleme += 1
            dogrulama += m
            if metin[kaydirma:kaydirma + m] == oruntu:
                konumlar.append(kaydirma)
        if kaydirma < n - m:                # pencereyi yuvarla
            karma_m = (karma_m - ord(metin[kaydirma]) * ust) % modul
            karma_m = (karma_m * taban + ord(metin[kaydirma + m])) % modul
    return konumlar, esleme, dogrulama


metin = "ABABDABACDABABCABAB"
oruntu = "ABABCABAB"
print(rabin_karp(metin, oruntu))          # ([10], 1, 9)
print(rabin_karp("ABABAB", "AB"))         # ([0, 2, 4], 3, 6)

Metnin on bir penceresinden yalnızca biri karma sınamasını geçer ve doğrulama için dokuz karakter okunur. Kaba kuvvetin aynı girdide yaptığı 29 karşılaştırmayla karşılaştırılınca fark görünür.

Python’un negatif sayılarda kalan işlemi negatif olmayan sonuç ürettiği için ara değerler düzeltme gerektirmez; sabit genişlikli tam sayı kullanan dillerde çıkarma sonrası modül düzeltmesi eklenir. Bilgisayarlar Nasıl Çalışır kursundaki işaretli aritmetik farkı burada somut bir hataya dönüşebilir.

Çakışma ve Doğrulama

Karma eşitliği, dizilerin eşit olduğunu kanıtlamaz. Farklı diziler aynı değere düşebilir — Veri Yapıları kursundaki çakışma kavramının aynısı.

Bu yüzden her karma eşleşmesi karakter karşılaştırmasıyla doğrulanır. Doğrulama olmadan algoritma yanlış sonuç üretir.

# Modül kasıtlı olarak küçük seçilirse çakışmalar artar
print(rabin_karp("ABABDABACDABABCABAB", "ABABCABAB", modul=7))
# ([10], 4, 36)

Küçük modülde dört pencere karma sınamasını geçer, ancak yalnızca biri gerçek eşleşmedir; diğer üçü doğrulamada elenir. Sonuç yine doğrudur — bedel, boşa yapılan karakter karşılaştırmalarıdır.

Bu, karma tabanlı yöntemlerin genel deseni: karma eleme yapar, doğrulama karar verir.

Maliyet

Beklenen maliyet $O(n + m)$’dir: her pencere sabit işlem alır ve çakışma olasılığı, modül yeterince büyük seçildiğinde ihmal edilebilir düzeydedir.

En kötü durum $O(nm)$’dir ve iki biçimde ortaya çıkar. Birincisi, gerçekten çok sayıda eşleşme olmasıdır ("AAAA…" içinde "AA" aramak) — bu kaçınılmazdır, çünkü çıktının kendisi büyüktür. İkincisi, seçilen karma işlevine göre kurgulanmış çakışma üreten bir metindir; modül rastgele seçilerek bu saldırı olasılığa çevrilir.

Ölçüt	Kaba kuvvet	Rabin–Karp
Önişleme	Yok	$O(m)$
Beklenen arama	$O(nm)$ en kötü	$O(n + m)$
En kötü arama	$O(nm)$	$O(nm)$
Ek alan	$O(1)$	$O(1)$

Taban ve Modül Seçimi

İki parametre yöntemin davranışını belirler.

Taban, abece büyüklüğünden küçük olmamalıdır; küçükse farklı karakter dizileri düzenli olarak aynı değere düşer. Bayt dizileri için 256, küçük abeceler için abece büyüklüğü kadar bir değer yeterlidir.

Modül asal seçilir. Asal olmayan bir modül, taban ile ortak çarpanlar taşıdığında karma değerlerini belirli kalıntılara yığar ve çakışmaları artırır.

Modülün büyüklüğü bir taşma sorusudur: ara çarpım karma * taban değeri, dilin tam sayı genişliğini aşmamalıdır. Altmış dört bitlik aritmetikte modülün yaklaşık $2^{31}$ altında tutulması bunu güvence altına alır. Python’un sınırsız tam sayıları bu kısıtı kaldırır, karşılığında büyük değerlerde işlem maliyeti artar.

Çakışma olasılığı, rastgele bir modül için pencere başına yaklaşık $m/q$’dur. Daha güçlü bir güvence gerekiyorsa iki bağımsız karma birlikte kullanılır; ikisinin birden çakışma olasılığı çarpım kadar küçülür ve doğrulama neredeyse hiç boşa çalışmaz.

Asıl Üstünlük: Çoklu Örüntü

Yöntemin en belirgin kazancı, tek örüntülü aramada değil aynı uzunlukta birçok örüntüyü birlikte aramada ortaya çıkar. Örüntülerin karma değerleri bir kümede tutulur; metin tek geçişte taranır ve her pencere için tek bir küme sorgusu yapılır.

def coklu_rabin_karp(metin: str, oruntuler: list[str],
                     taban: int = 256, modul: int = 1_000_003) -> dict[str, list[int]]:
    m = len(oruntuler[0])
    if any(len(o) != m for o in oruntuler):
        raise ValueError("tüm örüntüler aynı uzunlukta olmalı")

    hedefler: dict[int, list[str]] = {}
    for o in oruntuler:
        h = 0
        for karakter in o:
            h = (h * taban + ord(karakter)) % modul
        hedefler.setdefault(h, []).append(o)

    ust = pow(taban, m - 1, modul)
    karma = 0
    for i in range(m):
        karma = (karma * taban + ord(metin[i])) % modul

    sonuc: dict[str, list[int]] = {o: [] for o in oruntuler}
    for kaydirma in range(len(metin) - m + 1):
        for aday in hedefler.get(karma, []):
            if metin[kaydirma:kaydirma + m] == aday:
                sonuc[aday].append(kaydirma)
        if kaydirma < len(metin) - m:
            karma = (karma - ord(metin[kaydirma]) * ust) % modul
            karma = (karma * taban + ord(metin[kaydirma + m])) % modul
    return sonuc


print(coklu_rabin_karp("ABABDABACDABABCABAB", ["ABAB", "BACD", "CABA"]))
# {'ABAB': [0, 10, 15], 'BACD': [6], 'CABA': [14]}

Üç örüntü, metnin tek geçişinde bulunur. $k$ örüntü için maliyet $O(n + km)$’dir; kaba kuvvetle her örüntüyü ayrı aramak $O(knm)$ olurdu.

Aynı fikir iki boyuta genişletilir: satır karmaları yuvarlanarak bir görüntü içinde dikdörtgen örüntü aranabilir. Yuvarlanan karma ayrıca içerik tanımlı parçalama gibi alanlarda da kullanılır — aynı sabit maliyetli pencere güncellemesi, farklı bir amaç için.

Özet

• Rabin–Karp, pencereleri karma değerine indirger ve karşılaştırmayı sayı eşitliğine çevirir.
• Yuvarlanan karma, pencere kaydığında değeri sabit sayıda işlemle günceller.
• Karma eşitliği kanıt değildir; her aday karakter karşılaştırmasıyla doğrulanır.
• Beklenen maliyet $O(n + m)$, en kötü durum $O(nm)$’dir; rastgele modül seçimi kurgulanmış girdilere karşı korur.
• Asıl üstünlük, aynı uzunluktaki birçok örüntüyü tek geçişte aramaktır: $O(n + km)$.

Sonraki Adım

Rabin–Karp, örüntünün içeriğini bir sayıya sıkıştırdı ama yapısını hiç kullanmadı. Oysa ABABCABAB örüntüsünün öneki ile soneki arasındaki örtüşme, uyuşmazlık anında kaç konumun güvenle atlanabileceğini söyler. Sonraki ders bu yapıyı önek işlevi olarak hesaplayacak ve metinde hiç geri dönmeyen bir arama kuracak.