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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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

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

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

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

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

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

Ответ 3

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

Подробнее см. в этой статье: http://212.34.233.26/aram/IJITA17v2A.Avetisyan.doc