Przeczytaj

Algorytm Knutha‑Morrisa‑Pratta – implementacja w języku Java

Z e‑materiału Algorytm Knutha‑Morrisa‑PrattaPAWg1XbykAlgorytm Knutha‑Morrisa‑Pratta wiemy, że algorytm KMP jest rozszerzeniem algorytmu MP. Oba algorytmy zakładają zbudowanie tablicy częściowych dopasowań poprzez wcześniejszą analizę wzorca. Generowanie procesu przeszukiwania tekstu poprzedzone jest etapem budowy tablicy. Jednak dzięki mniejszej liczbie porównań, starty czasowe są zniwelowane.

W jaki sposób budujemy tablicę częściowych dopasowań? Jest to proces polegający na sprawdzaniu, jakiej szerokości są najdłuższe występujące w kolejnych prefiksachprefiksprefiksach wzorca prefikso‑sufiksyprefikso‑sufiksprefikso‑sufiksy.

Cały proces budowy tablicy częściowych dopasowań analizowaliśmy również w ramach zawartego w tej lekcji filmu. Powtórzyliśmy w nim najważniejsze pojęcia oraz zgłębiliśmy działanie opisywanego algorytmu z wyszczególnieniem wszystkich możliwych wariantów. Zdobytą, teoretyczną wiedzę wykorzystaliśmy także do zaimplementowania budowy tablicy w języku Java.

Inna, ale analogiczna do zawartej w filmie implementacja budowy tablicy została zaprezentowana poniżej. Możesz spróbować porównać obie implementacje i ocenić występujące różnice.

Specyfikacja problemu:

Dane:

wzorzec – łańcuch znaków

Wynik:

Program wyświetla długości prefikso‑sufiksów kolejnych prefiksów łańcucha wzorzec.

Linia 1. static int otwórz nawias kwadratowy zamknij nawias kwadratowy budowaTablicyKMP otwórz nawias okrągły String wzorzec zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. int rozmiarT znak równości wzorzec kropka length otwórz nawias okrągły zamknij nawias okrągły plus 1 średnik. Linia 3. int otwórz nawias kwadratowy zamknij nawias kwadratowy T znak równości new int otwórz nawias kwadratowy rozmiarT zamknij nawias kwadratowy średnik. Linia 4. int poz znak równości minus 1 średnik. Linia 5. T otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości minus 1 średnik. Linia 7. prawy ukośnik prawy ukośnik dla każdego kolejnego prefiksu wzorca. Linia 8. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny rozmiarT średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. prawy ukośnik prawy ukośnik dopóki możesz znaleźć dłuższy prefikso minus sufiks. Linia 10. while otwórz nawias okrągły poz zamknij nawias ostrokątny minus 1 ampersant ampersant wzorzec kropka charAt otwórz nawias okrągły poz zamknij nawias okrągły wykrzyknik znak równości wzorzec kropka charAt otwórz nawias okrągły i minus 1 zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. poz znak równości T otwórz nawias kwadratowy poz zamknij nawias kwadratowy średnik. Linia 12. zamknij nawias klamrowy. Linia 13. plus plus poz średnik. Linia 15. prawy ukośnik prawy ukośnik jeżeli element występujący po znalezionym. Linia 16. prawy ukośnik prawy ukośnik prefikso minus sufiksie jest taki sam jak po prefiksie. Linia 17. if otwórz nawias okrągły i znak równości znak równości rozmiarT minus 1 kreska pionowa kreska pionowa wzorzec kropka charAt otwórz nawias okrągły i zamknij nawias okrągły wykrzyknik znak równości wzorzec kropka charAt otwórz nawias okrągły poz zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. prawy ukośnik prawy ukośnik zapisz szerokość znalezionego prefikso minus sufiksu. Linia 19. T otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości poz średnik. Linia 20. zamknij nawias klamrowy. Linia 21. else otwórz nawias klamrowy. Linia 22. prawy ukośnik prawy ukośnik kolejny element tablicy będzie tym samym przecinek. Linia 23. prawy ukośnik prawy ukośnik co element na pozycji równej szerokości. Linia 24. prawy ukośnik prawy ukośnik prefikso minus sufiksu. Linia 25. T otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości T otwórz nawias kwadratowy poz zamknij nawias kwadratowy średnik. Linia 26. zamknij nawias klamrowy. Linia 27. zamknij nawias klamrowy. Linia 29. return T średnik. Linia 30. zamknij nawias klamrowy.

static int[] budowaTablicyKMP(String wzorzec) {
    int rozmiarT = wzorzec.length() + 1;
    int[] T = new int[rozmiarT];
    int poz = -1;
    T[0] = -1;

    // dla każdego kolejnego prefiksu wzorca
    for (int i = 1; i < rozmiarT; ++i) {
        // dopóki możesz znaleźć dłuższy prefikso-sufiks
        while(poz > -1 && wzorzec.charAt(poz) != wzorzec.charAt(i - 1)) {
            poz = T[poz];
        }
        ++poz;

        // jeżeli element występujący po znalezionym
        // prefikso-sufiksie jest taki sam jak po prefiksie
        if (i == rozmiarT - 1 || wzorzec.charAt(i) != wzorzec.charAt(poz)) {
            // zapisz szerokość znalezionego prefikso-sufiksu
            T[i] = poz;
        }
        else {
            // kolejny element tablicy będzie tym samym,
            // co element na pozycji równej szerokości
            // prefikso-sufiksu
            T[i] = T[poz];
        }
    }

    return T;
}

