Победите поиск строк с помощью алгоритма Ахо-Корасика

Манипулирование строками и поиск закономерностей в них — фундаментальные задачи науки о данных и типичная задача любого программиста.

Эффективные строковые алгоритмы играют важную роль во многих процессах обработки данных. Часто именно они делают такие процессы достаточно осуществимыми для практического использования.

В этой статье вы узнаете об одном из самых мощных алгоритмов поиска закономерностей в большом объеме текста: алгоритме Ахо-Корасика. Этот алгоритм использует структуру данных trie (произносится как «попробуй») для отслеживания шаблонов поиска и использует простой метод для эффективного поиска всех вхождений заданного набора шаблонов в любом фрагменте текста.

В предыдущей статье блога Toptal Engineering был продемонстрирован алгоритм поиска строк для той же задачи. Подход, использованный в этой статье, предлагает улучшенную вычислительную сложность.

Алгоритм Кнута-Морриса-Пратта (КМП)

Чтобы понять, как мы можем эффективно искать несколько шаблонов в тексте, нам нужно сначала решить более простую задачу: поиск одного шаблона в заданном тексте.

Предположим, у нас есть большой блок текста длины N и шаблон (который мы хотим найти в тексте) длины M. Хотим ли мы искать одно вхождение этого шаблона или все вхождения, мы можем достичь вычислительной сложности O (N + M) , используя алгоритм KMP.

Префикс Функция

Алгоритм KMP работает путем вычисления префиксной функции искомого шаблона. Функция префикса предварительно вычисляет запасную позицию для каждого префикса шаблона.

Давайте определим наш шаблон поиска как строку с меткой S Для каждой подстроки S[0..i] , где i >= 1 , мы найдем максимальный префикс этой строки, который также является суффиксом этой строки. Мы обозначим длину этого префикса P[i] .

Для шаблона «абракадабра» функция префикса будет создавать следующие резервные позиции:

Функция префикса идентифицирует интересную характеристику шаблона.

В качестве примера возьмем конкретный префикс шаблона: «абракадаб». Значение функции префикса для этого префикса равно двум. Это указывает на то, что для этого префикса «абракадаб» существует суффикс длины два, точно совпадающий с префиксом длины два (т. е. образец начинается с «аб», а префикс заканчивается на «аб»). самое длинное такое совпадение для этого префикса.

Реализация

Вот функция C#, которую можно использовать для вычисления функции префикса для любой строки:

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

Запуск этой функции по более длинному шаблону «abcdabcabcdabcdab» дает следующее:

Вычислительная сложность

Несмотря на то, что есть два вложенных цикла, сложность префиксной функции как раз O(M) , где M — длина шаблона S.

Это легко объяснить, наблюдая за тем, как работают петли.

Все итерации внешнего цикла через i можно разделить на три случая:

1. Увеличивает k на единицу. Цикл завершает одну итерацию.

2. Не изменяет нулевое значение k . Цикл завершает одну итерацию.

3. Не изменяет или уменьшает положительное значение k .

Первые два случая могут выполняться не более M раз.

Для третьего случая определим P(s, i) = k1 и P(s, i + 1) = k2, k2 <= k1 . Каждому из этих случаев должно предшествовать k1 - k2 вхождений первого случая. Количество убавок не превышает k1 - k2 + 1 . А всего у нас не более 2*M итераций.

Объяснение второго примера

Давайте посмотрим на второй пример шаблона «abcdabcabcdabcdab». Вот как функция префикса обрабатывает его шаг за шагом:

1. Для пустой подстроки и подстроки «a» длины один значение функции префикса устанавливается равным нулю. ( k = 0 )

2. Посмотрите на подстроку «ab». Текущее значение k равно нулю, а символ «b» не равен символу «a». Здесь у нас есть второй случай из предыдущего раздела. Значение k остается равным нулю, и значение функции префикса для подстроки «ab» также равно нулю.

3. То же самое и с подстроками «abc» и «abcd». Нет префиксов, которые также являются суффиксами этих подстрок. Значение для них остается на нуле.

4. Теперь давайте рассмотрим интересный случай, подстроку «abcda». Текущее значение k по-прежнему равно нулю, но последний символ нашей подстроки совпадает с ее первым символом. Это вызывает условие s[k] == s[i] , где k == 0 и i == 4 . Массив имеет нулевой индекс, а k — это индекс следующего символа для префикса максимальной длины. Это означает, что мы нашли префикс максимальной длины для нашей подстроки, который также является суффиксом. У нас есть первый случай, когда новое значение k равно единице, и, следовательно, значение префиксной функции P («abcda») равно единице.

