Inne podejście niż KMP

Algorytm Knuth–Morris–Pratt zyskiwał na samopodobieństwie wzorca: po nieudanym dopasowaniu wykorzystywał strukturę prefikso-sufiksów, żeby przesunąć się o więcej niż jedno pole, ale i tak czytał tekst od lewej do prawej, znak po znaku.

Algorytm Boyer–Moore (1977) idzie inną drogą. Porównujemy wzorzec z tekstem od końca wzorca do początku. Dzięki temu pojedyncze niedopasowanie często niesie ze sobą informację, która pozwala przeskoczyć wiele znaków tekstu naraz — w typowym przypadku BM nie czyta nawet większości tekstu, osiągając sublinearną złożoność rzędu O(n/m).

Kluczowa idea — porównujemy od prawej

Wyrównujemy wzorzec z lewym końcem aktualnego okna w tekście, ale porównanie zaczynamy od OSTATNIEGO znaku wzorca. Jeśli ostatni znak wzorca w ogóle nie zgadza się ze znakiem w tekście, to:

• po pierwsze — odrzucamy całe to wyrównanie po jednym porównaniu,
• po drugie — często możemy od razu przesunąć wzorzec o kilka pozycji w prawo, a nie tylko o jedną.

To, o ile możemy bezpiecznie przesunąć wzorzec, wyznaczają dwie heurystyki działające niezależnie od siebie:

• reguła złego znaku (bad character),
• reguła dobrego sufiksu (good suffix).

Po niedopasowaniu liczymy obie i bierzemy z nich maksimum. Każda z nich z osobna jest poprawna (nie pominie żadnego dopasowania), więc maksimum też jest poprawne — a daje większy skok.

Reguła złego znaku

Niech j będzie pozycją we wzorcu, na której nastąpiło niedopasowanie (porównujemy od prawej, więc j to indeks pierwszego niezgodnego znaku idąc od końca). Niech c = text[s + j] — to znak w tekście, który się "nie zgodził".

Dla każdego znaku zapisujemy indeks jego ostatniego wystąpienia we wzorcu. Dla znaków spoza wzorca przyjmujemy umownie -1. Przesunięcie liczone z reguły złego znaku to wtedy \text{shift}_{bc} = j - \text{bad\_char}[c]

def bad_character_table(pattern):
    table = {}
    for i, ch in enumerate(pattern):
        table[ch] = i
    return table


if __name__ == "__main__":
    pattern = "ABCDABD"
    table = bad_character_table(pattern)
    print(f"Wzorzec: {pattern}")
    print("Tablica złego znaku (ostatnie wystąpienie znaku we wzorcu):")
    for ch in sorted(table):
        print(f"  {ch} -> {table[ch]}")

Reguła dobrego sufiksu

W momencie niedopasowania zazwyczaj mamy już dopasowany jakiś sufiks wzorca. Reguła dobrego sufiksu wykorzystuje tę wiedzę — bardzo podobnie do prefikso-sufiksów z KMP.

Przypadek 1: sufiks pojawia się we wzorcu

Jeśli sufiks pattern[i:] ma we wzorcu jeszcze jedno wystąpienie poprzedzone innym znakiem niż ten, który wcześniej spowodował niedopasowanie, przesuwamy wzorzec tak, żeby to drugie wystąpienie sufiksu znalazło się pod jego pierwotną pozycją w tekście. Warunek ten jest analogią ulepszenia Knutha w KMP — bez niego po przesunięciu od razu ponownie natrafilibyśmy na to samo niedopasowanie.

Przypadek 2: tylko prefiks wzorca pasuje do końcówki

Jeśli sufiks pattern[i:] jako całość nie występuje gdzie indziej, szukamy najdłuższego prefiksu wzorca, który jest jednocześnie sufiksem dopasowanej końcówki, i przesuwamy wzorzec tak, żeby ten prefiks trafił na koniec dopasowanego fragmentu w tekście. Jeśli i to się nie udaje — przesuwamy wzorzec o całe m pól.

Implementacja preprocessingu

