Aho-Corasick Algoritması ile Dizi Aramayı Fethedin

Dizeleri manipüle etmek ve onlarda kalıp aramak, veri bilimindeki temel görevlerdir ve herhangi bir programcı için tipik bir görevdir.

Verimli dizi algoritmaları, birçok veri bilimi sürecinde önemli bir rol oynamaktadır. Çoğu zaman, bu tür süreçleri pratik kullanım için yeterince mümkün kılan şeylerdir.

Bu makalede, büyük miktarda metinde kalıp aramak için en güçlü algoritmalardan biri hakkında bilgi edineceksiniz: Aho-Corasick algoritması. Bu algoritma, arama modellerini takip etmek için bir trie veri yapısı ("try" olarak telaffuz edilir) kullanır ve herhangi bir metin bloğunda belirli bir model kümesinin tüm oluşumlarını verimli bir şekilde bulmak için basit bir yöntem kullanır.

Toptal Engineering Blog'daki önceki bir makale, aynı problem için bir dizi arama algoritması gösterdi. Bu makalede benimsenen yaklaşım, gelişmiş hesaplama karmaşıklığı sunar.

Knuth-Morris-Pratt (KMP) Algoritması

Bir metinde birden çok kalıbı nasıl verimli bir şekilde arayabileceğimizi anlamak için, önce daha kolay bir problemin üstesinden gelmeliyiz: Belirli bir metinde tek bir kalıp arama.

N uzunluğunda büyük bir metin bloğumuz ve M uzunluğunda bir modelimiz (metinde aramak istediğimiz) olduğunu varsayalım. Bu kalıbın tek bir oluşumunu veya tüm oluşumlarını aramak istesek de, KMP algoritmasını kullanarak O(N + M) hesaplama karmaşıklığına ulaşabiliriz.

Önek İşlevi

KMP algoritması, aradığımız kalıbın önek işlevini hesaplayarak çalışır. Ön ek işlevi, desenin her öneki için bir geri dönüş konumunu önceden hesaplar.

Arama modelimizi S etiketli bir string olarak tanımlayalım. i >= 1 olduğu her S[0..i] alt dizisi için, bu dizgenin aynı zamanda bu dizgenin son eki olan maksimum önekini bulacağız. Bu ön ekin uzunluğunu P[i] olarak etiketleyeceğiz.

"Abracadabra" modeli için önek işlevi aşağıdaki geri dönüş konumlarını üretecektir:

Önek işlevi, desenin ilginç bir özelliğini tanımlar.

Örnek olarak kalıbın belirli bir önekini alalım: "abracadab." Bu önek için önek işlev değeri ikidir. Bu, bu "abracadab" ön eki için, iki uzunluk önekiyle tam olarak eşleşen iki uzunlukta bir sonek bulunduğunu gösterir (yani, model "ab" ile başlar ve önek "ab" ile biter). bu önek için böyle en uzun eşleşme.

uygulama

Herhangi bir dize için önek işlevini hesaplamak için kullanılabilecek bir C# işlevi:

 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; }

Bu işlevi biraz daha uzun bir "abcdabcabcdabcdab" deseninde çalıştırmak şunu üretir:

Hesaplamalı Karmaşıklık

İki iç içe döngü olmasına rağmen, önek işlevinin karmaşıklığı yalnızca O(M) 'dir, burada M , S kalıbının uzunluğudur.

Bu, döngülerin nasıl çalıştığını gözlemleyerek kolayca açıklanabilir.

i aracılığıyla tüm dış döngü yinelemeleri üç duruma ayrılabilir:

1. k bir artırır. Döngü bir yinelemeyi tamamlar.

2. k sıfır değerini değiştirmez. Döngü bir yinelemeyi tamamlar.

3. k pozitif değerini değiştirmez veya azaltmaz.

İlk iki durum en fazla M kez çalışabilir.

Üçüncü durum için, P(s, i) = k1 ve P(s, i + 1) = k2, k2 <= k1 tanımlayalım. Bu vakaların her biri, ilk vakanın k1 - k2 oluşumlarından önce gelmelidir. Azalma sayısı k1 - k2 + 1 geçmez. Ve toplamda 2 * M'den fazla yinelememiz yok.

İkinci Örneğin Açıklaması

İkinci örnek “abcdabcabcdabcdab” örneğine bakalım. Önek işlevinin bunu adım adım nasıl işlediği aşağıda açıklanmıştır:

1. Boş bir alt dizgi ve bir uzunluktaki “a” alt dizgisi için önek işlevinin değeri sıfıra ayarlanır. ( k = 0 )

2. “ab” alt dizisine bakın. Mevcut k değeri sıfırdır ve “b” karakteri “a” karakterine eşit değildir. Burada, önceki bölümden ikinci vakamız var. k değeri sıfırda kalır ve "ab" alt dizisi için önek işlevinin değeri de sıfırdır.