5. То же самое происходит и для следующих двух подстрок: P("abcdab") = 2 и P("abcdabc") = 3 . Здесь мы ищем наш образец в тексте, сравнивая строки посимвольно. Допустим, первые семь символов шаблона совпали с какими-то семью последовательными символами обрабатываемого текста, но на восьмом символе совпадения нет. Что должно произойти дальше? В случае наивного сопоставления строк мы должны вернуть семь символов назад и снова начать процесс сравнения с первого символа нашего шаблона. Со значением функции префикса (здесь P("abcdabc") = 3 ) мы знаем, что наш трехсимвольный суффикс уже соответствует трем символам текста. А если следующим символом в тексте является «d», длина совпадающей подстроки нашего шаблона и подстроки в тексте увеличивается до четырех («abcd»). В противном случае P("abc") = 0 и мы начнем процесс сравнения с первого символа шаблона. Но важно то, что мы не возвращаемся во время обработки текста.

6. Следующая подстрока — «abcdabca». В предыдущей подстроке функция префикса была равна трем. Это означает, что k = 3 больше нуля, и в то же время мы имеем несоответствие между следующим символом в префиксе ( s[k] = s[3] = "d" ) и следующим символом в суффиксе ( s[i] = s[7] = "a" ). Это означает, что мы вызвали условие s[k] != s[i] и что префикс «abcd» не может быть суффиксом нашей строки. Мы должны уменьшить значение k и взять для сравнения предыдущий префикс, где это возможно. Как мы описали выше, массив имеет нулевой индекс, а k — это индекс следующего символа, который мы проверяем из префикса. Последний индекс совпавшего в данный момент префикса равен k - 1 . Мы берем значение функции префикса для текущего совпавшего префикса k = result[k - 1] . В нашем случае (третьем случае) длина максимального префикса уменьшится до нуля, а затем в следующей строке будет увеличена до единицы, потому что «а» — это максимальный префикс, который также является суффиксом нашей подстроки.

7. (Здесь мы продолжаем процесс вычислений, пока не дойдем до более интересного случая.)

8. Мы начинаем обрабатывать следующую подстроку: «abcdabcabcdabcd». Текущее значение k равно семи. Как и в случае с «abcdabca» выше, мы столкнулись с несоответствием: поскольку символ «a» (седьмой символ) не равен символу «d», подстрока «abcdabca» не может быть суффиксом нашей строки. Теперь мы получаем уже вычисленное значение функции префикса для «abcdabc» (три) и теперь у нас есть совпадение: Префикс «abcd» также является суффиксом нашей строки. Его максимальный префикс и значение функции префикса для нашей подстроки равно четырем, потому что таким стало текущее значение k .

9. Продолжаем этот процесс до конца узора.

Короче говоря: оба цикла занимают не более 3 миллионов итераций, что доказывает, что сложность составляет O (M). Использование памяти также равно O(M).

Реализация алгоритма 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; }

Приведенный выше алгоритм выполняет итерацию по тексту, символ за символом, и пытается увеличить максимальный префикс как для нашего шаблона, так и для некоторой последовательности последовательных символов в тексте. В случае неудачи мы не вернемся к предыдущей позиции по тексту. Мы знаем максимальный префикс найденной подстроки шаблона; этот префикс также является суффиксом этой найденной подстроки и мы можем просто продолжить поиск.

Сложность этой функции такая же, как и у префиксной функции, что делает общую вычислительную сложность O(N + M) при O(M) памяти.

Интересный факт: методы String.IndexOf() и String.Contains() в .NET framework имеют под капотом алгоритм такой же сложности.

Алгоритм Ахо-Корасика

Теперь мы хотим сделать то же самое для нескольких шаблонов.

Предположим, что имеется M паттернов длин L1 , L2 , …, Lm . Нам нужно найти все совпадения шаблонов из словаря в тексте длины N .

Тривиальным решением было бы взять любой алгоритм из первой части и запустить его M раз. У нас есть сложность O(N + L1 + N + L2 + … + N + Lm) , то есть O(M * N + L) .

Любой достаточно серьезный тест убивает этот алгоритм.

Взять словарь с 1000 самых распространенных английских слов в качестве шаблонов и использовать его для поиска в английской версии «Войны и мира» Толстого — это заняло бы довольно много времени. В книге более трех миллионов знаков.

Если мы возьмем 10 000 самых распространенных английских слов, алгоритм будет работать примерно в 10 раз медленнее. Очевидно, что при входных данных, превышающих этот, время выполнения также будет расти.

Именно здесь алгоритм Ахо-Корасика творит чудеса.

Сложность алгоритма Ахо-Корасика составляет O(N + L + Z) , где Z — количество совпадений. Этот алгоритм был изобретен Альфредом В. Ахо и Маргарет Дж. Корасик в 1975 году.

Реализация

Здесь нам понадобится trie, и мы добавим в наш алгоритм аналогичную идею префиксным функциям, описанным выше. Мы будем вычислять значения префиксной функции для всего словаря.

Каждая вершина в дереве будет хранить следующую информацию:

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

Существует несколько способов реализации дочерних ссылок. Алгоритм будет иметь сложность O(N + L + Z) в случае массива, но для этого потребуется дополнительная память O(L * q) , где q — длина алфавита, поскольку это максимальное количество потомков, которое может иметь узел.

