Boyer–Moore

KMP metnin her karakterine en az bir kez bakıyordu; bu, doğrusal maliyetin alt sınırı gibi görünür. Boyer–Moore ailesi bu sezgiyi bozar: bazı karakterlere hiç bakmadan doğru sonuç üretmek mümkündür.

Fikir yön değişikliğinden çıkar — örüntü, sondan başa doğru eşleştirilir.

Sondan Eşleme Neden Kazandırır

Örüntü metnin bir penceresine yerleştirilir ve karşılaştırma son karakterden başlar. Uyuşmazlık en sonda olursa, metindeki o karaktere bakılarak örüntünün ne kadar kaydırılabileceği belirlenir.

Metindeki karakter örüntüde hiç geçmiyorsa, örüntü tamamen onun ötesine kaydırılabilir: tek karşılaştırmayla $m$ konum elenmiş olur. Aradaki karakterlere hiç bakılmaz.

Örüntüde geçiyorsa, örüntünün o karakteri içeren en sağdaki konumu metindekiyle hizalanacak kadar kaydırılır. Bu, kötü karakter kuralıdır.

Kaydırma Tablosu

Kural, örüntüden çıkarılan basit bir tabloyla uygulanır: her karakter için, örüntünün sonuna olan uzaklığı.

def kaydirma_tablosu(oruntu: str) -> dict[str, int]:
    """Karakterin örüntü sonundan uzaklığı; son karakter tabloya alınmaz."""
    m = len(oruntu)
    return {oruntu[i]: m - 1 - i for i in range(m - 1)}


print(kaydirma_tablosu("ABABCABAB"))     # {'A': 1, 'B': 2, 'C': 4}

Tablo m - 1 karakterden kurulur; son karakter dışarıda bırakılır, çünkü kaydırma her zaman en az bir olmalıdır. Tabloda bulunmayan bir karakter için kaydırma $m$’dir.

Değerler örüntüdeki en sağdaki geçişten hesaplanır: aynı karakter birden çok kez geçiyorsa sözlükteki son atama kalır ve bu, en sağdaki konuma karşılık gelir.

Horspool Değişkesi

Boyer–Moore’un kolay yazılan ve pratikte yaygın kullanılan basitleştirmesi, kaydırmayı uyuşan karaktere değil pencerenin son karakterine göre yapar.

def horspool(metin: str, oruntu: str) -> tuple[list[int], int]:
    """(konumlar, karakter karşılaştırma sayısı)"""
    n, m = len(metin), len(oruntu)
    if m > n:
        return [], 0
    tablo = kaydirma_tablosu(oruntu)
    konumlar: list[int] = []
    kaydirma, sayac = 0, 0

    while kaydirma <= n - m:
        j = m - 1
        while j >= 0:                       # sondan başa karşılaştır
            sayac += 1
            if metin[kaydirma + j] != oruntu[j]:
                break
            j -= 1
        if j < 0:
            konumlar.append(kaydirma)
            kaydirma += 1
        else:
            son = metin[kaydirma + m - 1]
            kaydirma += tablo.get(son, m)   # tabloda yoksa tam örüntü boyu atla
    return konumlar, sayac


metin = "ABABDABACDABABCABAB"
oruntu = "ABABCABAB"
print(horspool(metin, oruntu))       # ([10], 20)
print(horspool("ABABAB", "AB"))      # ([0, 2, 4], 8)
print(horspool("aaa", "b"))          # ([], 3)

Kaydırma her zaman en az 1 olduğu için sonlanma güvencededir. Doğruluk, atlanan konumlarda eşleşme olamayacağının kuraldan çıkmasına dayanır: kaydırma, pencerenin son karakterinin örüntüde bulunabileceği en yakın hizaya kadardır.

Ölçülen Fark

Dört algoritma aynı girdilerde karşılaştırıldığında yön ayrımı sayılarla görünür.

