Сжатый индекс для поиска строк
Аннотация
Сивухин Н.С. Сжатый индекс для поиска строк, стр. 33, источников 17, изображений 3, 1 таблица.
Ключевые слова: ПОИСК ШАБЛОНОВ В ТЕКСТЕ ПО СЛОВАРЮ, АЛГОРИТМ АХО-КОРАСИК, СЖАТЫЕ СТРУКТУРЫ ДАННЫХ, RAM-МОДЕЛЬ, СТРОКИ.
В работе представлен алгоритм построения сжатого индекса для поиска множества строк в произвольном тексте.Полученный результат решает известную открытую проблему и на текущий момент является самым компактным алгоритмом, основанным на идее алгоритма Ахо-Корасик. Также, в качестве сопутствующего результата, было уточнено определение энтропии k-го порядка для произвольного помеченного дерева и показана несостоятельность в некоторых случаях определения, данного в статье Хона и др.
Ключевые слова: ПОИСК ШАБЛОНОВ В ТЕКСТЕ ПО СЛОВАРЮ, АЛГОРИТМ АХО-КОРАСИК, СЖАТЫЕ СТРУКТУРЫ ДАННЫХ, RAM-МОДЕЛЬ, СТРОКИ.
В работе представлен алгоритм построения сжатого индекса для поиска множества строк в произвольном тексте.Полученный результат решает известную открытую проблему и на текущий момент является самым компактным алгоритмом, основанным на идее алгоритма Ахо-Корасик. Также, в качестве сопутствующего результата, было уточнено определение энтропии k-го порядка для произвольного помеченного дерева и показана несостоятельность в некоторых случаях определения, данного в статье Хона и др.