Wikiszótár

Rabin-Karp algoritmus

Magyar

Kiejtés

  • IPA: [ ˈrɒbiŋkɒrpɒlɡoritmuʃ]

Főnév

Rabin-Karp algoritmus

  1. (matematika, algoritmusok) A Rabin-Karp-algoritmus egy hatékony szövegkeresési algoritmus, amelyet Richard M. Karp és Michael O. Rabin dolgozott ki 1987-ben. Az algoritmus a karakterláncok hash értékein alapul, és egy vagy több minta gyors keresésére használható egy nagyobb szövegben.


Jellemzők

  1. Hashing:
    • Az algoritmus hash függvényeket használ a szövegrészletek gyors összehasonlítására.
    • Az összehasonlítás akkor történik karakterenként, ha a hash értékek megegyeznek.
  2. Alkalmazások:
    • Szövegkeresés nagy szövegekben.
    • DNS-szekvenciák összehasonlítása.
    • Plágiumkeresés.
  3. Időkomplexitás:
    • Legjobb eset: (O(n + m)), ahol (n) a szöveg hossza, (m) a minta hossza.
    • Legrosszabb eset: (O(n m)), ha sok hash ütközés van.


Algoritmus működése

  1. Hash érték számítása:
    • Számítsuk ki a minta ((P)) és a szöveg első részletének ((T_1)) hash értékét egy (h) hash függvénnyel.
  2. Csúszóablakos ellenőrzés:
    • Mozgassuk a csúszóablakot a szövegen:
      • Frissítsük a hash értéket egy új karakter hozzáadásával és az első karakter eltávolításával.
      • Ha a hash érték megegyezik, végezzünk tényleges karakter-összehasonlítást a minta és az aktuális részlet között.
  3. Találatok rögzítése:
    • Jegyezzük fel a találatokat, ha a minta megegyezik a szöveg részletével.


Hash függvény

A hash függvény gyakran modulo műveletet használ a túlfutás elkerülésére: [ h(s) = (s[0] d^{m-1} + s[1] d^{m-2} + + s[m-1]) q ] ahol: - (d): az ábécé mérete (pl. 256 ASCII karakterekhez), - (q): egy nagy prímszám, amely minimalizálja a hash ütközéseket.


Pszeudokód

RabinKarp(text, pattern, d, q):
    n = text hossza
    m = pattern hossza
    h = d^(m-1) % q
    p_hash = 0  # Pattern hash
    t_hash = 0  # Szöveg hash

    # Kezdeti hash értékek számítása
    for i in 0 to m-1:
        p_hash = (d * p_hash + pattern[i]) % q
        t_hash = (d * t_hash + text[i]) % q

    for i in 0 to n-m:
        # Ha a hash értékek egyeznek, ellenőrizzük a mintát
        ha p_hash == t_hash:
            ha text[i:i+m] == pattern:
                visszaad találat

        # Hash érték frissítése
        ha i < n-m:
            t_hash = (d * (t_hash - text[i] * h) + text[i+m]) % q
            ha t_hash < 0:
                t_hash += q

Python implementáció

def rabin_karp(text, pattern, d=256, q=101):
    n, m = len(text), len(pattern)
    h = pow(d, m-1) % q
    p_hash, t_hash = 0, 0
    results = []

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

    for i in range(n - m + 1):
        # Hash összehasonlítás
        if p_hash == t_hash:
            if text[i:i+m] == pattern:
                results.append(i)

        # Hash frissítése
        if i < n - m:
            t_hash = (d * (t_hash - ord(text[i]) * h) + ord(text[i + m])) % q
            if t_hash < 0:
                t_hash += q

    return results

# Példa használat
text = "abracadabra"
pattern = "abra"
matches = rabin_karp(text, pattern)
print("Találatok indexei:", matches)

Kimenet: 

Találatok indexei: [0, 7]

C++ implementáció

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

vector<int> rabin_karp(const string& text, const string& pattern, int d = 256, int q = 101) {
    int n = text.size();
    int m = pattern.size();
    int h = 1;
    int p_hash = 0, t_hash = 0;
    vector<int> results;

    // Az "h" érték kiszámítása
    for (int i = 0; i < m - 1; ++i) {
        h = (h * d) % q;
    }

    // Kezdeti hash értékek kiszámítása
    for (int i = 0; i < m; ++i) {
        p_hash = (d * p_hash + pattern[i]) % q;
        t_hash = (d * t_hash + text[i]) % q;
    }

    for (int i = 0; i <= n - m; ++i) {
        // Hash értékek összehasonlítása
        if (p_hash == t_hash) {
            if (text.substr(i, m) == pattern) {
                results.push_back(i);
            }
        }

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

    return results;
}

int main() {
    string text = "abracadabra";
    string pattern = "abra";

    vector<int> matches = rabin_karp(text, pattern);
    cout << "Találatok indexei:";
    for (int idx : matches) {
        cout << " " << idx;
    }
    cout << endl;

    return 0;
}

Kimenet: 

Találatok indexei: 0 7

Összegzés

Előnyök:

  1. Hatékony több minta esetén: Hashing gyors összehasonlítást tesz lehetővé.
  2. Egyszerű implementáció: Könnyen érthető és általánosítható.

Hátrányok:

  1. Ütközések kezelése: Ha sok hash érték egyezik, a karakter-összehasonlítás megnövelheti a futási időt.
  2. Hash függvény érzékenysége: A teljesítmény függ a hash függvény minőségétől és a választott modultól ((q)).

A Rabin-Karp-algoritmus különösen hatékony több minta esetén vagy olyan helyzetekben, ahol a minták gyors előfeldolgozására van szükség.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Rabin-Karp_algoritmus&oldid=3479536”