Po zbudowaniu tablicy częściowych dopasowań, możemy przejść do poszukiwania wzorca w tekście. Analizę tego elementu oraz jego implementację w języku Java również znajdziemy w filmie edukacyjnym.

Oto przykładowa implementacja wyszukiwania wzorca w tekście (również alternatywna w stosunku do implementacji zawartej w filmie), działająca zarówno dla tablicy wyznaczonej metodą MP, jak i KMP (wystarczy tylko zamienić funkcję budującą tablicę dopasowań).

Specyfikacja problemu:

Dane:

wzorzec – łańcuch znaków; poszukiwany wzorzec
tekst – łańcuch znaków

Wynik:

Program wyświetla pozycje wystąpień wzorca w łańcuchu. Wartość -1 nie wskazuje żadnej pozycji wzorca i oznacza, iż wzorzec nie pojawia się w przeszukiwanym łańcuchu.

static int szukajWzorcaKMP(String wzorzec, String tekst) {
    int[] tablicaDopasowan = budowaTablicyKMP(wzorzec);

    int b = 0;
    for (int i = 0; i < tekst.length(); ++i) {
        while (b > -1 && wzorzec.charAt(b) != tekst.charAt(i)) {
            b = tablicaDopasowan[b];
        }
        ++b;

        if (b == wzorzec.length()) {
            // znaleziono dopasowanie
            return i - wzorzec.length() + 1;
        }
    }
    // nie znaleziono dopasowania
    return -1;
}

Przykładowy program napisany w języku Java, który za pomocą algorytmu Knutha‑Morrisa‑Pratta wyszukuje wzorzec w tekście, może wyglądać tak:

Linia 1. public class Main otwórz nawias klamrowy. Linia 2. static int otwórz nawias kwadratowy zamknij nawias kwadratowy budowaTablicyKMP otwórz nawias okrągły String wzorzec zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. int rozmiarT znak równości wzorzec kropka length otwórz nawias okrągły zamknij nawias okrągły plus 1 średnik. Linia 4. int otwórz nawias kwadratowy zamknij nawias kwadratowy T znak równości new int otwórz nawias kwadratowy rozmiarT zamknij nawias kwadratowy średnik. Linia 5. int poz znak równości minus 1 średnik. Linia 6. T otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości minus 1 średnik. Linia 8. prawy ukośnik prawy ukośnik dla każdego kolejnego prefiksu wzorca. Linia 9. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny rozmiarT średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. prawy ukośnik prawy ukośnik dopóki możesz znaleźć dłuższy prefikso minus sufiks. Linia 11. while otwórz nawias okrągły poz zamknij nawias ostrokątny minus 1 ampersant ampersant wzorzec kropka charAt otwórz nawias okrągły poz zamknij nawias okrągły wykrzyknik znak równości wzorzec kropka charAt otwórz nawias okrągły i minus 1 zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. poz znak równości T otwórz nawias kwadratowy poz zamknij nawias kwadratowy średnik. Linia 13. zamknij nawias klamrowy. Linia 14. plus plus poz średnik. Linia 16. prawy ukośnik prawy ukośnik jeżeli element występujący po znalezionym. Linia 17. prawy ukośnik prawy ukośnik prefikso minus sufiksie jest taki sam jak po prefiksie. Linia 18. if otwórz nawias okrągły i znak równości znak równości rozmiarT minus 1 kreska pionowa kreska pionowa wzorzec kropka charAt otwórz nawias okrągły i zamknij nawias okrągły wykrzyknik znak równości wzorzec kropka charAt otwórz nawias okrągły poz zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. prawy ukośnik prawy ukośnik zapisz szerokość znalezionego prefikso minus sufiksu. Linia 20. T otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości poz średnik. Linia 21. zamknij nawias klamrowy. Linia 22. else otwórz nawias klamrowy. Linia 23. prawy ukośnik prawy ukośnik kolejny element tablicy będzie tym samym przecinek. Linia 24. prawy ukośnik prawy ukośnik co element na pozycji równej szerokości. Linia 25. prawy ukośnik prawy ukośnik prefikso minus sufiksu. Linia 26. T otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości T otwórz nawias kwadratowy poz zamknij nawias kwadratowy średnik. Linia 27. zamknij nawias klamrowy. Linia 28. zamknij nawias klamrowy. Linia 30. return T średnik. Linia 31. zamknij nawias klamrowy. Linia 33. static int szukajWzorcaKMP otwórz nawias okrągły String wzorzec przecinek String tekst zamknij nawias okrągły otwórz nawias klamrowy. Linia 34. int otwórz nawias kwadratowy zamknij nawias kwadratowy tablicaDopasowan znak równości budowaTablicyKMP otwórz nawias okrągły wzorzec zamknij nawias okrągły średnik. Linia 36. int b znak równości 0 średnik. Linia 37. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny tekst kropka length otwórz nawias okrągły zamknij nawias okrągły średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 38. while otwórz nawias okrągły b zamknij nawias ostrokątny minus 1 ampersant ampersant wzorzec kropka charAt otwórz nawias okrągły b zamknij nawias okrągły wykrzyknik znak równości tekst kropka charAt otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 39. b znak równości tablicaDopasowan otwórz nawias kwadratowy b zamknij nawias kwadratowy średnik. Linia 40. zamknij nawias klamrowy. Linia 41. plus plus b średnik. Linia 43. if otwórz nawias okrągły b znak równości znak równości wzorzec kropka length otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 44. prawy ukośnik prawy ukośnik znaleziono dopasowanie. Linia 45. return i minus wzorzec kropka length otwórz nawias okrągły zamknij nawias okrągły plus 1 średnik. Linia 46. zamknij nawias klamrowy. Linia 47. zamknij nawias klamrowy. Linia 48. prawy ukośnik prawy ukośnik nie znaleziono dopasowania. Linia 49. return minus 1 średnik. Linia 50. zamknij nawias klamrowy. Linia 52. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 53. String tekst znak równości cudzysłów ala ma kota cudzysłów średnik. Linia 55. System kropka out kropka println otwórz nawias okrągły szukajWzorcaKMP otwórz nawias okrągły cudzysłów ala cudzysłów przecinek tekst zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 56. System kropka out kropka println otwórz nawias okrągły szukajWzorcaKMP otwórz nawias okrągły cudzysłów ma cudzysłów przecinek tekst zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 57. System kropka out kropka println otwórz nawias okrągły szukajWzorcaKMP otwórz nawias okrągły cudzysłów kota cudzysłów przecinek tekst zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 58. System kropka out kropka println otwórz nawias okrągły szukajWzorcaKMP otwórz nawias okrągły cudzysłów nie cudzysłów przecinek tekst zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 59. zamknij nawias klamrowy. Linia 60. zamknij nawias klamrowy.

