--- title: Rabin–Karp source: 'https://academia.sh/tr/kurslar/algoritmalar/rabin-karp' course: Algoritmalar language: tr updated: '2026-08-17T18:07:48+00:00' license: 'CC BY-SA 4.0' --- # Rabin–Karp Yuvarlanan karma ile örüntü eşleme, sabit maliyetli pencere güncellemesi, çakışma doğrulaması, en kötü durum ve çoklu örüntü aramada üstünlüğü. 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 ```python 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. ```python # 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. ```python 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.