Επιστήμη Δεδομένων Και Βάσεις Δεδομένων
Κατακτήστε την αναζήτηση συμβολοσειρών με τον αλγόριθμο Aho-Corasick
Ο χειρισμός συμβολοσειρών και η εύρεση μοτίβων σε αυτά είναι θεμελιώδεις εργασίες στην επιστήμη των δεδομένων και μια τυπική εργασία για κάθε προγραμματιστή.
Οι αποτελεσματικοί αλγόριθμοι συμβολοσειρών παίζουν σημαντικό ρόλο σε πολλές διαδικασίες επιστήμης δεδομένων. Είναι συχνά αυτά που καθιστούν τέτοιες διαδικασίες αρκετά εφικτές για πρακτική χρήση.
Σε αυτό το άρθρο, θα μάθετε για έναν από τους πιο ισχυρούς αλγόριθμους για την εύρεση μοτίβων σε μεγάλο αριθμό κειμένου: τον αλγόριθμο Aho-Corasick. Αυτός ο αλγόριθμος χρησιμοποιεί ένα δομή δεδομένων (προφέρεται 'δοκιμή') για να παρακολουθείτε τα μοτίβα αναζήτησης και χρησιμοποιεί μια απλή μέθοδο για την αποτελεσματική εύρεση όλων των εμφανίσεων ενός δεδομένου συνόλου μοτίβων σε οποιοδήποτε συννεφάκι κειμένου.
Ένα προηγούμενο άρθρο στο ApeeScape Engineering Blog έδειξε έναν αλγόριθμο αναζήτησης συμβολοσειρών για το ίδιο πρόβλημα. Η προσέγγιση που ακολουθείται σε αυτό το άρθρο προσφέρει καλύτερη υπολογιστική πολυπλοκότητα.
Ο αλγόριθμος Knuth-Morris-Pratt (KMP)
Για να καταλάβουμε πώς μπορούμε να αναζητήσουμε αποτελεσματικά πολλά μοτίβα σε ένα κείμενο, πρέπει πρώτα να αντιμετωπίσουμε ένα ευκολότερο πρόβλημα: αναζητώντας ένα μοτίβο σε ένα δεδομένο κείμενο.
Ας υποθέσουμε ότι έχουμε ένα μεγάλο κούμπωμα μήκους Ν και ένα μοτίβο (που θέλουμε να βρούμε στο κείμενο) του μήκους Μ . Εάν θέλουμε να αναζητήσουμε μια εμφάνιση αυτού του μοτίβου ή όλες τις εμφανίσεις, μπορούμε να επιτύχουμε μια υπολογιστική πολυπλοκότητα Ο (Ν + Μ) χρησιμοποιώντας τον αλγόριθμο KMP.
Λειτουργία προθέματος
Ο αλγόριθμος KMP λειτουργεί υπολογίζοντας μια συνάρτηση προθέματος του μοτίβου που αναζητούμε. Η συνάρτηση προθέματος υπολογίζει μια εναλλακτική θέση για κάθε πρόθεμα στο μοτίβο.
Ας ορίσουμε το μοτίβο αναζήτησης ως συμβολοσειρά, με την ετικέτα S. Για κάθε υπόστρωμα S [0..i], όπου i> = 1, θα βρούμε το μέγιστο πρόθεμα αυτής της συμβολοσειράς που είναι επίσης το επίθημα αυτής της συμβολοσειράς. Θα σημειώσουμε το μήκος αυτού του προθέματος P [i].
Για το μοτίβο 'abracadabra', η συνάρτηση προθέματος θα παράγει τις ακόλουθες θέσεις υποστήριξης:
Ευρετήριο (i) | 0 | ένας | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Χαρακτήρας | προς το | σι | ρ | προς το | ντο | προς το | ρε | προς το | σι | ρ | προς το |
Μήκος προθέματος (P[i]) | 0 | 0 | 0 | ένας | 0 | ένας | 0 | ένας | 2 | 3 | 4 |
Η συνάρτηση προθέματος προσδιορίζει ένα ενδιαφέρον χαρακτηριστικό του μοτίβου.
Ας πάρουμε ένα συγκεκριμένο πρόθεμα του μοτίβου ως παράδειγμα: 'abracadab'. Η τιμή της συνάρτησης προθέματος για αυτό το πρόθεμα είναι δύο. Αυτό δείχνει ότι για αυτό το πρόθεμα 'abracadab', υπάρχει ένα επίθημα μήκους δύο που ταιριάζει ακριβώς με το πρόθεμα του μήκους δύο (δηλαδή, το μοτίβο ξεκινά με 'ab' και το πρόθεμα τελειώνει με 'ab'). Επίσης, αυτός είναι ο μεγαλύτερος αγώνας για αυτό το πρόθεμα.
Εκτέλεση
Εδώ είναι μια συνάρτηση C # που μπορεί να χρησιμοποιηθεί για τον υπολογισμό της συνάρτησης προθέματος για οποιαδήποτε συμβολοσειρά:
public int[] CalcPrefixFunction(String s) { int[] result = new int[s.Length]; // matriz con valores de función de prefijo result[0] = 0; // la función de prefijo siempre es cero para el primer símbolo (su caso degenerado) int k = 0; // valor actual de la función de prefijo para (int i = 1; i 0 && s[i] != s[k]) k = result[k - 1]; if (s[k] == s[i]) k++; // hemos encontrado el prefijo más largo - caso 1 result[i] = k; // almacenar este resultado en la matriz } resultado de devolución; } Εκτελώντας αυτήν τη λειτουργία σε ένα ελαφρώς μεγαλύτερο μοτίβο, το 'abcdabcabcdabcdab' παράγει αυτό:
Ευρετήριο (i) | 0 | ένας | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | έντεκα | 12 | 13 | 14 | δεκαπέντε | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Χαρακτήρας | προς το | σι | ντο | ρε | προς το | σι | ντο | προς το | σι | ντο | ρε | προς το | σι | ντο | ρε | προς το | σι |
Λειτουργία προθέματος (P[i]) | 0 | 0 | 0 | 0 | ένας | 2 | 3 | ένας | 2 | 3 | 4 | 5 | 6 | 7 | 4 | 5 | 6 |
Υπολογιστική πολυπλοκότητα
Παρόλο που υπάρχουν δύο ένθετοι βρόχοι, η πολυπλοκότητα της λειτουργίας προθέματος είναι απλά Ο (Μ) , που Μ είναι το μήκος του μοτίβου μικρό .
Αυτό μπορεί να εξηγηθεί εύκολα εξετάζοντας τον τρόπο λειτουργίας των βρόχων.
Όλες οι επαναλήψεις του εξωτερικού βρόχου μέσω i Μπορούν να χωριστούν σε τρεις περιπτώσεις:
-
Αύξηση
kσε μια. Ο βρόχος ολοκληρώνει μία επανάληψη. -
Δεν αλλάζει την τιμή μηδέν
k. Ο βρόχος ολοκληρώνει μία επανάληψη. -
Δεν αλλάζει ή μειώνει μια θετική τιμή
k.
Οι δύο πρώτες περιπτώσεις μπορούν να εκτελεστούν το πολύ Μ φορές.
100 κορυφαία γραφεία μεμονωμένης οικογένειας
Για την τρίτη περίπτωση, ας ορίσουμε P (s, i) = k1 και P (s, i + 1) = k2, k2 <= k1. Κάθε μία από αυτές τις περιπτώσεις πρέπει να προηγείται των συμβάντων k1 - k2 της πρώτης περίπτωσης. Ο αριθμός των μειώσεων δεν υπερβαίνει το k1 - k2 + 1. Και συνολικά δεν έχουμε περισσότερα από 2 * Μ επαναλήψεις
Επεξήγηση του δεύτερου παραδείγματος
Ας δούμε το δεύτερο παράδειγμα μοτίβο 'abcdabcabcdabcdab'. Δείτε πώς η συνάρτηση προθέματος την επεξεργάζεται βήμα προς βήμα:
-
Για ένα κενό υπόστρωμα και ένα υπόστρωμα 'a' μήκους, η τιμή της συνάρτησης προθέματος ορίζεται στο μηδέν. (
k = 0) -
Κοιτάξτε το υπόστρωμα 'ab'. Η τρέχουσα τιμή
kείναι μηδέν και ο χαρακτήρας 'b' δεν είναι ίσος με τον χαρακτήρα 'a'. Εδώ, έχουμε τη δεύτερη περίπτωση από την προηγούμενη ενότητα. Η τιμή τουkπαραμένει μηδέν και η τιμή της λειτουργίας προθέματος για το υπόστρωμα 'ab' είναι επίσης μηδέν. -
Είναι το ίδιο για τα υποστρώματα 'abc' και 'abcd'. Δεν υπάρχουν προθέματα που είναι επίσης τα επίθημα αυτών των υποσυνόλων. Η τιμή για αυτούς παραμένει μηδέν.
-
Τώρα ας δούμε μια ενδιαφέρουσα περίπτωση, το υπόστρωμα 'abcda'. Η τρέχουσα τιμή
kείναι ακόμα μηδέν, αλλά ο τελευταίος χαρακτήρας του υποστρώματος μας ταιριάζει με τον πρώτο του χαρακτήρα. Αυτό ενεργοποιεί την κατάστασηs [k] == s [i], όπουk == 0καιi == 4. Ο πίνακας έχει δείκτη μηδέν καιkείναι το ευρετήριο του επόμενου χαρακτήρα στο πρόθεμα μέγιστου μήκους. Αυτό σημαίνει ότι βρήκαμε το πρόθεμα μέγιστου μήκους για το υπόστρωμα που είναι επίσης επίθημα. Έχουμε την πρώτη περίπτωση, όπου η νέα τιμήkείναι ένα και επομένως η τιμή της συνάρτησης προθέματος Ρ ('abcda') Είναι ένα. -
Η ίδια περίπτωση εμφανίζεται επίσης για τα ακόλουθα δύο υποστρώματα, P ('abcdab') = 2 Υ P ('abcdabc') = 3 . Εδώ, αναζητούμε το μοτίβο μας στο κείμενο, συγκρίνοντας τις συμβολοσειρές χαρακτήρες με χαρακτήρα. Ας πούμε ότι οι πρώτοι επτά χαρακτήρες του μοτίβου ταιριάζουν με περίπου επτά διαδοχικούς χαρακτήρες επεξεργασμένου κειμένου, αλλά ο όγδοος χαρακτήρας δεν ταιριάζει. Τι πρέπει να συμβεί στη συνέχεια; Στην περίπτωση μιας αφελής αντιστοίχισης συμβολοσειράς, πρέπει να επιστρέψουμε επτά χαρακτήρες και να ξεκινήσουμε ξανά τη διαδικασία σύγκρισης από τον πρώτο χαρακτήρα του μοτίβου μας. Με την τιμή της λειτουργίας προθέματος (εδώ P ('abcdabc') = 3 ) γνωρίζουμε ότι το επίθημα τριών χαρακτήρων αντιστοιχεί ήδη σε τρεις χαρακτήρες κειμένου. Και αν ο επόμενος χαρακτήρας του κειμένου είναι 'd', το μήκος του αντίστοιχου υποστρώματος του μοτίβου μας και του υποστρώματος στο κείμενο αυξάνεται σε τέσσερα ('abcd'). Αντιθέτως, P ('abc') = 0 και θα ξεκινήσουμε τη διαδικασία σύγκρισης από τον πρώτο χαρακτήρα του μοτίβου. Αλλά το σημαντικό είναι ότι δεν επιστρέφουμε κατά τη διάρκεια της επεξεργασίας κειμένου.
-
Το επόμενο υπόστρωμα είναι 'abcdabca'. Στο υπόστρωμα παραπάνω, η συνάρτηση προθέματος ισούται με τρία. Αυτό σημαίνει ότι
k = 3είναι μεγαλύτερο από το μηδέν και ταυτόχρονα έχουμε αναντιστοιχία μεταξύ του επόμενου χαρακτήρα στο πρόθεμα (s [k] = s [3] = 'd') και του επόμενου χαρακτήρα στο επίθημα (s [i] = s [7] ='a'). Αυτό σημαίνει ότι ενεργοποιούμε την συνθήκηs [k]! =S [i]και ότι το πρόθεμα 'abcd' δεν μπορεί να είναι το επίθημα της συμβολοσειράς μας. Πρέπει να μειώσουμε την τιμή τουkκαι πάρτε το παραπάνω πρόθεμα για σύγκριση, όταν είναι δυνατόν. Όπως περιγράψαμε νωρίτερα, ο πίνακας έχει δείκτη μηδέν καιkείναι το ευρετήριο του επόμενου χαρακτήρα που ελέγχουμε από το πρόθεμα. Το τελευταίο ευρετήριο του τρέχοντος προθέματος είναιk - 1. Παίρνουμε την τιμή της συνάρτησης προθέματος για το τρέχον αντίστοιχο πρόθεμαk = resultado [k - 1]. Στην περίπτωσή μας (η τρίτη περίπτωση) το μήκος του μέγιστου προθέματος θα μειωθεί στο μηδέν και στη συνέχεια στην επόμενη γραμμή θα αυξηθεί σε ένα, επειδή το 'a' είναι το μέγιστο πρόθεμα που είναι επίσης το επίθημα του υποστρώματος μας. -
(Εδώ συνεχίζουμε τη διαδικασία υπολογισμού μας μέχρι να φτάσουμε σε μια πιο ενδιαφέρουσα περίπτωση.)
-
Αρχίζουμε να επεξεργαζόμαστε το ακόλουθο substring: 'abcdabcabcdabcd'. Η τρέχουσα τιμή
kείναι επτά. Όπως και με το 'abcdabca' παραπάνω, έχουμε χτυπήσει έναν μη αγώνα: Επειδή ο χαρακτήρας 'a' (ο έβδομος χαρακτήρας) δεν είναι ίσος με τον χαρακτήρα 'd', το υπόστρωμα 'abcdabca' δεν μπορεί να είναι το επίθημα της συμβολοσειράς μας. Τώρα λαμβάνουμε την ήδη υπολογιζόμενη τιμή από τη συνάρτηση προθέματος για 'abcdabc' (τρία) και τώρα έχουμε έναν αγώνα: το πρόθεμα 'abcd' είναι επίσης το επίθημα της συμβολοσειράς μας. Το μέγιστο πρόθεμά του και η τιμή της συνάρτησης προθέματος για το substring μας είναι τέσσερα, επειδή αυτή είναι η τρέχουσα τιμήk. -
Συνεχίζουμε αυτήν τη διαδικασία μέχρι το τέλος του προτύπου.
Εν ολίγοις: και οι δύο κύκλοι δεν λαμβάνουν περισσότερες από 3M επαναλήψεις, πράγμα που δείχνει ότι η πολυπλοκότητα είναι O (M). Η χρήση μνήμης είναι επίσης O (M).
Υλοποίηση αλγορίθμου KMP
public int KMP(String text, String s) { int[] p = CalcPrefixFunction(s); // Calcular la función de prefijo para una cadena de patrón // La idea es la misma que en la función de prefijo descrita anteriormente, pero ahora // estamos comparando prefijos de texto y patrón. // El valor del prefijo de longitud máxima de la cadena del patrón que se encontró // en el texto: int maxPrefixLength = 0; for (int i = 0; i 0 && text[i] != s[maxPrefixLength]) maxPrefixLength = p[maxPrefixLength - 1]; // Si ocurrió una coincidencia, aumenta la longitud de la longitud máxima // prefijo. if (s[maxPrefixLength] == text[i]) maxPrefixLength++; // Si la longitud del prefijo tiene la misma longitud que la cadena del patrón, // significa que hemos encontrado una subcadena coincidente en el texto. if (maxPrefixLength == s.Length) { // Podemos devolver este valor o realizar esta operación. int idx = i - s.Length + 1; // Obtenga el prefijo de longitud máxima anterior y continúe la búsqueda. maxPrefixLength = p[maxPrefixLength - 1]; } } return -1; } Ο παραπάνω αλγόριθμος επαναλαμβάνει το κείμενο, τον χαρακτήρα ανά χαρακτήρα και προσπαθεί να αυξήσει το μέγιστο πρόθεμα τόσο για το μοτίβο μας όσο και για μια ακολουθία διαδοχικών χαρακτήρων στο κείμενο. Σε περίπτωση αποτυχίας, δεν θα επιστρέψουμε στην προηγούμενη θέση μας στο κείμενο. Γνωρίζουμε το μέγιστο πρόθεμα του εντοπισμένου υποστρώματος του μοτίβου. Αυτό το πρόθεμα είναι επίσης το επίθημα αυτού του εντοπισμένου υποστρώματος και μπορούμε απλώς να συνεχίσουμε την αναζήτηση.
Η πολυπλοκότητα αυτής της συνάρτησης είναι ίδια με τη συνάρτηση προθέματος, η οποία καθιστά τη συνολική υπολογιστική πολυπλοκότητα Ο (Ν + Μ) με Ο (Μ) μνήμη.
Trivia: Το
String.IndexOf ()καιString.Contains ()στο πλαίσιο .NET έχουν έναν αλγόριθμο με την ίδια πολυπλοκότητα κάτω από την κουκούλα.
Ο αλγόριθμος Aho-Corasick
Τώρα θέλουμε να κάνουμε το ίδιο για πολλά μοτίβα.
Ας υποθέσουμε ότι υπάρχουν μοτίβα Μ μήκους L1 , L2 , ..., Λμμ . Πρέπει να βρούμε όλους τους συνδυασμούς μοτίβων από ένα λεξικό σε ένα κείμενο μήκους Ν .
Μια ασήμαντη λύση θα ήταν να πάρετε οποιονδήποτε αλγόριθμο από το πρώτο μέρος και να τον εκτελέσετε ** M ** φορές. Έχουμε πολυπλοκότητα O (N + L1 + N + L2 +… + N + Lm) , δηλαδή (Μ * Ν + Λ) .
Οποιαδήποτε σοβαρή δοκιμή σκοτώνει αυτόν τον αλγόριθμο.
Η λήψη ενός λεξικού με τις 1.000 πιο κοινές αγγλικές λέξεις ως μοτίβα και η χρήση του για την αναζήτηση της αγγλικής έκδοσης του 'Πολέμου και Ειρήνης' του Τολστόι θα χρειαζόταν αρκετός χρόνος. Το βιβλίο έχει περισσότερους από τρία εκατομμύρια χαρακτήρες.
Εάν πάρουμε τις 10.000 πιο κοινές λέξεις στα Αγγλικά, ο αλγόριθμος θα λειτουργεί περίπου 10 φορές πιο αργός. Προφανώς σε εισόδους μεγαλύτερες από αυτό, ο χρόνος εκτέλεσης θα αυξηθεί επίσης.
Αυτό είναι όπου ο αλγόριθμος Aho-Corasick λειτουργεί τη μαγεία του.
Η πολυπλοκότητα του αλγόριθμου Aho-Corasick είναι O (N + L + Z) , που ΜΕ είναι ο αριθμός των αγώνων. Αυτός ο αλγόριθμος εφευρέθηκε από Άλφρεντ Β. Αχό Υ Margaret J. Corasick το 1975.
Εκτέλεση
Εδώ χρειαζόμαστε ένα trie, και προσθέτουμε στον αλγόριθμό μας μια ιδέα παρόμοια με τις συναρτήσεις προθέματος που περιγράφονται παραπάνω. Θα υπολογίσουμε τις τιμές συνάρτησης προθέματος για ολόκληρο το λεξικό.
Κάθε κορυφή στο trie αποθηκεύει τις ακόλουθες πληροφορίες:
public class Vertex { public Vertex() { Children = new Hashtable(); Leaf = false; Parent = -1; SuffixLink = -1; WordID = -1; EndWordLink= -1; } // Enlaces a los vértices secundarios en el trie: // Clave: Un solo caracter // Valor: El ID del vértice public Hashtable Children; // Indica que una palabra del diccionario termina en este vértice public bool Leaf; // Enlace al vértice padre public int Parent; // Char que nos mueve desde el vértice padre al vértice actual public char ParentChar; // Enlace de sufijo del vértice actual (el equivalente de P [i] del algoritmo KMP) public int SuffixLink; // Enlace al vértice de hoja de la palabra de longitud máxima que podemos hacer con el prefijo actual public int EndWordLink; // Si el vértice es la hoja, guardamos el ID de la palabra public int WordID; } Υπάρχουν διάφοροι τρόποι για την εφαρμογή δευτερευόντων συνδέσμων. Ο αλγόριθμος θα έχει μια πολυπλοκότητα O (N + L + Z) στην περίπτωση ενός πίνακα, αλλά αυτό θα έχει μια πρόσθετη απαίτηση μνήμης του O (L * q) , όπου q είναι το μήκος του αλφαβήτου, καθώς αυτός είναι ο μέγιστος αριθμός παιδιών που μπορεί να έχει ένας κόμβος.
Εάν χρησιμοποιούμε κάποια δομή με O (ημερολόγιο (q)) πρόσβαση στα στοιχεία του, έχουμε μια πρόσθετη απαίτηση μνήμης Ο (Λ) , αλλά η πολυπλοκότητα του πλήρους αλγορίθμου θα είναι O ((N + L) * log (q) + Z) .
Στην περίπτωση ενός πίνακα κατακερματισμού, έχουμε Ο (Λ) πρόσθετη μνήμη και η πολυπλοκότητα ολόκληρου του αλγορίθμου θα είναι O (N + L + Z) .
Αυτό το σεμινάριο χρησιμοποιεί έναν πίνακα κατακερματισμού επειδή θα λειτουργεί επίσης με διαφορετικά σύνολα χαρακτήρων, για παράδειγμα Κινέζους χαρακτήρες.
Έχουμε ήδη μια δομή για μια κορυφή. Στη συνέχεια, θα ορίσουμε μια λίστα κορυφών και θα ξεκινήσουμε τον ριζικό κόμβο του trie.
public class Aho { List Trie; List WordsLength; int size = 0; int root = 0; public Aho() { Trie = new List(); WordsLength = new List(); Init(); } private void Init() { Trie.Add(new Vertex()) size++; } } Στη συνέχεια προσθέτουμε όλα τα μοτίβα στο trie. Για αυτό, χρειαζόμαστε μια μέθοδο για να προσθέσουμε λέξεις στο trie:
public void AddString(String s, int wordID) { int curVertex = root; for (int i = 0; i Σε αυτό το σημείο, όλες οι λέξεις μοτίβου βρίσκονται στη δομή των δεδομένων. Αυτό απαιτεί πρόσθετη μνήμη Ο (Λ) .
Στη συνέχεια, πρέπει να υπολογίσουμε όλους τους συνδέσμους επιθημάτων και συνδέσμους εισαγωγής λεξικού.
Για να το καταστήσω σαφές και απλό στην κατανόηση, θα περάσω από το trie μας από τη ρίζα στα φύλλα και θα κάνω υπολογισμούς παρόμοιους με αυτό που κάναμε για τον αλγόριθμο KMP, αλλά σε αντίθεση με τον αλγόριθμο KMP, όπου βρίσκουμε το μέγιστο μήκος προθέματος που ήταν επίσης το επίθημα του ίδιου υποστρώματος, τώρα πρόκειται να βρούμε το επίθημα μέγιστου μήκους του τρέχοντος υποστρώματος που είναι επίσης το πρόθεμα κάποιου μοτίβου στο trie. Η τιμή αυτής της συνάρτησης δεν θα είναι το μήκος του επιθέματος που βρέθηκε. θα είναι ο σύνδεσμος προς τον τελευταίο χαρακτήρα του μέγιστου επιθήματος του τρέχοντος υποστρώματος. Αυτό εννοώ με το επίθημα συνδέσμου μιας κορυφής.
Θα επεξεργαστώ κορυφές κατά επίπεδα. Για αυτό, θα χρησιμοποιήσω έναν αλγόριθμο αναζήτηση κατά πλάτος (BFS) :
Και παρακάτω είναι η εφαρμογή αυτού του crossover:
public void PrepareAho() { Queue vertexQueue = new Queue(); vertexQueue.Enqueue(root); while (vertexQueue.Count > 0) { int curVertex = vertexQueue.Dequeue(); CalcSuffLink(curVertex); foreach (char key in Trie[curVertex].Children.Keys) { vertexQueue.Enqueue((int)Trie[curVertex].Children[key]); } } } Και παρακάτω είναι η μέθοδος CalcSuffLink για τον υπολογισμό της δέσμευσης επιθήματος για κάθε κορυφή (δηλαδή, η τιμή συνάρτησης προθέματος για κάθε υπόστρωμα στο trie):
public void CalcSuffLink(int vertex) { // Processing root (empty string) if (vertex == root) { Trie[vertex].SuffixLink = root; Trie[vertex].EndWordLink = root; return; } // Procesamiento de hijos de la raíz (subcadenas de un caracter) if (Trie[vertex].Parent == root) { Trie[vertex].SuffixLink = root; if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; return; } // Los casos anteriores son casos degenerados en cuanto al cálculo de la función del prefijo; // el valor siempre es 0 y los enlaces al vértice raíz. // Para calcular el sufijo link para el vértice actual, necesitamos el sufijo // enlace para el padre del vértice y el personaje que nos movió a la // vértice actual. int curBetterVertex = Trie[Trie[vertex].Parent].SuffixLink; char chVertex = Trie[vertex].ParentChar; // Desde este vértice y su subcadena comenzaremos a buscar el máximo // prefijo para el vértice actual y su subcadena. while (true) { // Si hay una ventaja con el carácter necesario, actualizamos nuestro enlace de sufijo // y abandonar el ciclo if (Trie[curBetterVertex].Children.ContainsKey(chVertex)) { Trie[vertex].SuffixLink = (int)Trie[curBetterVertex].Children[chVertex]; break; } // De lo contrario, estamos saltando por enlaces de sufijo hasta que lleguemos a la raíz // (equivalente a k == 0 en el cálculo de la función de prefijo) o encontramos un // mejor prefijo para la subserie actual. if (curBetterVertex == root) { Trie[vertex].SuffixLink = root; break; } curBetterVertex = Trie[curBetterVertex].SuffixLink; // Go back by sufflink } // Cuando completamos el cálculo del enlace de sufijo para el actual // vertex, debemos actualizar el enlace al final de la palabra de longitud máxima // que se puede producir a partir de la subcadena actual. if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; } Η πολυπλοκότητα αυτής της μεθόδου είναι ** O (L) **; Ανάλογα με την εφαρμογή της θυγατρικής συλλογής, η πολυπλοκότητα μπορεί να είναι ** O (L * log (q)) **.
Η δοκιμή πολυπλοκότητας είναι παρόμοια με τη δοκιμή της συνάρτησης προθέματος πολυπλοκότητας στον αλγόριθμο KMP.
Ας δούμε την παρακάτω εικόνα. Αυτή είναι μια απεικόνιση του trie για το λεξικό {abba, cab, baba, caab, ac, abac, bac} με όλες τις πληροφορίες σας υπολογισμένες:
Τα περιγράμματα του Trie είναι σκούρο μπλε, οι σύνδεσμοι επιθήματος είναι ανοιχτό μπλε και τα επιθήματα λεξικού είναι πράσινα Οι κόμβοι που αντιστοιχούν στις καταχωρήσεις λεξικού επισημαίνονται με μπλε χρώμα.
Και τώρα χρειαζόμαστε μια ακόμη μέθοδο: επεξεργασία ενός μπλοκ κειμένου που σκοπεύουμε να αναζητήσουμε:
public int ProcessString(String text) { // Estado actual del valor int currentState = root; // Valor de resultado apuntado int result = 0; for (int j = 0; j Και, τώρα είναι έτοιμο για χρήση:
Στην είσοδο, έχουμε μια λίστα με μοτίβα:
List patterns; Και αναζητήστε κείμενο:
string text; Και εδώ πώς να τα κολλήσετε όλα μαζί:
// Inicia la estructura trie. Como parámetro opcional podemos poner el aproximado // tamaño del trie para asignar memoria solo una vez para todos los nodos. Aho ahoAlg = new Aho(); for (int i = 0; i Και αυτό είναι! Τώρα ξέρετε πώς λειτουργεί αυτός ο απλός αλλά ισχυρός αλγόριθμος!
Το Aho-Corasick είναι πραγματικά ευέλικτο. Τα μοτίβα αναζήτησης δεν πρέπει να είναι απλά λέξεις, αλλά μπορούμε να χρησιμοποιήσουμε ολόκληρες προτάσεις ή τυχαίες συμβολοσειρές.
Εκτέλεση
Ο αλγόριθμος δοκιμάστηκε σε Intel Core i7-4702MQ.
Για τις δοκιμές, πήρα δύο λεξικά: τις 1.000 πιο κοινές λέξεις στα Αγγλικά και τις 10.000 πιο κοινές λέξεις στα Αγγλικά.
Για να προσθέσετε όλες αυτές τις λέξεις στο λεξικό και να προετοιμάσετε τη δομή δεδομένων για να συνεργαστείτε με κάθε ένα από τα λεξικά, ο αλγόριθμος απαιτούσε 55 ms και 135 ms, αντίστοιχα.
Ο αλγόριθμος επεξεργάστηκε πραγματικά βιβλία μήκους 3-4 εκατομμυρίων χαρακτήρων εντός 1,0-1,3 δευτερολέπτων, ενώ χρειάστηκε 9,6 δευτερόλεπτα για ένα βιβλίο με περίπου 30 εκατομμύρια χαρακτήρες.
Παράλληλος αλγόριθμος Aho-Corasick
Η παράλληλη μετάβαση με τον αλγόριθμο Aho-Corasick δεν είναι καθόλου πρόβλημα:
δημιουργήστε μια νέα γλώσσα προγραμματισμού
Ένα μεγάλο κείμενο μπορεί να χωριστεί σε πολλά κομμάτια και πολλά νήματα μπορούν να χρησιμοποιηθούν για την επεξεργασία κάθε κομματιού. Κάθε νήμα έχει πρόσβαση στο trie που δημιουργείται με βάση το λεξικό.
Τι γίνεται με τις λέξεις που χωρίζονται στο όριο μεταξύ των θραυσμάτων; Αυτό το πρόβλημα μπορεί να λυθεί εύκολα.
Αφήνω Ν είναι το μήκος του μεγάλου μας κειμένου, μικρό είναι το μέγεθος ενός θραύσματος, και μεγάλο είναι το μήκος του μεγαλύτερου μοτίβου στο λεξικό.
Τώρα μπορούμε να χρησιμοποιήσουμε ένα απλό τέχνασμα. Διαιρούμε τα κομμάτια με επικάλυψη στο τέλος, για παράδειγμα λαμβάνοντας [S * (i - 1), S * i + L - 1], όπου i είναι ο δείκτης του κομματιού. Όταν έχουμε μια αντιστοίχιση μοτίβου, μπορούμε εύκολα να πάρουμε τον αρχικό δείκτη του τρέχοντος αγώνα και απλώς να ελέγξουμε ότι αυτός ο δείκτης βρίσκεται εντός του εύρους των τεμαχίων χωρίς επικαλύψεις, |
Ένας ευέλικτος αλγόριθμος αναζήτησης συμβολοσειρών
Ο αλγόριθμος Aho-Corasick είναι ένας ισχυρός αλγόριθμος συνδυασμού συμβολοσειρών που προσφέρει την καλύτερη πολυπλοκότητα για οποιαδήποτε είσοδο και δεν απαιτεί πολλή επιπλέον μνήμη.
Ο αλγόριθμος χρησιμοποιείται συχνά σε διάφορα συστήματα, όπως ορθογραφικοί έλεγχοι, φίλτρα ανεπιθύμητων μηνυμάτων, μηχανές αναζήτησης, αναζήτηση βιοπληροφορικής / ακολουθίας DNA κ.λπ. Στην πραγματικότητα, μερικά δημοφιλή εργαλεία που μπορείτε να χρησιμοποιείτε καθημερινά χρησιμοποιούν αυτόν τον αλγόριθμο πίσω από τα παρασκήνια.
Η συνάρτηση προθέματος του ίδιου του αλγορίθμου KMP είναι ένα ενδιαφέρον εργαλείο που μειώνει την πολυπλοκότητα της αντιστοίχισης ενός μοτίβου με τον γραμμικό χρόνο. Ο αλγόριθμος Aho-Corasick ακολουθεί μια παρόμοια προσέγγιση και χρησιμοποιεί μια δομή δεδομένων trie για να κάνει το ίδιο για πολλά μοτίβα.
Ελπίζω ότι βρήκατε αυτό το σεμινάριο στον αλγόριθμο Aho-Corasick χρήσιμο.
