Rabin-Karp Algoritması

#Nasıl çalışır?

Rabin-Karp algoritması harfleri tek tek karşılaştırmak yerine sayıları karşılaştırır: desenin bir hash değeri hesaplanır ve metindeki her m harflik pencerenin hash'i bununla karşılaştırılır.

İşin püf noktası kayan hash'tir (rolling hash): pencere bir sağa kayınca hash baştan hesaplanmaz; soldan çıkan harfin katkısı çıkarılır, sağdan giren harfinki eklenir. Bu her adımı O(1) yapar.

Farklı dizgiler aynı hash'e sahip olabilir (çakışma). Bu yüzden hash'ler eşit olduğunda harfler yine de kontrol edilir; hash eşit ama harfler farklıysa buna sahte eşleşme (spurious hit) denir. Örnekte FUN ve DOG aynı hash'e düşüyor.

#Kendin dene

#Adım adım

1. 01Desenin hash'ini ve metnin ilk m harfinin hash'ini hesapla.
2. 02Hash'ler farklıysa harflere bakmadan geç.
3. 03Hash'ler eşitse harfleri karşılaştır: tutuyorsa eşleşme, tutmuyorsa sahte eşleşme.
4. 04Pencereyi kaydırıp hash'i sabit sürede güncelle (rolling hash).

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

BASE, MOD = 26, 101  # a small modulus so collisions show up; real code uses a large prime


def code(c: str) -> int:
    return ord(c) - ord("A") + 1  # A = 1 .. Z = 26


def rabin_karp(text: str, pattern: str):
    """Returns (match positions, number of spurious hits)."""
    n, m = len(text), len(pattern)
    high = pow(BASE, m - 1, MOD)  # weight of the leftmost letter
    p = t = 0
    for k in range(m):
        p = (p * BASE + code(pattern[k])) % MOD
        t = (t * BASE + code(text[k])) % MOD
    found, spurious = [], 0
    for s in range(n - m + 1):
        if t == p:  # equal hashes: the letters still have to be checked
            if text[s:s + m] == pattern:
                found.append(s)
            else:
                spurious += 1
        if s + m < n:  # roll: drop text[s], add text[s + m]
            t = ((t - code(text[s]) * high) * BASE + code(text[s + m])) % MOD
    return found, spurious


found, spurious = rabin_karp("FUNNYDOGFUN", "DOG")
print(" ".join(map(str, found)))
print(spurious)  # FUN has the same hash as DOG

#Karmaşıklık

İyi bir taban ve büyük bir asal mod ile çakışmalar çok nadir olur ve algoritma pratikte doğrusaldır. Ders, sayılar okunabilir kalsın diye bilerek küçük bir mod (101) kullanıyor; gerçek uygulamalar 10⁹ + 7 gibi büyük asallar ya da iki farklı hash kullanır.

#Ne zaman kullanılır?

Aynı anda birçok desen aramak (tüm desenlerin hash'leri bir kümede tutulur), intihal tespiti, dosyalarda tekrar eden parçaları bulmak (rsync, veri tekilleştirme) ve iki boyutlu desen arama Rabin-Karp fikrine dayanır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.