Rabin-Karp
- Algoritmalar kursu
- Uzman seviye
- Ders 14/41
- 4 dk
Rabin-Karp hash tabanlı string eşleme öğrenirsin.
Rabin-Karp
Rabin-Karp, hash tabanlı bir string eşleme algoritmasıdır. Örüntünün ve metindeki her pencerenin hash değerini karşılaştırır.
Hash'ler eşitse olası eşleşme vardır; tam doğrulama için karakter karakter karşılaştırma yapılır. Hash çakışmaları bu doğrulama adımıyla çözülür.
Yuvarlanan hash (rolling hash) sayesinde bir pencereden diğerine O(1) sürede geçilir; toplam karmaşıklık ortalama O(n+m)'dir.
Yuvarlanan hash
Yuvarlanan hash, pencere sağa kaydırıldığında eski karakterin katkısını çıkarıp yeni karakterin katkısını ekler. Bu, hash'i baştan hesaplamaktan kaçınır.
Formül: h = ((h - ord(text[i-m]) * pow_base) * base + ord(text[i])) % mod. Burada pow_base = base^(m-1) mod mod'dir.
Mod alınması büyük sayı taşmasını önler; mod değeri genellikle büyük bir asal sayı seçilir.
Uygulama rabin_karp fonksiyonu
rabin_karp(text, pattern) yaz. İlk eşleşme indeksini döndür; yoksa -1. print(rabin_karp("merhabatarif", "tarif")) ile 7 yazdır.
Başlangıç kodu
def rabin_karp(text, pattern):
# Hash tabanlı eşleşmeÖrnek çözüm
def rabin_karp(text, pattern):
# Hash tabanlı eşleşme
base = 256
mod = 101
n, m = len(text), len(pattern)
if m == 0 or m > n:
return -1
ph = 0
th = 0
pow_base = 1
for _ in range(m - 1):
pow_base = (pow_base * base) % mod
for i in range(m):
ph = (ph * base + ord(pattern[i])) % mod
th = (th * base + ord(text[i])) % mod
for i in range(n - m + 1):
if ph == th:
if text[i:i + m] == pattern:
return i
if i < n - m:
th = ((th - ord(text[i]) * pow_base) * base + ord(text[i + m])) % mod
if th < 0:
th += mod
return -1
print(rabin_karp("merhabatarif", "tarif"))Beklenen çıktı
7
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 hash hesabı
h = (h * base + ord(text[____)) % modh = (h * base + ord(text[i)) % modAçıklama: karakter hash'e eklenir.
2 Hash çakışması bulunursa ne yapılır?
if h == pattern_hash:
...- Eşleşme kabul edilir
- Arama durdurulur
- Karakter karakter doğrulanır Doğru cevap
- Yeni mod seçilir
Açıklama: Hash çakışması karakter karakter doğrulamayla çözülür.
3 Rabin-Karp kavramları
| Kavram | Anlamı |
|---|---|
yuvarlanan hash |
O(1) kaydırma |
mod |
Büyük asal |
çakışma |
Doğrulama gerekli |
base |
256 karakter |