Wikiszótár

Knuth-Morris-Pratt-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈknuthmorːiʃprɒtːɒlɡoritmuʃ]

Főnév

Knuth-Morris-Pratt-algoritmus

  1. (informatika)

Knuth-Morris-Pratt algoritmus (KMP)

A Knuth-Morris-Pratt (KMP) algoritmus egy hatékony sztringkeresési algoritmus, amely egy szövegben találja meg egy adott minta előfordulását. Az algoritmus előfeldolgozza a mintát, hogy gyorsabban találhassa meg a lehetséges egyezéseket, elkerülve az ismételt összehasonlításokat.


Elmélet

  1. Alapprobléma:
    • Adott egy szöveg ((T)) és egy minta ((P)).
    • Az algoritmus célja, hogy megtalálja, hol (ha egyáltalán) fordul elő (P) a (T)-ben.
  2. Előfeldolgozás:
    • Létrehoz egy részleges egyezési táblázatot (prefix-funkció), amely megmutatja, hogy a minta bizonyos részének melyik előző része egyezhet.
    • Ez lehetővé teszi az algoritmus számára, hogy elkerülje az ismételt összehasonlításokat, ha egy részleges egyezés megszakad.
  3. Kulcsgondolat:
    • Ha a minta (P) részben illeszkedik a szöveghez, és egy eltérés történik, akkor a részleges egyezési táblázat segítségével gyorsan megállapítható, hogy a minta melyik pozíciójában folytatható az összehasonlítás.


Időkomplexitás

  • Előfeldolgozás: (O(m)), ahol (m) a minta hossza.
  • Keresés: (O(n)), ahol (n) a szöveg hossza.
  • Összesen: (O(n + m)).


Pszeudokód

Előfeldolgozás (Prefix-függvény kiszámítása)

ComputePrefixFunction(P):
    m = P hossza
    pi = [0] * m  // Prefix-függvény
    j = 0  // Prefix hossza
    ciklus i = 1-től m-1-ig:
        amíg j > 0 és P[i] != P[j]:
            j = pi[j - 1]
        ha P[i] == P[j]:
            j = j + 1
        pi[i] = j
    térj vissza pi

KMP keresés

KMP(T, P):
    n = T hossza
    m = P hossza
    pi = ComputePrefixFunction(P)
    j = 0  // Minta pozíciója
    ciklus i = 0-tól n-1-ig:
        amíg j > 0 és T[i] != P[j]:
            j = pi[j - 1]
        ha T[i] == P[j]:
            j = j + 1
        ha j == m:
            return i - m + 1  // Talált egyezés kezdőpozíciója
            j = pi[j - 1]
    térj vissza -1  // Nincs egyezés

Python implementáció

def compute_prefix_function(pattern):
    m = len(pattern)
    pi = [0] * m
    j = 0  # Prefix hossza

    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j

    return pi

def kmp_search(text, pattern):
    n = len(text)
    m = len(pattern)
    pi = compute_prefix_function(pattern)
    j = 0  # Minta pozíciója

    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            return i - m + 1  # Egyezés kezdőpozíciója
            j = pi[j - 1]

    return -1  # Nincs egyezés

# Példa használat
text = "ababcabcabababd"
pattern = "ababd"
result = kmp_search(text, pattern)
print(f"A minta kezdőpozíciója: {result}" if result != -1 else "Nincs egyezés.")

Kimenet: 

A minta kezdőpozíciója: 10

C++ implementáció

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

vector<int> compute_prefix_function(const string& pattern) {
    int m = pattern.size();
    vector<int> pi(m, 0);
    int j = 0;

    for (int i = 1; i < m; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        pi[i] = j;
    }

    return pi;
}

int kmp_search(const string& text, const string& pattern) {
    int n = text.size();
    int m = pattern.size();
    vector<int> pi = compute_prefix_function(pattern);
    int j = 0;

    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == m) {
            return i - m + 1;  // Egyezés kezdőpozíciója
        }
    }

    return -1;  // Nincs egyezés
}

int main() {
    string text = "ababcabcabababd";
    string pattern = "ababd";

    int result = kmp_search(text, pattern);
    if (result != -1) {
        cout << "A minta kezdőpozíciója: " << result << endl;
    } else {
        cout << "Nincs egyezés." << endl;
    }

    return 0;
}

Kimenet: 

A minta kezdőpozíciója: 10

Összegzés

Előnyök:

  1. Hatékonyság: (O(n + m)) időben működik, még a legrosszabb esetben is.
  2. Előfeldolgozás: Az ismétlődő összehasonlítások minimalizálása a prefix-függvénnyel.

Hátrányok:

  1. Komplexitás: Az algoritmus implementálása bonyolultabb, mint a naiv sztringkeresés.

A KMP algoritmus kiváló választás nagy szövegek gyors keresésére, például DNS-keresés, szövegbányászat vagy kódegyezés esetén.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Knuth-Morris-Pratt-algoritmus&oldid=3480587”