3. "abc" ve "abcd" alt dizeleri için de aynı durum geçerlidir. Bu alt dizelerin son eki olan hiçbir önek yoktur. Onlar için değer sıfırda kalır.

4. Şimdi ilginç bir duruma, “abcda” alt dizisine bakalım. Mevcut k değeri hala sıfır, ancak alt dizimizin son karakteri ilk karakteriyle eşleşiyor. Bu, s[k] == s[i] koşulunu tetikler, burada k == 0 ve i == 4 . Dizi sıfır dizinlidir ve k , maksimum uzunluk öneki için sonraki karakterin dizinidir. Bu, aynı zamanda bir sonek olan alt dizimiz için maksimum uzunluk önekini bulduğumuz anlamına gelir. k yeni değerinin bir olduğu ve dolayısıyla P(“abcda”) önek fonksiyonunun değerinin bir olduğu ilk duruma sahibiz.

5. Aynı durum sonraki iki alt dizi için de geçerlidir, P(“abcdab”) = 2 ve P(“abcdabc”) = 3 . Burada, karakter karakter dizileri karşılaştırarak metindeki desenimizi arıyoruz. Diyelim ki, kalıbın ilk yedi karakteri, işlenmiş metnin ardışık yedi karakteriyle eşleşti, ancak sekizinci karakterde eşleşmedi. Bundan sonra ne olmalı? Naive string eşleşmesi durumunda, yedi karakter geri döndürmeli ve desenimizin ilk karakterinden tekrar karşılaştırma işlemine başlamalıyız. Önek fonksiyon değeriyle (burada P(“abcdabc”) = 3 ) üç karakterli son ekimizin zaten metnin üç karakteriyle eşleştiğini biliyoruz. Ve metindeki bir sonraki karakter "d" ise, desenimizin eşleşen alt dizesinin ve metindeki alt dizenin uzunluğu dörde ("abcd") çıkarılır. Aksi takdirde, P(“abc”) = 0 olur ve örüntünün ilk karakterinden karşılaştırma işlemine başlayacağız. Ancak önemli olan metnin işlenmesi sırasında geri dönmememizdir.

6. Bir sonraki alt dize "abcdabca" dır. Önceki alt dizide önek işlevi üçe eşitti. Bu, k = 3 sıfırdan büyük olduğu ve aynı zamanda önekteki bir sonraki karakter ( s[k] = s[3] = "d" ) ile sonekteki bir sonraki karakter arasında bir uyumsuzluğumuz olduğu anlamına gelir ( s[i] = s[7] = "a" ). Bu, s[k] != s[i] koşulunu tetiklediğimiz ve “abcd” ön ekinin dizgemizin son eki olamayacağı anlamına gelir. Mümkünse, k değerini düşürmeli ve karşılaştırma için önceki öneki almalıyız. Yukarıda açıkladığımız gibi, dizi sıfır indekslidir ve k , önekten kontrol ettiğimiz bir sonraki karakterin indeksidir. Halihazırda eşleşen ön ekin son dizini k - 1 . Şu anda eşleşen önek k = result[k - 1] için önek işlevinin değerini alıyoruz. Bizim durumumuzda (üçüncü durumda) maksimum önek uzunluğu sıfıra düşürülecek ve daha sonra bir sonraki satırda bire kadar artırılacaktır, çünkü “a” aynı zamanda alt dizimizin son eki olan maksimum önektir.

7. (Burada daha ilginç bir duruma ulaşana kadar hesaplama işlemimize devam ediyoruz.)

8. Şu alt diziyi işlemeye başlıyoruz: “abcdabcabcdabcd.” k mevcut değeri yedidir. Yukarıdaki “abcdabca”da olduğu gibi, eşleşmeyen bir noktaya ulaştık: “a” karakteri (yedinci karakter) “d” karakterine eşit olmadığı için, “abcdabca” alt dizgisi dizgemizin son eki olamaz. Şimdi “abcdabc” (üç) için önek fonksiyonunun önceden hesaplanmış değerini alıyoruz ve şimdi bir eşleşmemiz var: “abcd” öneki aynı zamanda dizgemizin son ekidir. Alt dizimiz için maksimum öneki ve önek fonksiyonunun değeri dörttür, çünkü k mevcut değeri bu hale geldi.

9. Bu işleme kalıbın sonuna kadar devam ediyoruz.

Kısacası: Her iki döngü de 3 M iterasyondan fazlasını almaz, bu da karmaşıklığın O(M) olduğunu kanıtlar. Bellek kullanımı da O(M)'dir.

KMP Algoritması Uygulaması

 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; }

