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.
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)) % prime
t_hash = (base * t_hash + ord(text)) % 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 == pattern:
result.append(i)
# Hash frissítése az új ablakra
if i < n - m:
t_hash = (base * (t_hash - ord(text) * h) + ord(text)) % 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:
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) % prime;
t_hash = (base * t_hash + text) % 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 * h) + text) % 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
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.