Wikiszótár

Baeza-Yates-Gonnet-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈbɒɛzɒiɒtɛʒɡonːɛtɒlɡoritmuʃ]

Főnév

Baeza-Yates-Gonnet-algoritmus

  1. (matematika)

Baeza-Yates-Gonnet-algoritmus

A Baeza-Yates-Gonnet-algoritmus egy hatékony szövegkereső algoritmus, amelyet gyors substring (részsztring) keresésére fejlesztettek ki nagy szövegekben. Az algoritmus egyesíti a hashing és a szuffixfák előnyeit, hogy gyors szövegegyezést érjen el.

Az algoritmus leginkább a hash-alapú szövegkeresési módszerek csoportjába tartozik, és a Rabin-Karp-eljáráshoz hasonlóan működik, de optimalizálva van az illesztési műveletek csökkentésére.


Működési elv

  1. Hashing:
    • Az algoritmus a keresett minta (pattern) és a szöveg aktuális ablakának hash-értékét számolja ki.
    • A hash-értékek gyorsan újraszámíthatók az ablakok között.
  2. Összehasonlítás:
    • Ha a hash-értékek egyeznek, a mintát és a szövegrészt karakterenként összehasonlítja, hogy megerősítse az illeszkedést.
    • Ha a hash-értékek eltérnek, az algoritmus azonnal tovább lép a következő ablakra.
  3. Optimalizálás:
    • A Baeza-Yates-Gonnet-algoritmus hatékonyan minimalizálja az összehasonlítások számát, kihasználva a hashing mechanizmus előnyeit.
  4. Időkomplexitás:
    • Átlagos esetben: ( O(n + m) ), ahol ( n ) a szöveg hossza és ( m ) a minta hossza.
    • Legrosszabb esetben: ( O(nm) ), ha sok ütközés történik a hash-értékek között.


Algoritmus lépései

  1. Hash érték inicializálása:
    • Számítsd ki a keresett minta hash-értékét.
    • Számítsd ki a szöveg első ablakának (az első ( m ) karakter) hash-értékét.
  2. Keresési folyamat:
    • Lépj végig a szövegen ablakokban.
    • Ha a hash-értékek megegyeznek, karakterenként hasonlítsd össze a mintát az aktuális ablakkal.
    • Ha illeszkedés található, jegyezd fel az aktuális pozíciót.
  3. Ablak frissítése:
    • Használj egy gördülő hash-függvényt az új hash-érték gyors kiszámítására az előző érték alapján.
  4. Ismétlés:
    • Haladj végig az összes lehetséges ablakon.


Python Implementáció

Az alábbi Python-kód bemutatja a Baeza-Yates-Gonnet-algoritmus működését. 

def baeza_yates_gonnet(text, pattern, base=256, prime=101):
    """
    Baeza-Yates-Gonnet szövegkereső algoritmus.

    :param text: Szöveg, amelyben keresünk.
    :param pattern: Keresett minta.
    :param base: Hash alap (általában 256).
    :param prime: Hash modulo értéke (általában egy prím).
    :return: A minta kezdőindexei a szövegben.
    """
    n = len(text)
    m = len(pattern)
    h = pow(base, m-1) % prime  # Hash súly
    p_hash = 0  # Minta hash értéke
    t_hash = 0  # Szöveg hash értéke
    result = []

    # Kezdeti hash-értékek kiszámítása
    for i in range(m):
        p_hash = (base * p_hash + ord(pattern[i])) % prime
        t_hash = (base * t_hash + ord(text[i])) % prime

    # Keresés a szövegben
    for i in range(n - m + 1):
        # Hash értékek összehasonlítása
        if p_hash == t_hash:
            # Karakterenkénti ellenőrzés
            if text[i:i+m] == pattern:
                result.append(i)

        # Hash frissítése az új ablakra
        if i < n - m:
            t_hash = (base * (t_hash - ord(text[i]) * h) + ord(text[i + m])) % prime
            if t_hash < 0:
                t_hash += prime

    return result

# Példa használat
text = "ababcabcabc"
pattern = "abc"

matches = baeza_yates_gonnet(text, pattern)
print(f"Minta megtalálva a következő indexeken: {matches}")

Kimenet: 

Minta megtalálva a következő indexeken: [2, 5, 8]

C++ Implementáció

Az alábbi C++-kód a Baeza-Yates-Gonnet-algoritmus egy egyszerű változatát mutatja be. 

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

vector<int> baezaYatesGonnet(const string& text, const string& pattern, int base = 256, int prime = 101) {
    int n = text.size();
    int m = pattern.size();
    int h = 1;  // Hash súly
    for (int i = 0; i < m - 1; i++) {
        h = (h * base) % prime;
    }

    int p_hash = 0;  // Minta hash
    int t_hash = 0;  // Szöveg hash
    vector<int> result;

    // Kezdeti hash-értékek
    for (int i = 0; i < m; i++) {
        p_hash = (base * p_hash + pattern[i]) % prime;
        t_hash = (base * t_hash + text[i]) % prime;
    }

    // Keresés
    for (int i = 0; i <= n - m; i++) {
        if (p_hash == t_hash) {
            if (text.substr(i, m) == pattern) {
                result.push_back(i);
            }
        }

        // Hash frissítése
        if (i < n - m) {
            t_hash = (base * (t_hash - text[i] * h) + text[i + m]) % prime;
            if (t_hash < 0) {
                t_hash += prime;
            }
        }
    }

    return result;
}

int main() {
    string text = "ababcabcabc";
    string pattern = "abc";

    vector<int> matches = baezaYatesGonnet(text, pattern);

    cout << "Minta megtalálva a következő indexeken: ";
    for (int index : matches) {
        cout << index << " ";
    }
    cout << endl;

    return 0;
}

Kimenet: 

Minta megtalálva a következő indexeken: 2 5 8

Magyarázat

  1. Hashing:
    • Az algoritmus gördülő hash-t használ, amely hatékonyan frissíti az aktuális ablak hash-értékét anélkül, hogy újra kiszámolná minden karakterre.
  2. Összehasonlítások:
    • A hash-értékek gyors szűrőként működnek, és csökkentik az explicit összehasonlítások számát.
  3. Előnyök:
    • Hatékony nagy szövegekben, különösen akkor, ha kevés ütközés fordul elő a hash-értékek között.
  4. Hátrányok:
    • Ha a hash-függvény nem elég jó, sok ütközés történhet, ami lassítja az algoritmust.


Alkalmazások

  1. Szövegfeldolgozás:
    • Nagy dokumentumokban substringek gyors keresése.
  2. DNS-keresések:
    • DNS-szekvenciák gyors illesztése.
  3. Adatbázisok:
    • Szöveges adatok gyors keresése adatbázisokban.

Ez az algoritmus egyszerűbb implementációval és hatékony hash-alapú mechanizmussal dolgozik, amely hasznos, ha gyors substring keresésre van szükség.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Baeza-Yates-Gonnet-algoritmus&oldid=3480704”