Wikiszótár

Boyer-Moore-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈboiɛrmoorɛɒlɡoritmuʃ]

Főnév

Boyer-Moore-algoritmus

  1. (matematika) A Boyer-Moore-algoritmus egy hatékony szövegkeresési algoritmus, amely egy minta (pattern) egy adott szövegben (text) való első előfordulását keresi. Az algoritmus hatékonysága a jobb-minta összehasonlításokon és két előfeldolgozási lépésen alapul: a Bad Character és a Good Suffix heurisztikákon. Az algoritmus jellemzően (O(n))-es futási időt ér el a gyakorlatban, ahol (n) a szöveg hossza.


Fő ötlet

  1. Jobbról balra történő mintaillesztés:
    • Az algoritmus a mintát a szöveg adott pozíciójához illeszti jobbról balra haladva.
  2. Előfeldolgozási lépések:
    • Bad Character heurisztika: Ha egy karakter nem illeszkedik, az algoritmus kihasználja annak pozícióját a mintában.
    • Good Suffix heurisztika: Ha egy részleges egyezés nem folytatható, a már illeszkedett szuffixumot használja a minta gyors eltolásához.
  3. Gyors eltolás:
    • A mintát a lehető legnagyobb mértékben eltolja, elkerülve a felesleges összehasonlításokat.


Algoritmus működése

1. Előfeldolgozás

  • Bad Character táblázat:
    • Létrehoz egy táblázatot, amely minden karakterhez tárolja a minta utolsó előfordulási helyét. Ha egy karakter nincs a mintában, akkor -1-et tárol.
    • Ha a minta adott karaktere nem illeszkedik a szöveghez, az algoritmus a táblázat alapján eltolja a mintát.
  • Good Suffix táblázat:
    • Ha a minta részben illeszkedik, de nem teljesen, az algoritmus ezt az információt használja a minta optimális eltolására.

2. Mintaillesztés

  • A mintát a szöveg elejéhez igazítjuk.
  • Jobbról balra haladva összehasonlítjuk a minta karaktereit a szöveggel.
  • Ha eltérést találunk, a Bad Character és a Good Suffix heurisztikák közül a nagyobb eltolást választjuk.

3. Ismétlés

  • Az algoritmus ismétli az eltolást és az összehasonlítást, amíg a minta végig nem ér a szövegen.


Pszeudokód

BoyerMoore(text, pattern):
    n = len(text)
    m = len(pattern)
    
    # Előfeldolgozás
    bad_char = create_bad_char_table(pattern)
    good_suffix = create_good_suffix_table(pattern)
    
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1
        
        if j < 0:
            print(f"Minta megtalálva itt: {i}")
            i += good_suffix[0]
        else:
            shift = max(1, j - bad_char[text[i + j]])
            i += shift

Előfeldolgozás részletei

1. Bad Character táblázat

def create_bad_char_table(pattern):
    bad_char = [-1] * 256  # ASCII karakterek
    for i in range(len(pattern)):
        bad_char[ord(pattern[i])] = i
    return bad_char

2. Good Suffix táblázat

def create_good_suffix_table(pattern):
    m = len(pattern)
    good_suffix = [0] * m
    border = [0] * (m + 1)
    
    j = m
    for i in range(m - 1, -1, -1):
        if pattern[i:] == pattern[m - j:]:
            border[j] = i + 1
        j -= 1
    
    j = 0
    for i in range(m):
        if border[j] == 0:
            good_suffix[i] = m - j
        else:
            good_suffix[i] = m - border[j]
        j += 1
    
    return good_suffix

Python implementáció

def boyer_moore(text, pattern):
    n = len(text)
    m = len(pattern)
    
    if m == 0:
        return []

    # Előfeldolgozás
    bad_char = create_bad_char_table(pattern)
    good_suffix = create_good_suffix_table(pattern)
    
    i = 0
    results = []
    while i <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1
        
        if j < 0:
            results.append(i)
            i += good_suffix[0]
        else:
            i += max(1, j - bad_char[ord(text[i + j])])
    
    return results

# Példa
text = "ABAAABCDABC"
pattern = "ABC"
result = boyer_moore(text, pattern)
print("A minta megtalálható pozíciói:", result)

Kimenet: 

A minta megtalálható pozíciói: [4, 8]

C++ implementáció

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<int> create_bad_char_table(const string& pattern) {
    vector<int> bad_char(256, -1);  // ASCII karakterek
    for (int i = 0; i < pattern.size(); ++i) {
        bad_char[pattern[i]] = i;
    }
    return bad_char;
}

vector<int> boyer_moore(const string& text, const string& pattern) {
    int n = text.size();
    int m = pattern.size();
    vector<int> result;
    if (m == 0) return result;

    vector<int> bad_char = create_bad_char_table(pattern);

    int shift = 0;
    while (shift <= n - m) {
        int j = m - 1;
        while (j >= 0 && pattern[j] == text[shift + j]) {
            --j;
        }
        if (j < 0) {
            result.push_back(shift);
            shift += (shift + m < n) ? m - bad_char[text[shift + m]] : 1;
        } else {
            shift += max(1, j - bad_char[text[shift + j]]);
        }
    }
    return result;
}

int main() {
    string text = "ABAAABCDABC";
    string pattern = "ABC";
    vector<int> positions = boyer_moore(text, pattern);

    cout << "A minta megtalálható pozíciói: ";
    for (int pos : positions) {
        cout << pos << " ";
    }
    cout << endl;

    return 0;
}

Kimenet: 

A minta megtalálható pozíciói: 4 8

Előnyök

  1. Hatékonyság:
    • Gyakorlati helyzetekben (O(n))-es teljesítmény érhető el.
  2. Optimális működés:
    • Kiváló teljesítményt nyújt hosszú szövegek és minták esetén.
  3. Heurisztikák kombinációja:
    • A két heurisztika hatékony eltolásokat tesz lehetővé.


Hátrányok

  1. Előfeldolgozás költsége:
    • Az előfeldolgozás időigényes lehet.
  2. Kis minták:
    • Rövid minták esetén más algoritmusok (pl. Knuth-Morris-Pratt) hatékonyabbak lehetnek.


Összegzés

A Boyer-Moore-algoritmus az egyik leggyorsabb szövegkeresési algoritmus, amelyet különösen nagy szövegek és minták keresésére használnak. A Bad Character és a Good Suffix heurisztikák kombinációja révén az algoritmus hatékonyan csökkenti az összehasonlítások számát, így a gyakorlatban nagyon gyors. Ezért az algoritmus népszerű választás, ha nagy adathalmazokban kell keresni mintákat.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Boyer-Moore-algoritmus&oldid=3479724”