Yukarıdaki algoritma metin boyunca, karakter karakter yinelenir ve hem desenimiz hem de metindeki bazı ardışık karakter dizileri için maksimum öneki artırmaya çalışır. Başarısızlık durumunda, konumumuzu metinde daha önce geri döndürmeyeceğiz. Modelin bulunan alt dizisinin maksimum önekini biliyoruz; bu önek aynı zamanda bulunan bu alt dizinin son ekidir ve aramaya devam edebiliriz.

Bu işlevin karmaşıklığı, önek işleviyle aynıdır ve O(N + M) toplam hesaplama karmaşıklığını O (M) bellekle yapar.

Diğer bilgiler: .NET çerçevesindeki String.IndexOf() ve String.Contains() yöntemleri, başlık altında aynı karmaşıklığa sahip bir algoritmaya sahiptir.

Aho-Corasick Algoritması

Şimdi aynı şeyi birden fazla desen için yapmak istiyoruz.

L1 , L2 , …, Lm uzunluklarında M desenleri olduğunu varsayalım. N uzunluğunda bir metinde bir sözlükten tüm kalıp eşleşmelerini bulmamız gerekiyor.

Önemsiz bir çözüm, herhangi bir algoritmayı ilk bölümden alıp M kez çalıştırmak olacaktır. O(N + L1 + N + L2 + … + N + Lm) karmaşıklığına sahibiz, yani O(M * N + L) .

Yeterince ciddi herhangi bir test bu algoritmayı öldürür.

Kalıp olarak en yaygın 1.000 İngilizce kelimeyi içeren bir sözlük almak ve onu Tolstoy'un “Savaş ve Barış” kitabının İngilizce versiyonunu aramak için kullanmak oldukça zaman alacaktı. Kitap üç milyondan fazla karakter uzunluğunda.

En yaygın 10.000 İngilizce kelimeyi alırsak, algoritma yaklaşık 10 kat daha yavaş çalışacaktır. Açıkçası bundan daha büyük girdilerde, yürütme süresi de artacaktır.

Aho-Corasick algoritmasının sihrini yaptığı yer burasıdır.

Aho-Corasick algoritmasının karmaşıklığı O(N + L + Z) şeklindedir; burada Z , eşleşme sayısıdır. Bu algoritma, 1975 yılında Alfred V. Aho ve Margaret J. Corasick tarafından icat edildi.

uygulama

Burada bir denemeye ihtiyacımız var ve algoritmamıza yukarıda açıklanan önek işlevlerine benzer bir fikir ekliyoruz. Tüm sözlük için önek fonksiyon değerlerini hesaplayacağız.

Trie'deki her bir köşe noktası aşağıdaki bilgileri depolayacaktır:

 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; }

Alt bağlantıları uygulamanın birden çok yolu vardır. Algoritma, bir dizi durumunda O(N + L + Z) karmaşıklığına sahip olacaktır, ancak bu, O(L * q) ek bir bellek gereksinimine sahip olacaktır; burada q , alfabenin uzunluğudur, çünkü bu bir düğümün sahip olabileceği maksimum çocuk sayısı.

Öğelerine O(log(q)) erişimi olan bir yapı kullanırsak, ek bir O(L) bellek gereksinimimiz olur, ancak tüm algoritmanın karmaşıklığı O((N + L) * log(q) olacaktır. + Z) .

Bir karma tablo durumunda, O(L) ek belleğimiz vardır ve tüm algoritmanın karmaşıklığı O(N + L + Z) olacaktır.

Bu öğretici, farklı karakter kümeleriyle, örneğin Çince karakterlerle de çalışacağı için bir karma tablo kullanır.

Zaten bir köşe için bir yapımız var. Ardından, bir köşe listesi tanımlayacağız ve trie'nin kök düğümünü başlatacağız.

 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++; } }

Daha sonra tüm kalıpları trie'ye ekliyoruz. Bunun için, trie'ye bir kelime eklemek için bir metoda ihtiyacımız var:

 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); }

Bu noktada kalıp kelimelerinin tamamı veri yapısındadır. Bu, ek bir O(L) belleği gerektirir.

Ardından, tüm son ek bağlantılarını ve sözlük giriş bağlantılarını hesaplamamız gerekiyor.

Açık ve anlaşılır hale getirmek için, denememizi kökten yapraklara geçeceğim ve KMP algoritması için yaptığımız gibi benzer hesaplamalar yapacağım, ancak maksimum uzunluğu bulduğumuz KMP algoritmasının aksine. Aynı alt dizginin son eki olan önek, şimdi mevcut alt dizginin maksimum uzunluklu son ekini bulacağız ve bu aynı zamanda trie'deki bazı kalıpların önekidir. Bu işlevin değeri, bulunan son ekin uzunluğu olmayacaktır; geçerli alt dizinin maksimum son ekinin son karakterine bağlantı olacaktır. Bir tepenin son ek bağlantısı ile kastettiğim budur.

