Ας φανταστούμε ότι έχεις μια μεγάλη σελίδα ενός βιβλίου και ψάχνεις ένα συγκεκριμένο λέξη ή φράση σε αυτή τη σελίδα. Μπορείς να διαβάζεις τη σελίδα από την αρχή προς το τέλος, και κάθε φορά που βρίσκεις τη λέξη που ψάχνεις, σταματάς.

Ο αλγόριθμος KMP κάνει κάτι παρόμοιο, αλλά πιο έξυπνα. Αντί να επιστρέψει κάθε φορά στην αρχή της φράσης που ψάχνει όταν δεν ταιριάζει, αυτός ο αλγόριθμος “θυμάται” τις πληροφορίες από τις προηγούμενες απόπειρες. Αυτό τον βοηθάει να παραλείψει κάποιες θέσεις και να κάνει την αναζήτηση πιο γρήγορη.

Ας δούμε αυτό με ένα παράδειγμα: Υποθέτουμε ότι θέλεις να βρεις τη λέξη “ΚΟΤΑ” μέσα σε ένα μεγάλο κείμενο. Ξεκινάς διαβάζοντας το κείμενο και όταν φτάνεις στα γράμματα “ΚΟΤΑΛ”, βλέπεις ότι η λέξη δεν ταιριάζει ακριβώς επειδή το τέλος είναι διαφορετικό. Αντί να ξαναρχίσεις από το δεύτερο γράμμα του κειμένου, ο KMP σου επιτρέπει να καταλάβεις ότι δεν υπάρχει τρόπος η λέξη “ΚΟΤΑ” να αρχίζει από το δεύτερο γράμμα της σειράς “ΚΟΤΑΛ”. Έτσι, αντί να χάσεις χρόνο, πηδάς κατευθείαν σε επόμενες θέσεις που έχουν νόημα να ελεγχθούν.

Στη C#, αυτός ο αλγόριθμος μπορεί να γραφτεί με τον εξής τρόπο: Χρησιμοποιείς έναν πίνακα που σε βοηθάει να “θυμάσαι” πού να πας στην επόμενη αναζήτηση, ανάλογα με το πού έχεις φτάσει στο κείμενο και τι έχεις διαβάσει μέχρι εκείνη τη στιγμή.

Αυτή η “μνήμη” σου εξοικονομεί χρόνο και κάνει την αναζήτηση πολύ πιο αποτελεσματική από το να ξεκινάς πάντα από την αρχή!

Ας δούμε πώς θα υλοποιούσαμε τον αλγόριθμο Knuth-Morris-Pratt (KMP) σε C# για να βρούμε τη λέξη “ΚΟΤΑ” μέσα σε ένα μεγαλύτερο κείμενο. Θα διαχωρίσουμε την υλοποίηση σε δύο βασικά μέρη: τη δημιουργία του πίνακα προθεμάτων (πίνακας LPS) και την αναζήτηση της λέξης με τη χρήση αυτού του πίνακα.

1. Δημιουργία του Πίνακα LPS

Ο πίνακας LPS (Longest Prefix Suffix) χρησιμοποιείται για να αποφεύγουμε την επανεξέταση των χαρακτήρων της λέξης-στόχου που έχουν ήδη ελεγχθεί. Το κάθε στοιχείο του πίνακα δείχνει το μήκος του μεγαλύτερου κοινού προθέματος και επιθέματος για την υποσυμβολοσειρά που τελειώνει στη θέση i.

2. Αναζήτηση με τον αλγόριθμο KMP

Χρησιμοποιώντας τον πίνακα LPS, η αναζήτηση γίνεται πιο αποδοτικά διότι αποφεύγουμε το άσκοπο ξαναέλεγχο των χαρακτήρων που έχουμε ήδη συγκρίνει.

using System;

class Program
{
    static void Main()
    {
        string text = "ΑΥΤΟ ΕΙΝΑΙ ΕΝΑ ΜΕΓΑΛΟ ΚΕΙΜΕΝΟ ΚΑΙ ΨΑΧΝΟΥΜΕ ΤΗΝ ΛΕΞΗ ΚΟΤΑ";
        string pattern = "ΚΟΤΑ";
        KMP_Search(text, pattern);
    }

    static void KMP_Search(string text, string pattern)
    {
        int M = pattern.Length;
        int N = text.Length;

        // LPS Array
        int[] lps = new int[M];
        ComputeLPSArray(pattern, M, lps);

        int i = 0; // index for text
        int j = 0; // index for pattern
        while (i < N)
        {
            if (pattern[j] == text[i])
            {
                j++;
                i++;
            }
            if (j == M)
            {
                Console.WriteLine("Found pattern at index " + (i - j));
                j = lps[j - 1];
            }
            else if (i < N && pattern[j] != text[i])
            {
                if (j != 0)
                    j = lps[j - 1];
                else
                    i = i + 1;
            }
        }
    }

    static void ComputeLPSArray(string pattern, int M, int[] lps)
    {
        int length = 0;
        int i = 1;
        lps[0] = 0; // lps[0] is always 0

        while (i < M)
        {
            if (pattern[i] == pattern[length])
            {
                length++;
                lps[i] = length;
                i++;
            }
            else
            {
                if (length != 0)
                {
                    length = lps[length - 1];
                }
                else
                {
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }
}

Στο παράδειγμα αυτό, υλοποιήσαμε την αναζήτηση της λέξης “ΚΟΤΑ” σε ένα μεγαλύτερο κείμενο. Ο κώδικας περιλαμβάνει τη δημιουργία του πίνακα LPS και την αναζήτηση με βάση αυτόν τον πίνακα.

ασκησειςDownload