# kaba_kuvvet ve kmp: önceki iki dersin gerçekleştirimleri, blok tek başına
# koşabilsin diye buraya alındı
def kaba_kuvvet(metin: str, oruntu: str) -> tuple[list[int], int]:
    """(bulunan konumlar, karakter karşılaştırma sayısı)"""
    n, m = len(metin), len(oruntu)
    konumlar: list[int] = []
    sayac = 0
    for kaydirma in range(n - m + 1):
        j = 0
        while j < m:
            sayac += 1
            if metin[kaydirma + j] != oruntu[j]:
                break
            j += 1
        if j == m:
            konumlar.append(kaydirma)
    return konumlar, sayac


def onek_islevi(oruntu: str) -> list[int]:
    """pi[i]: oruntu[0..i] parçasının en uzun öz önek-sonek uzunluğu."""
    pi = [0] * len(oruntu)
    k = 0
    for i in range(1, len(oruntu)):
        while k > 0 and oruntu[i] != oruntu[k]:
            k = pi[k - 1]                  # daha kısa bir aday öneke geri çekil
        if oruntu[i] == oruntu[k]:
            k += 1
        pi[i] = k
    return pi


def kmp(metin: str, oruntu: str) -> tuple[list[int], int]:
    """(konumlar, karakter karşılaştırma sayısı)"""
    pi = onek_islevi(oruntu)
    konumlar: list[int] = []
    k = 0
    sayac = 0
    for i, karakter in enumerate(metin):
        while k > 0 and karakter != oruntu[k]:
            sayac += 1
            k = pi[k - 1]
        sayac += 1
        if karakter == oruntu[k]:
            k += 1
        if k == len(oruntu):
            konumlar.append(i - len(oruntu) + 1)
            k = pi[k - 1]                  # örtüşen sonraki geçişi kaçırma
    return konumlar, sayac
uzun = ("bir metin icinde oruntu aramanin maliyeti "
        "abecenin buyuklugune ve tekrarlara baglidir. ") * 10

for desen in ("oruntu", "tekrarlara", "zzzzz"):
    print(desen,
          kaba_kuvvet(uzun, desen)[1],
          kmp(uzun, desen)[1],
          horspool(uzun, desen)[1])

# oruntu     915 870 240
# tekrarlara 981 900 190
# zzzzz      866 870 174
#                        ← metin uzunluğu: 870

Horspool, metin uzunluğundan daha az karşılaştırma yapar: 870 karakterlik metinde 174. Örüntü uzadıkça sayı düşer, çünkü her başarısız denemede daha büyük adım atılır.

Doğrusalın altındaki bu davranış bir çelişki değildir: algoritma metnin her karakterine bakmaz. Örüntünün olmadığını göstermek için tüm metni okumak gerekmez.

Beklenen karşılaştırma sayısı, abece büyüklüğü $\sigma$ arttıkça $n/m$’ye yaklaşır. Doğal dil ve büyük abeceler bu koşulu sağladığından, sondan eşleme metin arama araçlarının tipik seçimidir.

En Kötü Durum ve İyi Sonek Kuralı

Yalnızca kötü karakter kuralıyla en kötü durum $O(nm)$ kalır. Küçük abeceli, tekrarlı girdilerde kaydırmalar küçülür.

print(horspool("A" * 30 + "B", "A" * 10 + "B")[1])     # 31
print(kaba_kuvvet("A" * 30 + "B", "A" * 10 + "B")[1])  # 231

Bu girdide sonuç iyidir, çünkü uyuşmazlık ilk karşılaştırmada ortaya çıkar. Ters kurgu — "A"*30 içinde "BAAAAAAAAA" gibi bir örüntü — kaydırmaları bire indirir.

Tam Boyer–Moore, kötü karakter kuralına iyi sonek kuralını ekler: eşleşmiş olan sonek parçası, örüntünün başka bir yerinde geçiyorsa oraya hizalanır; geçmiyorsa sonekin bir öneki örüntünün başına denk getirilir. İki kuraldan büyük kaydırmayı öneren seçilir.