public class Main {
    static int[] budowaTablicyKMP(String wzorzec) {
        int rozmiarT = wzorzec.length() + 1;
        int[] T = new int[rozmiarT];
        int poz = -1;
        T[0] = -1;

        // dla każdego kolejnego prefiksu wzorca
        for (int i = 1; i < rozmiarT; ++i) {
            // dopóki możesz znaleźć dłuższy prefikso-sufiks
            while(poz > -1 && wzorzec.charAt(poz) != wzorzec.charAt(i - 1)) {
                poz = T[poz];
            }
            ++poz;

            // jeżeli element występujący po znalezionym
            // prefikso-sufiksie jest taki sam jak po prefiksie
            if (i == rozmiarT - 1 || wzorzec.charAt(i) != wzorzec.charAt(poz)) {
                // zapisz szerokość znalezionego prefikso-sufiksu
                T[i] = poz;
            }
            else {
                // kolejny element tablicy będzie tym samym,
                // co element na pozycji równej szerokości
                // prefikso-sufiksu
                T[i] = T[poz];
            }
        }

        return T;
    }

    static int szukajWzorcaKMP(String wzorzec, String tekst) {
        int[] tablicaDopasowan = budowaTablicyKMP(wzorzec);

        int b = 0;
        for (int i = 0; i < tekst.length(); ++i) {
            while (b > -1 && wzorzec.charAt(b) != tekst.charAt(i)) {
                b = tablicaDopasowan[b];
            }
            ++b;

            if (b == wzorzec.length()) {
                // znaleziono dopasowanie
                return i - wzorzec.length() + 1;
            }
        }
        // nie znaleziono dopasowania
        return -1;
    }

    public static void main(String[] args) {
        String tekst = "ala ma kota";

        System.out.println(szukajWzorcaKMP("ala", tekst));
        System.out.println(szukajWzorcaKMP("ma", tekst));
        System.out.println(szukajWzorcaKMP("kota", tekst));
        System.out.println(szukajWzorcaKMP("nie", tekst));
    }
}

Wynik działania przedstawionego programu:

Słownik

prefiks

początkowa część łańcucha znaków składająca się z k znaków (k pierwszych znaków łańcucha)

sufiks

końcowa część łańcucha znaków składająca się z k znaków (k ostatnich znaków łańcucha)

prefikso‑sufiks

składający się z k znaków prefiks danego łańcucha znaków, który jest jednocześnie jego sufiksem (część łańcucha znaków występująca zarówno na jego początku, jak i końcu)

Aplet

Sprawdź się

Algorytm Knutha‑Morrisa‑Pratta – implementacja w języku Java

Słownik