Boyer-Moore
- Algoritmalar kursu
- Uzman seviye
- Ders 15/41
- 4 dk
Boyer-Moore kötü karakter kuralıyla eşleme öğrenirsin.
Boyer-Moore
Boyer-Moore, örüntüyü sağdan sola tarayarak eşleşme arar. Bu yön, büyük kaydırmalar yapmayı sağlar; çoğu durumda metnin yalnızca küçük bir bölümünü gözden geçirir.
İki ilke kullanır: kötü karakter ve iyi sonek. Burada kötü karakter yöntemini işleyeceğiz.
Kötü karakter yöntemi, uyuşmazlık bulunan metin karakterine göre örüntüyü kaydırır; böylece uyuşmayan karakter örüntüye hizalanır.
Kötü karakter tablosu
Kötü karakter tablosu, her karakter için örüntüdeki son görülme indeksini saklar. Uyuşmazlıkta, kaydırma miktarı max(1, j - bad[text[i]]) olarak hesaplanır.
Eğer uyuşmayan karakter örüntüde yoksa, örüntüyü tamamen bu karakterin sağına kaydırırız. Tablo bir hazırlık adımıdır ve O(m + |alfabe|) zamanda kurulur.
Bu ilke tek başına bile çoğu pratik durumda hızlı çalışır.
Uygulama boyer_moore fonksiyonu
boyer_moore(text, pattern) yaz. İlk eşleşme indeksini döndür; yoksa -1. print(boyer_moore("konfeksiyonmakine", "makine")) ile 11 yazdır.
Başlangıç kodu
def boyer_moore(text, pattern):
# Kötü karakter yöntemi ile araÖrnek çözüm
def boyer_moore(text, pattern):
# Kötü karakter yöntemi ile ara
n, m = len(text), len(pattern)
if m == 0:
return 0
bad = {}
for i in range(m):
bad[pattern[i]] = i
i = 0
while i <= n - m:
j = m - 1
while j >= 0 and pattern[j] == text[i + j]:
j -= 1
if j < 0:
return i
shift = j - bad.get(text[i + j], -1)
if shift < 1:
shift = 1
i += shift
return -1
print(boyer_moore("konfeksiyonmakine", "makine"))Beklenen çıktı
11
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Boyer-Moore kavramları
| Kavram | Anlamı |
|---|---|
sağdan sola |
Tarama yönü |
kötü karakter |
Kaydırma ilkesi |
iyi sonek |
İkinci ilke |
büyük kaydırma |
Hız avantajı |
2 Kötü karakter yöntemi ne yapar?
shift = j - bad.get(text[i+j], -1)- Tabloyu yeniden kurar
- Örüntüyü bir adım kaydırır
- Eşleşmeyi iptal eder
- Uyuşmazlık karakterine göre kaydırır Doğru cevap
Açıklama: Kötü karakter yöntemi uyuşmazlık karakterine göre kaydırır.
3 kötü karakter kaydırması
shift = j - bad.get(text[i + j], ____)shift = j - bad.get(text[i + j], -1)Açıklama: -1 ile kaydırma en az 1 olur.