İyi sonek tablosu, KMP’nin önek işlevine benzer biçimde $O(m)$’de kurulur. Ek bir teknikle (eşleşmiş bölgelerin yeniden karşılaştırılmasını önleyen kural) en kötü durum $O(n)$’e indirilebilir.

Pencerenin Bir Sonrasına Bakmak

Aynı ailenin bir başka değişkesi, kaydırmayı pencerenin son karakterine değil, pencereden hemen sonraki karaktere göre yapar. O karakter, bir sonraki hizalamada örüntünün içinde kalacağından, örüntüde hiç geçmiyorsa $m+1$ konum birden atlanabilir.

def hizli_arama(metin: str, oruntu: str) -> tuple[list[int], int]:
    n, m = len(metin), len(oruntu)
    if m > n:
        return [], 0
    tablo = {oruntu[i]: m - i for i in range(m)}     # tüm karakterler tabloda
    konumlar: list[int] = []
    kaydirma, sayac = 0, 0

    while kaydirma <= n - m:
        j = 0
        while j < m:
            sayac += 1
            if metin[kaydirma + j] != oruntu[j]:
                break
            j += 1
        if j == m:
            konumlar.append(kaydirma)
        if kaydirma + m >= n:
            break
        kaydirma += tablo.get(metin[kaydirma + m], m + 1)
    return konumlar, sayac


print(hizli_arama(metin, oruntu))            # ([10], 14)
print(hizli_arama(uzun, "tekrarlara")[1])    # 190

Karşılaştırma yönü burada baştan sonadır; kazanç yalnızca kaydırma kuralından gelir. Tablonun tüm örüntü karakterlerini içermesi ve kaydırmanın $m+1$’e kadar çıkabilmesi, gerçekleştirimi kısaltırken pratikte büyük adımlar sağlar.

Dört Yöntemin Yeri

Ölçüt	Kaba kuvvet	Rabin–Karp	KMP	Boyer–Moore
Önişleme	Yok	$O(m)$	$O(m)$	$O(m + \sigma)$
Beklenen	$O(n)$ (büyük abece)	$O(n + m)$	$O(n + m)$	$O(n/m)$’ye yakın
En kötü	$O(nm)$	$O(nm)$	$O(n + m)$	$O(n)$ (tam biçim)
Ek alan	$O(1)$	$O(1)$	$O(m)$	$O(m + \sigma)$
Akış verisi	Uygun	Uygun	Uygun	Uygun değil

Son satır, sondan eşlemenin bedelidir: pencere içinde geri gidildiği için metnin ileriye doğru tek geçişte okunması yetmez.

Seçim ölçütü şudur: abece büyük ve örüntü uzunsa Boyer–Moore; en kötü durum güvencesi ya da akış işleme gerekiyorsa KMP; çok sayıda örüntü aynı anda aranıyorsa Rabin–Karp; kısa metin ve tek seferlik arama için kaba kuvvet.

Özet

• Boyer–Moore ailesi örüntüyü sondan başa eşleştirir; bu, metnin bazı karakterlerine hiç bakmadan atlamayı mümkün kılar.
• Kötü karakter kuralı, uyuşmayan metin karakterinin örüntüdeki en sağdaki konumuna hizalar; örüntüde yoksa tam örüntü boyu atlanır.
• Horspool değişkesi kaydırmayı pencerenin son karakterine göre yapar ve tek tabloyla çalışır.
• Beklenen karşılaştırma sayısı abece büyüdükçe $n/m$’ye yaklaşır; ölçümde metin uzunluğunun altına iner.
• İyi sonek kuralı eklendiğinde en kötü durum doğrusala indirilebilir.
• Sondan eşleme akış verisine uygun değildir; pencere içinde geri gidilir.

Sonraki Adım

Dört algoritma da örüntüyü önişledi; metin her aramada baştan tarandı. Aynı metinde binlerce sorgu yapılacaksa denge tersine döner: metni bir kez önişleyip her sorguyu logaritmik maliyetle yanıtlamak daha ucuzdur. Sonraki ders, metnin tüm soneklerini düzenleyen yapıları — sonek dizisi ve sonek ağacını — ele alacak.