def preprocess_strong_suffix(pattern):
    m = len(pattern)
    shift = [0] * (m + 1)
    bpos = [0] * (m + 1)
    bpos[m] = m + 1
    j = m + 1
    for i in range(m, 0, -1):
        while j <= m and pattern[i - 1] != pattern[j - 1]:
            shift[j] = shift[j] or (j - i)
            j = bpos[j]
        j -= 1
        bpos[i - 1] = j
    return shift, bpos


def preprocess_case2(shift, bpos):
    j = bpos[0]
    for i in range(len(shift)):
        shift[i] = shift[i] or j
        if i == j:
            j = bpos[j]
    return shift


def good_suffix_table(pattern):
    shift, bpos = preprocess_strong_suffix(pattern)
    return preprocess_case2(shift, bpos)


if __name__ == "__main__":
    pattern = "ABCDABD"
    shift = good_suffix_table(pattern)
    print(f"Wzorzec: {pattern}")
    print("Tablica dobrego sufiksu (shift[i] - przesuniecie po")
    print("niedopasowaniu na pozycji i-1, sufiks pattern[i:] dopasowany):")
    for i, s in enumerate(shift):
        print(f"  shift[{i}] = {s}")

Łączenie reguł i wyszukiwanie

Po niedopasowaniu na pozycji j mamy dwa kandydujące przesunięcia:

Bierzemy z nich maksimum, na końcu zabezpieczamy się jeszcze przez max(1, ...), żeby nigdy nie zatrzymać się w miejscu:

from l1 import bad_character_table
from l2 import good_suffix_table


def boyer_moore_search(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return 0 if m == 0 else -1

    bad_char = bad_character_table(pattern)
    gs_shift = good_suffix_table(pattern)

    s = 0
    while s <= n - m:
        j = next((k for k in range(m - 1, -1, -1) if pattern[k] != text[s + k]), -1)
        if j == -1:
            return s
        bc = j - bad_char.get(text[s + j], -1)
        s += max(1, bc, gs_shift[j + 1])
    return -1


if __name__ == "__main__":
    text = "ABAAABCDABCDABDEABCDABDABCDABD"
    pattern = "ABCDABD"
    pos = boyer_moore_search(text, pattern)
    print(f"Tekst:   {text}")
    print(f"Wzorzec: {pattern}")
    print(f"Pierwsze wystapienie na pozycji: {pos}")
    if pos >= 0:
        print(" " * (len(f"Tekst:   ") + pos) + "^" * len(pattern))

Reguła Galila

Klasyczny BM ma jedną słabość: w pesymistycznym przypadku może osiągnąć złożoność O(nm) — wystarczy wzorzec, w którym po każdym przesunięciu znów porównujemy te same znaki, które już raz dopasowaliśmy.

Reguła Galila (Zvi Galil, 1979) to drobna modyfikacja pętli wyszukiwania, która ogranicza ponowne porównania znaków już raz dopasowanych. Po przesunięciu wzorca z reguły dobrego sufiksu wiemy, że pewien jego prefiks musi się zgadzać z fragmentem tekstu, który właśnie minęliśmy — zamiast porównywać te znaki ponownie, zapamiętujemy granicę i pomijamy je w kolejnym porównaniu.

Dzięki temu pesymistyczny czas wyszukiwania spada z O(nm) do O(n), bez zmiany preprocessingu.

Złożoność

m — długość wzorca, n — długość tekstu, k — rozmiar alfabetu.

Kiedy używać Boyer–Moore

BM lubi:

• długie wzorce — im większe m, tym większe potencjalne skoki,
• duży alfabet — im większe k, tym częściej znak z tekstu nie ma w ogóle odpowiednika we wzorcu, więc reguła złego znaku daje maksymalny skok.

BM przegrywa z KMP, gdy alfabet jest mały i powtarzalność tekstu duża (klasyczny przykład: dopasowywanie sekwencji DNA z 4-znakowego alfabetu) — wtedy reguła złego znaku rzadko daje duże skoki, a koszt preprocessingu i bardziej skomplikowanej pętli przeważa.

W praktyce w bibliotekach standardowych częściej spotyka się uproszczony wariant Horspoola — używa tylko reguły złego znaku w nieco prostszej wersji, ma gorszy worst-case od pełnego BM, ale jest prostszy w implementacji i zwykle wystarczająco szybki.