Комментарии 16
Хотелось бы еще сравнения с другими алгоритмами, вроде Кнута-Морриса-Пратта и области применения.
Насколько я понимаю, Ахо-Корасик выгоден, когда нужно искать одновременно несколько постоянных паттернов, а текст каждый раз новый (например, поиск стоп-слов при ранжировании для поисковиков).
Насколько я понимаю, Ахо-Корасик выгоден, когда нужно искать одновременно несколько постоянных паттернов, а текст каждый раз новый (например, поиск стоп-слов при ранжировании для поисковиков).
Кнут-Моррис-Пратт — другая задача, тут скорее можно тривиально модифицировать Рабина-Карпа
Расскажите, пожалуйста, как вы можете модифицировать Рабина-Карпа для паттернов разной длины? Я умею только добиваться времени O(n * sqrt(sum m)) при помощи знания, что различных длин у строк суммарной длины sum не более квадратного корня из sum. После этого для каждой из различных длин делаем один проход по haystack.
Тривиально так как вы и написали:
1) Храним строки (хеш, trie — не суть)
2) Храним длины
За каждый сдвиг вырезаем по всем длинам и ищем в строках.
Менее тривиально так:
1) Храним строки
2) Храним словарик из префиксов длины length, каждому из них соответствует набор длин, для которых есть слова
Идем по тексту, с каждого символа вырезаем все длины меньше length и ищем в строках. Потом вырезаем строку длины length, ищем в префиксах, получаем список длин. Каждую длину вырезаем, ищем в строках.
Можно играться с длиной префикса, чтобы получить оптимальную скорость на конкретных данных.
По памяти получается лучше, чем непожатый ДКА из Ахо-Корасик, по скорости конечно хуже.
1) Храним строки (хеш, trie — не суть)
2) Храним длины
За каждый сдвиг вырезаем по всем длинам и ищем в строках.
Менее тривиально так:
1) Храним строки
2) Храним словарик из префиксов длины length, каждому из них соответствует набор длин, для которых есть слова
Идем по тексту, с каждого символа вырезаем все длины меньше length и ищем в строках. Потом вырезаем строку длины length, ищем в префиксах, получаем список длин. Каждую длину вырезаем, ищем в строках.
Можно играться с длиной префикса, чтобы получить оптимальную скорость на конкретных данных.
По памяти получается лучше, чем непожатый ДКА из Ахо-Корасик, по скорости конечно хуже.
Да. Алгоритм Рабина-Карпа у нас оказался гораздо практичнее из-за гораздо более экономного потребления памяти.
del
Попробуйте описать Ву-Манбера на фильтрах Блума, вам понравится!
вот интересно… для частного случая, если слова состоят из букв-байтов, то в 128битный регистр SSE помещается сразу 16 букв. Одной или двумя SSE командами процессора Intel можно сравнить 16 букв двух строк. не получится ли такое решение в лоб быстрее, чем по деревьям лазить?
Замечательно. Расскажите еще, пожалуйста, про какие-нибудь строковые структуры, например, про суффиксное дерево или автомат, вроде, они более применимы на практике.
На хабре уже есть статьи про эти структуры данных:
http://habrahabr.ru/post/111675/
http://habrahabr.ru/post/115346/
http://habrahabr.ru/post/111675/
http://habrahabr.ru/post/115346/
Хочется сделать несколько замечаний к предложенному алгоритму:
1. Можно не выполнять построение автомата вообще (т.е. убрать кэширование переходов по символам, которые построены из суффиксных ссылкок). При этом время проверки одного haystack (строки, где ищем вхождения) останется линейным (и зависящим от алфавита в худшем случае логарифмически). Остальной код (кроме отсутствия кэширования) остаётся прежним. Время работы доказывается аналогично КМП: проследим за глубиной текущей вершины. Она неотрицательно и увеличивается не более, чем на длину haystack. Значит, уменьшается не более, чем на столько же.
2. Если требуется в некотором смысле персистентный поиск (например, у нас есть другой бор, в котором лежат haystack с квадратичной суммарной длиной), то предыдущий трюк уже не прокатит — он линеен относительно суммарной длины всех haystack.
3. Предподсчёт можно выполнять не только лениво, но и в bfs, Это улучшит константу.
1. Можно не выполнять построение автомата вообще (т.е. убрать кэширование переходов по символам, которые построены из суффиксных ссылкок). При этом время проверки одного haystack (строки, где ищем вхождения) останется линейным (и зависящим от алфавита в худшем случае логарифмически). Остальной код (кроме отсутствия кэширования) остаётся прежним. Время работы доказывается аналогично КМП: проследим за глубиной текущей вершины. Она неотрицательно и увеличивается не более, чем на длину haystack. Значит, уменьшается не более, чем на столько же.
2. Если требуется в некотором смысле персистентный поиск (например, у нас есть другой бор, в котором лежат haystack с квадратичной суммарной длиной), то предыдущий трюк уже не прокатит — он линеен относительно суммарной длины всех haystack.
3. Предподсчёт можно выполнять не только лениво, но и в bfs, Это улучшит константу.
Честно говоря, не понимаю, в чем заключается разница между понятиями «Бор» и «ДКА» в данном контексте. Бор здесь — это обычный детерминированный конечный автомат, используемый для хранения словаря (набора слов из некоторого алфавита). Этот автомат здесь, в силу особенностей своего построения, имеет древовидную структуру переходов, но и только — все остальное у него ничем от автомата не отличается. В библиотеке я так и определяю: AcAutomaton наследует класс Trie, который наследует Fsm. Trie полезен сам по себе, например используется для хранения словаря.
Спасибо автору за статью и за код (взял, как основу). Пришлось допилить, т.к. проблема с кириллицей. Еще одно доработка, полезная когда образцов немного — массивы признаков, если ли символ в хотя бы в одном образце и есть ли символ в начале образца.
Для поиска символов юникода изменения посерьезнее, но и скорость увеличилась раз в 10 по сравнению с вариантом, когда символ юникода тупо записывался в 2 узла.
Для поиска символов юникода изменения посерьезнее, но и скорость увеличилась раз в 10 по сравнению с вариантом, когда символ юникода тупо записывался в 2 узла.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм Ахо-Корасик