---
title: Boyer–Moore
source: 'https://academia.sh/tr/kurslar/algoritmalar/boyer-moore'
course: Algoritmalar
language: tr
updated: '2026-08-17T18:07:45+00:00'
license: 'CC BY-SA 4.0'
---

# Boyer–Moore

Sondan eşleme, kötü karakter ve iyi sonek kuralları, Horspool basitleştirmesi, doğrusalın altına inen davranış ve dört algoritmanın ölçülen karşılaştırması.

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ığı.

```python
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.

```python
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.

```python
# 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.

```python
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.

```python
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.