Wikiszótár

Boyer-Moore-Horspool-algoritmus

Magyar

Kiejtés

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

Főnév

Boyer-Moore-Horspool-algoritmus

  1. (matematika)

Boyer-Moore-Horspool-algoritmus

A Boyer-Moore-Horspool-algoritmus egy hatékony szövegkereső algoritmus, amelyet arra terveztek, hogy egy adott mintát (pattern) keressen egy szövegben (text). Ez az algoritmus egy egyszerűsített változata a Boyer-Moore algoritmusnak, de a legtöbb esetben gyorsabb, mert kevesebb szabályt használ.


Működési elv

  1. Előfeldolgozás:
    • Létrehoz egy eltolási táblázatot (shift table), amely azt mondja meg, hogy adott karakterek esetén mennyit lehet ugrani, ha nincs egyezés.
    • Az utolsó karaktereket használja az összehasonlítás során.
  2. Összehasonlítás:
    • A minta végéről indul, és a szöveg karaktereivel összehasonlítva dönt, hogy egyezés van-e vagy sem.
    • Ha nincs egyezés, az eltolási táblázat alapján ugrik tovább.
  3. Hatékonyság:
    • Átlagos esetben az algoritmus futási ideje ( O(n) ), ahol ( n ) a szöveg hossza.
    • Legrosszabb esetben ( O(nm) ), ahol ( m ) a minta hossza.


Pszedókód

  1. Készíts egy eltolási táblázatot a minta karaktereire.
  2. Hasonlítsd össze a minta végét a szöveg aktuális pozíciójával.
  3. Ha nincs egyezés, az eltolási táblázat segítségével ugorj tovább.
  4. Ismételd a folyamatot, amíg el nem éred a szöveg végét.

Eltolási táblázat előállítása

  • Minden karakter esetén: ( [c] = ).
  • A minta minden karaktere esetén: ( [minta[i]] = - i - 1 ).


Python Implementáció

def boyer_moore_horspool(text, pattern):
    """
    Boyer-Moore-Horspool algoritmus szövegkereséshez.

    :param text: Szöveg, amelyben keresünk.
    :param pattern: A keresett minta.
    :return: Az egyezés kezdőindexe(i), vagy -1, ha nincs egyezés.
    """
    m = len(pattern)
    n = len(text)
    
    if m > n:
        return -1
    
    # Eltolási táblázat előállítása
    shift = {char: m for char in set(text)}
    for i in range(m - 1):
        shift[pattern[i]] = m - i - 1
    
    # Szöveg keresése
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1
        if j < 0:  # Egyezést találtunk
            return i
        i += shift.get(text[i + m - 1], m)  # Előrelépés az eltolási táblázat alapján
    
    return -1

# Példa használat
text = "hello there, this is an example"
pattern = "example"
index = boyer_moore_horspool(text, pattern)

if index != -1:
    print(f"Minta megtalálva a(z) {index}. indexen.")
else:
    print("Minta nem található.")

Kimenet: 

Minta megtalálva a(z) 21. indexen.

C++ Implementáció

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int boyerMooreHorspool(const string& text, const string& pattern) {
    int m = pattern.size();
    int n = text.size();

    if (m > n) {
        return -1;
    }

    // Eltolási táblázat előállítása
    unordered_map<char, int> shift;
    for (char c : text) {
        shift[c] = m;
    }
    for (int i = 0; i < m - 1; ++i) {
        shift[pattern[i]] = m - i - 1;
    }

    // Szöveg keresése
    int i = 0;
    while (i <= n - m) {
        int j = m - 1;
        while (j >= 0 && pattern[j] == text[i + j]) {
            --j;
        }
        if (j < 0) { // Egyezést találtunk
            return i;
        }
        i += shift.count(text[i + m - 1]) ? shift[text[i + m - 1]] : m;
    }

    return -1;
}

int main() {
    string text = "hello there, this is an example";
    string pattern = "example";

    int index = boyerMooreHorspool(text, pattern);

    if (index != -1) {
        cout << "Minta megtalálva a(z) " << index << ". indexen." << endl;
    } else {
        cout << "Minta nem található." << endl;
    }

    return 0;
}

Kimenet: 

Minta megtalálva a(z) 21. indexen.

Magyarázat

  1. Eltolási táblázat:
    • Az algoritmus a karakterek alapján ugrik, nem karakterenként halad előre, így gyorsítva a keresést.
  2. Hatékonyság:
    • Gyorsabb, mint a naiv algoritmus, mert nem néz meg minden karaktert.
    • Átlagos esetben ( O(n) ), ahol ( n ) a szöveg hossza.
  3. Használat:
    • Szövegkeresés alkalmazásokban (pl. szövegszerkesztők, keresőmotorok).
    • DNS-szekvenciák vagy hosszú szövegek feldolgozása.

Ez a megközelítés könnyen implementálható és hatékony sok gyakorlati esetben.

Fordítások

Tartalom

További információk

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