Φαντάσου ότι έχεις ένα βιβλίο και θέλεις να βρεις μια συγκεκριμένη λέξη μέσα σε αυτό. Υπάρχει ένας πολύ γρήγορος τρόπος για να το κάνεις αυτό, που λέγεται αλγόριθμος Boyer-Moore.

Σκέψου τον αλγόριθμο Boyer-Moore σαν να παίζεις ένα παιχνίδι μνήμης με τις λέξεις στο βιβλίο. Αντί να κοιτάς κάθε γράμμα από την αρχή της λέξης προς το τέλος, ξεκινάς κοιτώντας τα γράμματα από το τέλος προς την αρχή.

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

Επιπλέον, ο Boyer-Moore χρησιμοποιεί κάτι που ονομάζεται “κανόνες ευκαιρίας”. Αν το γράμμα που βλέπεις δεν ταιριάζει, αντί να μετακινηθείς μόνο ένα γράμμα δεξιά, ο αλγόριθμος μπορεί να σε πηδήξει πολλά γράμματα δεξιά, παρακάμπτοντας τα γράμματα που ξέρεις ότι δεν έχουν νόημα να ελέγξεις. Αυτό το κάνει χρησιμοποιώντας δύο ειδικούς πίνακες που του λένε πόσο μπορεί να πηδήξει μπροστά ανάλογα με το γράμμα που βρήκε και τη θέση του γράμματος στη λέξη.

Αυτή η τακτική του να πηδάει πολλά γράμματα ταυτόχρονα κάνει τον αλγόριθμο Boyer-Moore πολύ γρήγορο, ειδικά αν η λέξη που ψάχνεις είναι μακριά ή αν το κείμενο είναι πολύ μεγάλο.

Στη C#, μπορούμε να γράψουμε τον αλγόριθμο Boyer-Moore χρησιμοποιώντας κάποιες βασικές δομές δεδομένων όπως πίνακες για να κρατήσουμε τους κανόνες ευκαιρίας και να εκτελέσουμε τις αναζητήσεις. Αν θες, μπορώ να σου δείξω πώς να γράψεις ένα τέτοιο πρόγραμμα.

Ας δούμε πώς μπορείς να υλοποιήσεις τον αλγόριθμο Boyer-Moore σε C# για να αναζητήσεις μια υποσυμβολοσειρά μέσα σε ένα μεγαλύτερο κείμενο. Αυτή η υλοποίηση θα χρησιμοποιήσει τον πίνακα τελευταίας εμφάνισης για την ευκαιρία πήδηματος, παρακάμπτοντας σημεία του κειμένου που δεν είναι πιθανό να οδηγήσουν σε αντιστοιχία.

Κώδικας C# για τον αλγόριθμο Boyer-Moore

using System;
using System.Collections.Generic;

public class BoyerMooreSearch
{
public static void Main()
{
string text = “Εδώ είναι ένα μεγάλο κείμενο όπου ψάχνουμε τη λέξη ‘ΚΟΤΑ'”;
string pattern = “ΚΟΤΑ”;
int position = Search(text, pattern);
if (position != -1)
Console.WriteLine($”Η λέξη ‘{pattern}’ βρέθηκε στη θέση: {position}”);
else
Console.WriteLine(“Η λέξη δεν βρέθηκε.”);
}

public static int Search(string text, string pattern)
{
    int n = text.Length;
    int m = pattern.Length;
    Dictionary<char, int> lastOccurrence = BuildLastOccurrenceTable(pattern);

    int i = m - 1;
    while (i < n)
    {
        int j = m - 1;
        while (j >= 0 && pattern[j] == text[i])
        {
            j--;
            i--;
        }
        if (j < 0)
        {
            return i + 1; // Βρέθηκε η λέξη
        }
        else
        {
            i += Math.Max(1, j - lastOccurrence.GetValueOrDefault(text[i], -1));
        }
    }
    return -1; // Η λέξη δεν βρέθηκε
}

private static Dictionary<char, int> BuildLastOccurrenceTable(string pattern)
{
    var lastOccurrence = new Dictionary<char, int>();
    for (int i = 0; i < pattern.Length; i++)
    {
        lastOccurrence[pattern[i]] = i;
    }
    return lastOccurrence;
}
}

Πώς λειτουργεί αυτός ο κώδικας:

  1. Κατασκευή Πίνακα Τελευταίας Εμφάνισης: Αυτός ο πίνακας περιέχει την τελευταία θέση κάθε χαρακτήρα του προτύπου μέσα στη λέξη-στόχο. Είναι ένας λεξικό που αποθηκεύει για κάθε χαρακτήρα την τελευταία του θέση στο πρότυπο.

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

  1. Επανάληψη: Ο αλγόριθμος συνεχίζει να μετακινείται στο κείμενο μέχρι να βρει τη λέξη ή να εξαντληθεί το κείμενο.

Αυτός ο κώδικας αποτελεί ένα βασικό παράδειγμα του αλγόριθμου Boyer-Moore και είναι πολύ αποτελεσματικός για την αναζήτηση υποσυμβολοσειρών σε μεγάλα κείμενα, καθώς ελαχιστοποιεί τον αριθμό των συγκρίσεων.

ασκησειςDownload