Taklukkan Pencarian String dengan Algoritma Aho-Corasick

Memanipulasi string dan mencari pola di dalamnya adalah tugas mendasar dalam ilmu data, dan tugas khas untuk programmer mana pun.

Algoritma string yang efisien memainkan peran penting dalam banyak proses ilmu data. Seringkali merekalah yang membuat proses tersebut cukup layak untuk penggunaan praktis.

Dalam artikel ini, Anda akan belajar tentang salah satu algoritme paling kuat untuk mencari pola dalam sejumlah besar teks: Algoritme Aho-Corasick. Algoritme ini menggunakan struktur data trie (diucapkan "coba") untuk melacak pola pencarian dan menggunakan metode sederhana untuk secara efisien menemukan semua kemunculan serangkaian pola tertentu dalam gumpalan teks apa pun.

Artikel sebelumnya di Blog Toptal Engineering menunjukkan algoritma pencarian string untuk masalah yang sama. Pendekatan yang diambil dalam artikel ini menawarkan peningkatan kompleksitas komputasi.

Algoritma Knuth-Morris-Pratt (KMP)

Untuk memahami bagaimana kita dapat mencari beberapa pola dalam teks secara efisien, pertama-tama kita perlu mengatasi masalah yang lebih mudah: Mencari satu pola dalam teks tertentu.

Misalkan kita memiliki gumpalan besar teks dengan panjang N dan pola (yang ingin kita cari dalam teks) dengan panjang M . Apakah kita ingin mencari kemunculan tunggal dari pola ini, atau semua kemunculan, kita dapat mencapai kompleksitas komputasi O(N + M) menggunakan algoritma KMP.

Fungsi Awalan

Algoritma KMP bekerja dengan menghitung fungsi awalan dari pola yang kita cari. Fungsi awalan menghitung sebelumnya posisi mundur untuk setiap awalan pola.

Mari kita definisikan pola pencarian kita sebagai string, berlabel S . Untuk setiap substring S[0..i] , di mana i >= 1 , kita akan menemukan awalan maksimum dari string ini yang juga merupakan akhiran dari string ini. Kami akan memberi label panjang awalan ini P[i] .

Untuk pola “abracadabra”, fungsi awalan akan menghasilkan posisi mundur berikut:

Fungsi awalan mengidentifikasi karakteristik pola yang menarik.

Mari kita ambil awalan tertentu dari pola sebagai contoh: “abracadab.” Nilai fungsi awalan untuk awalan ini adalah dua. Hal ini menunjukkan bahwa untuk awalan “abracadab” ini, terdapat akhiran dengan panjang dua yang sama persis dengan awalan dengan panjang dua (yaitu, polanya dimulai dengan “ab” dan awalan diakhiri dengan “ab.”) Selanjutnya, ini adalah kecocokan terpanjang untuk awalan ini.

Penerapan

