Масштабируемость aho corasick

Question

Я хочу найти в текстовом документе вхождения ключевых фраз в базе данных ключевых фраз (извлечено из заголовков статей в Википедии). (т. е. учитывая документ, который я хочу выяснить, есть ли у каждой фразы соответствующая статья в википедии), я узнал об алгоритме Ахо-Корасика Я хочу знать, является ли создание автомата Aho-Corasick для словаря миллионов записей эффективным и масштабируемым.

Answer 1

Давайте просто сделаем простые вычисления:

Предположим, что у вас есть 1 миллион шаблонов (строк, фраз) со средней длиной 10 символов и значением (метка, маркер, указатель и т. Д.) Длиной 1 слово (4 байта), назначенным каждому шаблону

Тогда вам понадобится массив размером 10 + 4 = 14 миллионов байт (14 МБ), чтобы хранить список шаблонов.

Из 1 миллиона шаблонов по 10 байтов (букв, символов) вы можете создать три AC-цепочки, содержащие не более 10 миллионов узлов. Насколько большой это дерево на практике зависит от размера каждого узла. В нем должно быть не менее 1 байта для метки (буквы) и слова (4 байта) для указателя на следующий узел в три (или шаблона для терминального узла) плюс 1 бит (логическое значение) для маркировки терминального узла, Всего около 5 байт

Итак, для минимального размера дерева для 1 миллиона шаблонов на 10 символов вам потребуется минимум 50 миллионов байтов или около 50 МБ памяти.

На практике это может быть в 3-10 раз больше, но все же очень-очень управляемо, так как даже память 500 МБ сегодня очень умеренная. (Сравните это с приложениями Windows, такими как Word или Outlook)

Учитывая, что с точки зрения скорости алгоритм Aho-Corasick (AC) практически непобедим, он все еще остается лучшим алгоритмом для сопоставления с несколькими образцами. Это мое сильное личное образованное мнение, кроме академического мусора.

Все сообщения о "новых" новейших и лучших алгоритмах, которые могут превосходить AC, сильно преувеличены (за исключением, может быть, некоторых особых случаев с короткими паттернами, такими как ДНК)

Единственное улучшение AC может на практике идти по линии более мощного оборудования (многоядерные, более быстрые процессоры, кластеры и т. Д.)

Не верь мне на слово, проверь это на себе. Но помните, что реальная скорость AC сильно зависит от реализации (язык и качество кодирования)

Answer 2

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

OTOH большой выигрыш в Aho-Corasick заключается в поиске подстрок достойного размера, которые могут возникнуть в любом возможном месте в пределах строки ввода. Если ваш текстовый документ уже разрезан на слова, и ваши поисковые фразы больше не нужны чем, например, 6 слов, затем вы можете создать хэш-таблицу из K-словосочетаний, а затем найти каждый смежный K-словесный раздел слов из входного текста в нем, для K = 1..6.

(Ответ на комментарий)

Ахо-Корасик должен жить в памяти, потому что вы будете следовать указателям повсюду. Если вам нужно работать вне памяти, возможно, проще всего вернуться к старомодной сортировке / слиянию. Создайте файл записей K-слов из входных данных, где K - максимальное количество слов в любой интересующей вас фразе. Сортируйте его, а затем объедините с файлом отсортированных фраз Википедии. Вы, вероятно, можете сделать это почти вручную в Unix / Linux, используя такие утилиты, как sort и join и немного shell / awk / perl / что угодно. См. Также http://en.wikipedia.org/wiki/Key_Word_in_Context (я достаточно взрослый, чтобы фактически использовать один из этих индексов, предоставленных в виде переплетенных страниц компьютерной распечатки).

Answer 3

Ну, есть обходной путь. Записав встроенный AC словарь в текстовый файл в формате, похожем на XML, создав индексный файл для первых 6 уровней этого дерева и т. Д. В моих тестах я ищу все частичные совпадения предложения словарь (500 000 записей), и я получаю ~ 150 мс для ~ 100 результатов для предложения из 150-200 символов.

Для получения более подробной информации, посмотрите эту статью: http://212.34.233.26/aram/IJITA17v2A.Avetisyan.doc

Answer 4

Существуют и другие способы получения производительности: - сжатие переходов между состояниями: их можно уменьшить до 32 бит.- угробить указатели;записать переходы состояний в плоский вектор.- упаковать узлы возле корня дерева вместе: они будут в кеше.Реализация занимает около 3 байтов на символ исходного набора шаблонов, а для 32-битных узлов может занимать пространство шаблона около 10 миллионов символов.Для 64-битных узлов еще не достигнут (или покажет) предел.

Документ: https://docs.google.com/document/d/1e9Qbn22__togYgQ7PNyCz3YzIIVPKvrf8PCrFa74IFM/view Источник: https://github.com/mischasan/aho-corasick