Köşeleri seviyelere göre işleyeceğim. Bunun için bir genişlik öncelikli arama (BFS) algoritması kullanacağım:

Ve aşağıda bu geçişin uygulanması:

 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]); } } }

Ve aşağıda, her köşe için son ek bağlantısını hesaplamak için CalcSuffLink yöntemi (yani, trie'deki her alt dize için önek işlev değeri):

 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; }

Bu yöntemin karmaşıklığı O(L) ; alt koleksiyonun uygulanmasına bağlı olarak, karmaşıklık O(L * log(q)) olabilir.

Karmaşıklık kanıtı, KMP algoritmasındaki karmaşıklık kanıtı öneki işlevine benzer.

Aşağıdaki resme bakalım. Bu, { abba, cab, baba, caab, ac, abac, bac } tüm hesaplanmış bilgileriyle bir görselleştirmesidir:

Üçgen kenarları koyu mavi, son ek bağlantıları açık mavi ve sözlük son ek bağlantıları yeşildir. Sözlük girişlerine karşılık gelen düğümler mavi renkle vurgulanır.

Ve şimdi yalnızca bir yönteme daha ihtiyacımız var - aramayı düşündüğümüz bir metin bloğunu işlemek:

 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; }

Ve şimdi bu kullanıma hazır:

Girişte, bir kalıp listemiz var:

 List<string> patterns;

Ve arama metni:

 string text;

Ve işte nasıl yapıştırılacağı:

 // 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);

Ve bu kadar! Artık bu basit ama güçlü algoritmanın nasıl çalıştığını biliyorsunuz!

Aho-Corasick gerçekten esnektir. Arama kalıpları yalnızca kelimeler olmak zorunda değildir, ancak tüm cümleleri veya rastgele karakter zincirlerini kullanabiliriz.

Verim

Algoritma bir Intel Core i7-4702MQ üzerinde test edildi.

Testler için iki sözlük aldım: En yaygın 1.000 İngilizce kelime ve en yaygın 10.000 İngilizce kelime.

Tüm bu kelimeleri sözlüğe eklemek ve sözlüklerin her biri ile çalışacak veri yapısını hazırlamak için algoritma sırasıyla 55ms ve 135ms gerekliydi.

Algoritma, 3-4 milyon karakter uzunluğundaki gerçek kitapları 1.0-1.3 saniyede işlerken, yaklaşık 30 milyon karakterlik bir kitap için 9.6 saniye sürdü.

Aho-Corasick Algoritmasını Paralelleştirme

Aho-Corasick algoritmasına paralel gitmek hiç sorun değil:

Büyük bir metin birden çok parçaya bölünebilir ve her parçayı işlemek için birden çok iş parçacığı kullanılabilir. Her iş parçacığının, sözlüğe dayalı olarak oluşturulan denemeye erişimi vardır.

Parçalar arasındaki sınırda bölünen kelimelere ne dersiniz? Bu sorun kolayca çözülebilir.

N büyük metnimizin uzunluğu, S bir yığının boyutu ve L sözlükteki en büyük kalıbın uzunluğu olsun.

Şimdi basit bir numara kullanabiliriz. Parçaları, sonunda bir miktar örtüşme ile böleriz, örneğin [S * (i - 1), S * i + L - 1] alarak, burada i , yığının indeksidir. Bir model eşleşmesi aldığımızda, mevcut eşleşmenin başlangıç ​​indeksini kolayca alabilir ve bu indeksin örtüşme olmadan yığın aralığında olduğunu kontrol edebiliriz, [S * (i - 1), S * i - 1] .

Çok Yönlü Bir Dizi Arama Algoritması

Aho-Corasick algoritması, herhangi bir girdi için en iyi karmaşıklığı sunan ve fazla ek bellek gerektirmeyen güçlü bir dizi eşleştirme algoritmasıdır.

Algoritma genellikle yazım denetleyicileri, spam filtreleri, arama motorları, biyoinformatik/DNA dizilimi arama vb. gibi çeşitli sistemlerde kullanılır. Aslında, her gün kullanabileceğiniz bazı popüler araçlar bu algoritmayı perde arkasında kullanıyor.

KMP algoritmasının önek işlevinin kendisi, tek desen eşleştirmenin karmaşıklığını doğrusal zamana indiren ilginç bir araçtır. Aho-Corasick algoritması da benzer bir yaklaşım izler ve aynı şeyi birden çok model için yapmak üzere bir trie veri yapısı kullanır.

Umarım Aho-Corasick algoritmasıyla ilgili bu öğreticiyi faydalı bulmuşsunuzdur.