Berikut adalah fungsi C# yang dapat digunakan untuk menghitung fungsi awalan untuk string apa pun:

 public int[] CalcPrefixFunction(String s) { int[] result = new int[s.Length]; // array with prefix function values result[0] = 0; // the prefix function is always zero for the first symbol (its degenerate case) int k = 0; // current prefix function value for (int i = 1; i < s.Length; i++) { // We're jumping by prefix function values to try smaller prefixes // Jumping stops when we find a match, or reach zero // Case 2 if we stop at a zero-length prefix // Case 3 if we stop at a match while (k > 0 && s[i] != s[k]) k = result[k - 1]; if (s[k] == s[i]) k++; // we've found the longest prefix - case 1 result[i] = k; // store this result in the array } return result; }

Menjalankan fungsi ini pada pola yang sedikit lebih panjang "abcdabcabcdabcdab" menghasilkan ini:

Kompleksitas Komputasi

Terlepas dari kenyataan bahwa ada dua loop bersarang, kompleksitas fungsi awalan hanya O(M) , di mana M adalah panjang pola S .

Ini dapat dijelaskan dengan mudah dengan mengamati cara kerja loop.

Semua iterasi loop luar melalui i dapat dibagi menjadi tiga kasus:

1. Meningkatkan k satu. Loop menyelesaikan satu iterasi.

2. Tidak mengubah nilai nol k . Loop menyelesaikan satu iterasi.

3. Tidak mengubah atau mengurangi nilai positif k .

Dua kasus pertama dapat dijalankan paling banyak M kali.

Untuk kasus ketiga, mari kita definisikan P(s, i) = k1 dan P(s, i + 1) = k2, k2 <= k1 . Masing-masing kasus ini harus didahului oleh k1 - k2 kemunculan kasus pertama. Hitungan penurunan tidak melebihi k1 - k2 + 1 . Dan secara total kami memiliki tidak lebih dari 2 * M iterasi.

Penjelasan Contoh Kedua

Mari kita lihat contoh pola kedua “abcdabcabcdabcdab”. Berikut adalah bagaimana fungsi awalan memprosesnya, langkah demi langkah:

1. Untuk substring kosong dan substring "a" dengan panjang satu, nilai fungsi awalan diatur ke nol. ( k = 0 )

2. Lihatlah substring "ab." Nilai k saat ini adalah nol dan karakter "b" tidak sama dengan karakter "a." Di sini, kita memiliki kasus kedua dari bagian sebelumnya. Nilai k tetap nol dan nilai fungsi awalan untuk substring “ab” juga nol.

3. Ini kasus yang sama untuk substring "abc" dan "abcd." Tidak ada prefiks yang juga merupakan sufiks dari substring ini. Nilai untuk mereka tetap di nol.

4. Sekarang mari kita lihat kasus yang menarik, substring “abcda.” Nilai k saat ini masih nol, tetapi karakter terakhir dari substring kita cocok dengan karakter pertamanya. Ini memicu kondisi s[k] == s[i] , di mana k == 0 dan i == 4 . Array diindeks nol, dan k adalah indeks karakter berikutnya untuk awalan panjang maksimum. Ini berarti bahwa kami telah menemukan awalan panjang maksimum untuk substring kami yang juga merupakan akhiran. Kami memiliki kasus pertama, di mana nilai baru k adalah satu, dan dengan demikian nilai fungsi awalan P("abcda") adalah satu.

5. Kasus yang sama juga terjadi untuk dua substring berikutnya, P(“abcdab”) = 2 dan P(“abcdabc”) = 3 . Di sini, kami mencari pola kami dalam teks, membandingkan string karakter demi karakter. Katakanlah tujuh karakter pertama dari pola tersebut cocok dengan sekitar tujuh karakter berturut-turut dari teks yang diproses, tetapi pada karakter kedelapan tidak cocok. Apa yang harus terjadi selanjutnya? Dalam kasus pencocokan string naif, kita harus mengembalikan tujuh karakter dan memulai proses perbandingan lagi dari karakter pertama pola kita. Dengan nilai fungsi awalan (di sini P(“abcdabc”) = 3 ) kita tahu bahwa akhiran tiga karakter kita sudah cocok dengan tiga karakter teks. Dan jika karakter berikutnya dalam teks adalah “d”, panjang substring yang cocok dari pola dan substring kita dalam teks ditambah menjadi empat (“abcd”). Jika tidak, P(“abc”) = 0 dan kita akan memulai proses perbandingan dari karakter pertama pola. Tapi yang penting kita tidak kembali saat memproses teks.

6. Substring berikutnya adalah "abcdabca." Pada substring sebelumnya, fungsi awalan sama dengan tiga. Ini berarti bahwa k = 3 lebih besar dari nol, dan pada saat yang sama kita memiliki ketidakcocokan antara karakter berikutnya di awalan ( s[k] = s[3] = "d" ) dan karakter berikutnya di akhiran ( s[i] = s[7] = "a" ). Ini berarti bahwa kita memicu kondisi s[k] != s[i] , dan bahwa awalan “abcd” tidak dapat menjadi akhiran dari string kita. Kita harus menurunkan nilai k dan mengambil awalan sebelumnya untuk perbandingan, jika memungkinkan. Seperti yang kami jelaskan di atas, array diindeks nol, dan k adalah indeks karakter berikutnya yang kami periksa dari awalan. Indeks terakhir dari awalan yang saat ini cocok adalah k - 1 . Kami mengambil nilai fungsi awalan untuk awalan yang saat ini cocok k = result[k - 1] . Dalam kasus kami (kasus ketiga) panjang awalan maksimum akan dikurangi menjadi nol dan kemudian pada baris berikutnya akan ditingkatkan menjadi satu, karena "a" adalah awalan maksimum yang juga merupakan akhiran dari substring kami.

7. (Di sini kami melanjutkan proses perhitungan kami sampai kami mencapai kasus yang lebih menarik.)

8. Kami mulai memproses substring berikut: "abcdabcabcdabcd." Nilai k saat ini adalah tujuh. Seperti "abcdabca" di atas, kami menemukan ketidakcocokan: Karena karakter "a" (karakter ketujuh) tidak sama dengan karakter "d", substring "abcdabca" tidak dapat menjadi akhiran dari string kami. Sekarang kita mendapatkan nilai yang sudah dihitung dari fungsi awalan untuk "abcdabc" (tiga) dan sekarang kita memiliki kecocokan: Awalan "abcd" juga merupakan akhiran dari string kita. Awalan maksimumnya dan nilai fungsi awalan untuk substring kita adalah empat, karena itulah yang menjadi nilai k saat ini.

9. Kami melanjutkan proses ini sampai akhir pola.

Singkatnya: Kedua siklus membutuhkan tidak lebih dari 3 M iterasi, yang membuktikan kompleksitasnya menjadi O(M). Penggunaan memori juga O(M).

Implementasi Algoritma KMP

 public int KMP(String text, String s) { int[] p = CalcPrefixFunction(s); // Calculate prefix function for a pattern string // The idea is the same as in the prefix function described above, but now // we're comparing prefixes of text and pattern. // The value of maximum-length prefix of the pattern string that was found // in the text: int maxPrefixLength = 0; for (int i = 0; i < text.Length; i++) { // As in the prefix function, we're jumping by prefixes until k is // greater than 0 or we find a prefix that has matches in the text. while (maxPrefixLength > 0 && text[i] != s[maxPrefixLength]) maxPrefixLength = p[maxPrefixLength - 1]; // If a match happened, increase the length of the maximum-length // prefix. if (s[maxPrefixLength] == text[i]) maxPrefixLength++; // If the prefix length is the same length as the pattern string, it // means that we have found a matching substring in the text. if (maxPrefixLength == s.Length) { // We can return this value or perform this operation. int idx = i - s.Length + 1; // Get the previous maximum-length prefix and continue search. maxPrefixLength = p[maxPrefixLength - 1]; } } return -1; }

Algoritme di atas mengulangi teks, karakter demi karakter, dan mencoba meningkatkan awalan maksimum untuk pola kita dan beberapa urutan karakter berurutan dalam teks. Jika gagal, kami tidak akan mengembalikan posisi kami ke posisi sebelumnya dalam teks. Kita tahu awalan maksimum dari substring pola yang ditemukan; awalan ini juga merupakan akhiran dari substring yang ditemukan ini dan kita dapat melanjutkan pencarian.

Kompleksitas fungsi ini sama dengan fungsi awalan, membuat kompleksitas komputasi keseluruhan O(N + M) dengan memori O(M) .

Trivia: Metode String.IndexOf() dan String.Contains() dalam kerangka .NET memiliki algoritme dengan kompleksitas yang sama.

Algoritma Aho-Corasick

Sekarang kita ingin melakukan hal yang sama untuk beberapa pola.

Misalkan ada M pola panjang L1 , L2 , …, Lm . Kita perlu menemukan semua kecocokan pola dari kamus dalam teks dengan panjang N .

Solusi sepele akan mengambil algoritma apa pun dari bagian pertama dan menjalankannya M kali. Kami memiliki kompleksitas O(N + L1 + N + L2 + … + N + Lm) , yaitu O(M * N + L) .

Setiap tes yang cukup serius membunuh algoritma ini.

Mengambil kamus dengan 1.000 kata bahasa Inggris yang paling umum sebagai pola dan menggunakannya untuk mencari "War and Peace" versi bahasa Inggris dari Tolstoy akan memakan waktu cukup lama. Buku ini memiliki panjang lebih dari tiga juta karakter.

Jika kita mengambil 10.000 kata bahasa Inggris yang paling umum, algoritme akan bekerja sekitar 10 kali lebih lambat. Jelas pada input yang lebih besar dari ini, waktu eksekusi juga akan bertambah.

Di sinilah algoritma Aho-Corasick melakukan keajaibannya.

Kompleksitas algoritma Aho-Corasick adalah O(N + L + Z) , di mana Z adalah jumlah kecocokan. Algoritma ini ditemukan oleh Alfred V. Aho dan Margaret J. Corasick pada tahun 1975.

Penerapan

Di sini, kita membutuhkan sebuah trie, dan kita menambahkan ide yang serupa ke algoritma kita ke fungsi awalan yang dijelaskan di atas. Kami akan menghitung nilai fungsi awalan untuk seluruh kamus.

Setiap simpul dalam trie akan menyimpan informasi berikut:

 public class Vertex { public Vertex() { Children = new Hashtable(); Leaf = false; Parent = -1; SuffixLink = -1; WordID = -1; EndWordLink= -1; } // Links to the child vertexes in the trie: // Key: A single character // Value: The ID of vertex public Hashtable Children; // Flag that some word from the dictionary ends in this vertex public bool Leaf; // Link to the parent vertex public int Parent; // Char which moves us from the parent vertex to the current vertex public char ParentChar; // Suffix link from current vertex (the equivalent of P[i] from the KMP algorithm) public int SuffixLink; // Link to the leaf vertex of the maximum-length word we can make from the current prefix public int EndWordLink; // If the vertex is the leaf, we store the ID of the word public int WordID; }

Ada beberapa cara untuk menerapkan tautan anak. Algoritme akan memiliki kompleksitas O(N + L + Z) dalam kasus array, tetapi ini akan memiliki persyaratan memori tambahan O(L * q) , di mana q adalah panjang alfabet, karena itu jumlah maksimum anak yang dapat dimiliki sebuah simpul.

Jika kita menggunakan beberapa struktur dengan akses O(log(q)) ke elemen-elemennya, kita memiliki persyaratan memori tambahan O(L) , tetapi kompleksitas keseluruhan algoritma adalah O((N + L) * log(q) +Z) .

Dalam kasus tabel hash, kami memiliki memori tambahan O(L) , dan kompleksitas keseluruhan algoritma adalah O(N + L + Z) .

Tutorial ini menggunakan tabel hash karena juga akan bekerja dengan set karakter yang berbeda, misalnya karakter Cina.

Kita sudah memiliki struktur untuk sebuah simpul. Selanjutnya, kita akan mendefinisikan daftar simpul dan menginisialisasi simpul akar dari trie.

 public class Aho { List<Vertex> Trie; List<int> WordsLength; int size = 0; int root = 0; public Aho() { Trie = new List<Vertex>(); WordsLength = new List<int>(); Init(); } private void Init() { Trie.Add(new Vertex()) size++; } }

Kemudian kami menambahkan semua pola ke trie. Untuk ini, kita memerlukan metode untuk menambahkan kata ke trie:

 public void AddString(String s, int wordID) { int curVertex = root; for (int i = 0; i < s.Length; ++i) // Iterating over the string's characters { char c = s[i]; // Checking if a vertex with this edge exists in the trie: if (!Trie[curVertex].Children.ContainsKey(c)) { Trie.Add(new Vertex()); Trie[size].SuffixLink = -1; // If not - add vertex Trie[size].Parent = curVertex; Trie[size].ParentChar = c; Trie[curVertex].Children[c] = size; size++; } curVertex = (int)Trie[curVertex].Children[c]; // Move to the new vertex in the trie } // Mark the end of the word and store its ID Trie[curVertex].Leaf = true; Trie[curVertex].WordID = wordID; WordsLength.Add(s.Length); }

Pada titik ini, semua kata pola berada dalam struktur data. Ini membutuhkan memori tambahan O(L) .

Selanjutnya kita perlu menghitung semua tautan sufiks dan tautan entri kamus.

Agar jelas dan mudah dipahami, saya akan menelusuri trie kita dari akar ke daun dan membuat perhitungan serupa seperti yang kita buat untuk algoritme KMP, tetapi berbeda dengan algoritme KMP, di mana kita menemukan panjang maksimum awalan yang juga merupakan akhiran dari substring yang sama, sekarang kita akan menemukan akhiran dengan panjang maksimum dari substring saat ini yang juga merupakan awalan dari beberapa pola di trie. Nilai dari fungsi ini bukanlah panjang dari sufiks yang ditemukan; itu akan menjadi tautan ke karakter terakhir dari sufiks maksimum dari substring saat ini. Inilah yang saya maksud dengan suffix link dari sebuah vertex.

Saya akan memproses simpul berdasarkan level. Untuk itu, saya akan menggunakan algoritma breadth-first search (BFS):

Dan di bawah ini adalah implementasi dari traversal ini:

 public void PrepareAho() { Queue<int> vertexQueue = new Queue<int>(); 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]); } } }

