Описание тега aho-corasick

Вопросы с тегом
Алгоритм сопоставления строк Aho-Corasick - это быстрый алгоритм для поиска всех вхождений набора подстрок в тексте шаблона. Это обобщение алгоритма Кнута-Морриса-Пратта.
1 ответ

Являются ли ссылки суффиксов в дереве суффиксов такими же, как рёбра неудачи в ахо-коразическом автомате?

Если да, может ли кто-нибудь объяснить назначение суффиксных ссылок в дереве суффиксов для точного сопоставления строк?
04 окт '16 в 15:52
1 ответ

Aho-Corasick-подобный алгоритм для использования в антивирусном коде

Существует ли такой алгоритм, как Aho-Corasick, который может одновременно сопоставлять набор шаблонов и может использоваться для сравнения антивирусных программ? Все ли известные коммерческие антивирусные программы используют алгоритм Aho-Corasick?…
04 ноя '11 в 18:32
2 ответа

Java реализация алгоритма сопоставления строк Aho-Corasick?

Теперь я знаю, что были предыдущие вопросы относительно этого алгоритма, однако, честно говоря, я не сталкивался с простой реализацией Java. Многие люди скопировали и вставили один и тот же код в свои профили GitHub, и это меня раздражает. Поэтому д…
24 окт '17 в 23:01
1 ответ

Как сгенерировать хеш Aho-Corasick

Недавно я начал разработку антивирусного программного обеспечения с открытым исходным кодом, хотя хэши генерируются с помощью алгоритма Aho-Corasick. Я хотел бы знать, как генерировать хеш-коды Aho-Corasick из исполняемых файлов, так как я почти не …
08 апр '11 в 22:46
2 ответа

Зачем нужен блок else в методе "push_links" следующего кода?

Этот код для алгоритма Aho-Corasick, который я отсюда рецензировал Я понял этот код до блока if метода push_links, но я не получил использование или требование для остальной части того же метода. Более конкретно, первый метод используется для постро…
12 июн '15 в 17:13
1 ответ

Алгоритм Кнута-Морриса-Пратта в Хаскеле

У меня проблемы с пониманием этой реализации алгоритма Кнута-Морриса-Пратта в Haskell. http://twanvl.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell В частности, я не понимаю конструкцию автомата. Я знаю, что он использует метод "Связывание узла" для …
22 май '13 в 14:21
1 ответ

Эффективное хранение Trie для веб-приложения

У меня есть трио Aho Corasick, через которое я анализирую текст. Теперь этот три существует как часть моего приложения фляги. Он развернут на Heroku, и в настоящее время я наивно храню маринованные формы автомата, открываю их при необходимости и исп…
10 янв '17 в 10:17
1 ответ

Как использовать Aho-Corasick, чтобы найти фрагмент текста в заданном наборе строк?

У меня есть код алгоритма Aho-Corasick. Но я все еще не понимаю, как использовать информацию о состоянии во время процедуры поиска при поиске текста в заданном списке строк. Например у меня есть список строк [MOSCOW][COLA]и теперь мне нужно определи…
18 июл '12 в 12:36
1 ответ

Использование регулярных выражений в исходном тексте Python

Я пытаюсь создать скрипт, который позволит пользователю вводить ряд регулярных выражений, которые будут проходить через входной файл и получать совпадения. В настоящее время я использую ahocorasick, но у меня возникают проблемы, когда я пытаюсь ввес…
26 янв '15 в 14:24
1 ответ

Сбой при использовании ахорайного алгоритма?

Я получил код для алгоритма ахораксика здесь: http://www.komodia.com/aho-corasick. Я использовал его, как сказал гид, добавил линии и построил дерево. Однако я изменил его с использования std wstring на std string, но это не должно иметь значения. Я…
05 июн '12 в 06:27
1 ответ

Использование python (acora) для поиска строк, содержащих ключевые слова

Я пишу программу, которая читает в каталоге текстовых файлов и находит определенную комбинацию строк, которые перекрываются (то есть совместно используются всеми файлами). Мой текущий подход заключается в том, чтобы взять один файл из этого каталога…
12 фев '18 в 16:56
1 ответ

Функция вывода для алгоритма Aho-Corasick

У меня проблема с реализацией функции вывода для алгоритма Aho-Corasick. В общем, я не совсем понимаю, как работает функция вывода. В соответствии с этой статьей в функции goto я помещаю соответствующий индекс шаблона для вывода, например output[cur…
30 июн '17 в 14:51
1 ответ

Почему не работает лямбда-пример в hankcs/AhoCorasickDoubleArrayTrie?

Я просто копирую пример со страницы проекта github без каких-либо изменений, и это дает мне ошибку компиляции Чтобы воспроизвести, добавьте эту зависимость к вашему пом <dependency> <groupId>com.hankcs</groupId> <artifactId>a…
31 янв '19 в 22:20
3 ответа

Как я могу ускорить мой алгоритм Aho-Corasick?

Я пытаюсь решить проблему на HackerRank; "Определение здоровья ДНК". После некоторых обсуждений я решил, что алгоритм Ахо-Корасика будет лучшим выбором. Проблема заключается в поиске строки для различных последовательностей со связанным значением. З…
29 май '18 в 04:07
1 ответ

Алгоритм, чтобы найти, сколько подстрок в диапазоне больших чисел

У меня есть проблема с этим упражнением: Учитывая диапазон от А до Б с 1 <= A,B <= 10^18 и некоторое целое число, представляющее подстроку Ni с 1 <= i <= 1000;вернуть общее количество возможных чисел в диапазоне между A, B (включая A и B…
26 сен '13 в 22:47
1 ответ

Поиск шаблонов в большом текстовом файле (в настоящее время с Aho-Corasick)

У меня большой текстовый файл (5-500 МБ) и набор из нескольких тысяч шаблонов. Для каждого шаблона я хочу получить количество вхождений шаблона в файл. Текст не содержит пробелов и является базовой длинной буквенно-цифровой строкой. Для этой цели я …
25 сен '18 в 16:23
2 ответа

Количество вхождений подстрок в строку в O(N)

Мне было интересно, как посчитать количество вхождений каждой иглы в стоге сена за линейное время. Я думал, что буду использовать алгоритм Aho-Corasick, но я не хочу, чтобы сложность времени зависела от количества попаданий игл.
19 ноя '16 в 20:50
0 ответов

Как сделать несколько поисков внутри объекта NSData?

TL, DR Смотрите эту функцию члена NSData (Свифт здесь): func rangeOfData(_ dataToFind: NSData, options mask: NSDataSearchOptions, range searchRange: NSRange) -> NSRange Я хочу заменить этот первый параметр на Set (или другая коллекция) NSData и в…
11 апр '16 в 20:08
1 ответ

Как я могу эффективно найти всех людей, упомянутых в каком-либо тексте, терпя при этом орфографические ошибки?

У меня есть список имен миллионов известных людей (из Викиданных), и мне нужно создать систему, которая бы эффективно находила всех людей, упомянутых в довольно коротком тексте: это может быть всего одно слово (например, "Эйнштейн") для несколько ст…
15 ноя '16 в 15:57
1 ответ

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

Пожалуйста, помогите мне найти ошибки в этом коде. Я написал простую программу, которая добавляет n строк в три по алгоритму Aho-Corasick, но он не работает правильно. Сбой после ввода строк. Что не так с этим кодом? #include <cstdlib> #includ…
23 мар '13 в 15:37