Если мы используем некоторую структуру с O(log(q)) доступом к ее элементам, у нас есть дополнительное требование к памяти O(L) , но сложность всего алгоритма будет O((N + L) * log(q) + З) .

В случае хэш-таблицы у нас есть O(L) дополнительной памяти, а сложность всего алгоритма будет O(N + L + 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++; } }

Затем мы добавляем все шаблоны в файл 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); }

На данный момент все слова шаблона находятся в структуре данных. Это требует дополнительной памяти O(L) .

Далее нам нужно вычислить все суффиксные ссылки и ссылки на словарные статьи.

Чтобы сделать его ясным и простым для понимания, я собираюсь пройти по нашему дереву от корня к листьям и произвести вычисления, подобные тем, которые мы сделали для алгоритма KMP, но в отличие от алгоритма KMP, где мы находим максимальную длину префикс, который также был суффиксом той же подстроки, теперь мы найдем суффикс максимальной длины текущей подстроки, который также является префиксом некоторого шаблона в дереве. Значением этой функции будет не длина найденного суффикса; это будет ссылка на последний символ максимального суффикса текущей подстроки. Вот что я имею в виду под суффиксной ссылкой вершины.

Буду обрабатывать вершины по уровням. Для этого я буду использовать алгоритм поиска в ширину (BFS):

А ниже реализация этого обхода:

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

А ниже показан метод CalcSuffLink для вычисления суффиксной ссылки для каждой вершины (т. е. значения префиксной функции для каждой подстроки в дереве):

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

Сложность этого метода O(L) ; в зависимости от реализации дочерней коллекции сложность может быть O(L * log(q)) .

Доказательство сложности аналогично доказательству префиксной функции сложности в алгоритме KMP.

Давайте посмотрим на следующее изображение. Это визуализация словаря { abba, cab, baba, caab, ac, abac, bac } со всей вычисляемой информацией:

Края треугольника окрашены в темно-синий цвет, ссылки суффикса — светло-голубые, а ссылки суффикса словаря — в зеленый цвет. Узлы, соответствующие словарным статьям, выделены синим цветом.

А теперь нам нужен только еще один метод — обработка блока текста, в котором мы собираемся искать:

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

И теперь это готово к использованию:

На входе у нас есть список паттернов:

 List<string> patterns;

И текст поиска:

 string text;

А вот как склеить:

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

Вот и все! Теперь вы знаете, как работает этот простой, но мощный алгоритм!

Ахо-Корасик действительно гибкий. Шаблоны поиска не обязательно должны состоять только из слов, мы можем использовать целые предложения или случайные цепочки символов.

Представление

Алгоритм был протестирован на Intel Core i7-4702MQ.

Для тестов я взял два словаря: «1000 самых распространенных английских слов» и «10 000 самых распространенных английских слов».

Чтобы добавить все эти слова в словарь и подготовить структуру данных для работы с каждым из словарей, алгоритму потребовалось 55 мс и 135 мс соответственно.

Алгоритм обрабатывал настоящие книги длиной 3-4 миллиона знаков за 1,0-1,3 секунды, в то время как для книги, содержащей около 30 миллионов знаков, потребовалось 9,6 секунды.

Распараллеливание алгоритма Ахо-Корасика

Идти параллельно с алгоритмом Ахо-Корасика вообще не проблема:

Большой текст можно разделить на несколько фрагментов, и для обработки каждого фрагмента можно использовать несколько потоков. Каждый поток имеет доступ к сгенерированному trie на основе словаря.

Как насчет разделения слов на границе между фрагментами? Эту проблему можно легко решить.

Пусть N будет длиной нашего большого текста, S — размером фрагмента, а L — длиной самого большого шаблона в словаре.

Теперь мы можем использовать простой трюк. Мы разделяем фрагменты с некоторым перекрытием в конце, например, беря [S * (i - 1), S * i + L - 1] , где i - индекс фрагмента. Когда мы получаем совпадение с шаблоном, мы можем легко получить начальный индекс текущего совпадения и просто проверить, что этот индекс находится в пределах диапазона фрагментов без перекрытий, [S * (i - 1), S * i - 1] .

Универсальный алгоритм поиска строк

Алгоритм Ахо-Корасика — это мощный алгоритм сопоставления строк, который предлагает наилучшую сложность для любых входных данных и не требует много дополнительной памяти.

Алгоритм часто используется в различных системах, таких как проверка орфографии, спам-фильтры, поисковые системы, биоинформатика/поиск последовательности ДНК и т. д. Фактически, некоторые популярные инструменты, которые вы можете использовать каждый день, используют этот алгоритм за кулисами.

Функция префикса из алгоритма KMP сама по себе является интересным инструментом, который сводит сложность сопоставления одного шаблона к линейному времени. Алгоритм Ахо-Корасика следует аналогичному подходу и использует структуру данных trie, чтобы сделать то же самое для нескольких шаблонов.

Я надеюсь, что вы нашли это руководство по алгоритму Ахо-Корасика полезным.