Dan di bawah ini adalah metode CalcSuffLink untuk menghitung suffix link untuk setiap vertex (yaitu nilai fungsi prefix untuk setiap substring di trie):

 public void CalcSuffLink(int vertex) { // Processing root (empty string) if (vertex == root) { Trie[vertex].SuffixLink = root; Trie[vertex].EndWordLink = root; return; } // Processing children of the root (one character substrings) 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; } // Cases above are degenerate cases as for prefix function calculation; the // value is always 0 and links to the root vertex. // To calculate the suffix link for the current vertex, we need the suffix // link for the parent of the vertex and the character that moved us to the // current vertex. int curBetterVertex = Trie[Trie[vertex].Parent].SuffixLink; char chVertex = Trie[vertex].ParentChar; // From this vertex and its substring we will start to look for the maximum // prefix for the current vertex and its substring. while (true) { // If there is an edge with the needed char, we update our suffix link // and leave the cycle if (Trie[curBetterVertex].Children.ContainsKey(chVertex)) { Trie[vertex].SuffixLink = (int)Trie[curBetterVertex].Children[chVertex]; break; } // Otherwise, we are jumping by suffix links until we reach the root // (equivalent of k == 0 in prefix function calculation) or we find a // better prefix for the current substring. if (curBetterVertex == root) { Trie[vertex].SuffixLink = root; break; } curBetterVertex = Trie[curBetterVertex].SuffixLink; // Go back by sufflink } // When we complete the calculation of the suffix link for the current // vertex, we should update the link to the end of the maximum length word // that can be produced from the current substring. if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; }

Kompleksitas metode ini adalah O(L) ; tergantung pada implementasi koleksi anak, kompleksitasnya mungkin O(L * log(q)) .

Pembuktian kompleksitas mirip dengan fungsi prefiks pembuktian kompleksitas pada algoritma KMP.

Mari kita lihat gambar berikut. Ini adalah visualisasi dari trie untuk kamus { abba, cab, baba, caab, ac, abac, bac } dengan semua info terhitungnya:

Tepi trie berwarna biru tua, tautan sufiks berwarna biru muda, dan tautan sufiks kamus berwarna hijau. Node yang sesuai dengan entri kamus disorot dengan warna biru.

Dan sekarang kita hanya membutuhkan satu metode lagi—memproses blok teks yang ingin kita cari:

 public int ProcessString(String text) { // Current state value int currentState = root; // Targeted result value int result = 0; for (int j = 0; j < text.Length; j++) { // Calculating new state in the trie while (true) { // If we have the edge, then use it if (Trie[currentState].Children.ContainsKey(text[j])) { currentState = (int)Trie[currentState].Children[text[j]]; break; } // Otherwise, jump by suffix links and try to find the edge with // this char // If there aren't any possible edges we will eventually ascend to // the root, and at this point we stop checking. if (currentState == root) break; currentState = Trie[currentState].SuffixLink; } int checkState = currentState; // Trying to find all possible words from this prefix while (true) { // Checking all words that we can get from the current prefix checkState = Trie[checkState].EndWordLink; // If we are in the root vertex, there are no more matches if (checkState == root) break; // If the algorithm arrived at this row, it means we have found a // pattern match. And we can make additional calculations like find // the index of the found match in the text. Or check that the found // pattern is a separate word and not just, eg, a substring. result++; int indexOfMatch = j + 1 - WordsLength[Trie[checkState].WordID]; // Trying to find all matched patterns of smaller length checkState = Trie[checkState].SuffixLink; } } return result; }

Dan, sekarang ini siap digunakan:

Pada input, kami memiliki daftar pola:

 List<string> patterns;

Dan teks pencarian:

 string text;

Dan inilah cara merekatkannya:

 // Init the trie structure. As an optional parameter we can put the approximate // size of the trie to allocate memory just once for all nodes. Aho ahoAlg = new Aho(); for (int i = 0; i < patterns.Count; i++) { ahoAlg.AddString(patterns[i], i); // Add all patterns to the structure } // Prepare algorithm for work (calculates all links in the structure): ahoAlg.PrepareAho(); // Process the text. Output might be different; in my case, it's a count of // matches. We could instead return a structure with more detailed information. int countOfMatches = ahoAlg.ProcessString(text);

Dan itu saja! Anda sekarang tahu bagaimana algoritma sederhana namun kuat ini bekerja!

Aho-Corasick sangat fleksibel. Pola pencarian tidak harus hanya kata-kata, tetapi kita dapat menggunakan seluruh kalimat atau rantai karakter acak.

Pertunjukan

Algoritme diuji pada Intel Core i7-4702MQ.

Untuk tes, saya mengambil dua kamus: 1.000 kata bahasa Inggris yang paling umum, dan 10.000 kata bahasa Inggris yang paling umum.

Untuk menambahkan semua kata ini ke kamus dan menyiapkan struktur data untuk bekerja dengan masing-masing kamus, algoritme masing-masing membutuhkan 55 md dan 135 md.

Algoritme memproses buku asli dengan panjang 3-4 juta karakter dalam waktu 1,0-1,3 detik, sedangkan buku dengan sekitar 30 juta karakter membutuhkan waktu 9,6 detik.

Memparalelkan Algoritma Aho-Corasick

Menjadi paralel dengan algoritma Aho-Corasick bukanlah masalah sama sekali:

Sebuah teks besar dapat dibagi menjadi beberapa potongan dan beberapa utas dapat digunakan untuk memproses setiap potongan. Setiap utas memiliki akses ke trie yang dihasilkan berdasarkan kamus.

Bagaimana dengan kata-kata yang dipecah di batas antara potongan? Masalah ini dapat diselesaikan dengan mudah.

Biarkan N menjadi panjang teks besar kita, S menjadi ukuran potongan, dan L menjadi panjang pola terbesar dalam kamus.

Sekarang kita bisa menggunakan trik sederhana. Kami membagi potongan dengan beberapa tumpang tindih di akhir, misalnya mengambil [S * (i - 1), S * i + L - 1] , di mana i adalah indeks dari potongan. Ketika kita mendapatkan kecocokan pola, kita dapat dengan mudah mendapatkan indeks awal dari kecocokan saat ini dan hanya memeriksa apakah indeks ini berada dalam rentang potongan tanpa tumpang tindih, [S * (i - 1), S * i - 1] .

Algoritma Pencarian String Serbaguna

Algoritme Aho-Corasick adalah algoritme pencocokan string yang kuat yang menawarkan kompleksitas terbaik untuk input apa pun dan tidak memerlukan banyak memori tambahan.

Algoritma ini sering digunakan di berbagai sistem, seperti pemeriksa ejaan, filter spam, mesin pencari, pencarian urutan bioinformatika/DNA, dll. Sebenarnya, beberapa alat populer yang mungkin Anda gunakan setiap hari menggunakan algoritma ini di belakang layar.

Fungsi awalan dari algoritma KMP itu sendiri adalah alat yang menarik yang membawa kompleksitas pencocokan pola tunggal ke waktu linier. Algoritma Aho-Corasick mengikuti pendekatan serupa dan menggunakan struktur data trie untuk melakukan hal yang sama untuk beberapa pola.

Saya harap tutorial tentang algoritma Aho-Corasick ini bermanfaat bagi Anda.