Научно-технический журнал МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ УДК 004.651 А.Н. ГРИГОРЬЕВА АЛГОРИТМ ЭФФЕКТИВНОГО ПОСТРОЕНИЯ МНОЖЕСТВА КЛЮЧЕЙ ИНДЕКСА НА ОСНОВЕ МУЛЬТИГРАММ В данной статье рассмотрены методы индексирования строк, обоснован выбор индекса на основе мультиграмм для ускорения поиска по фрагментам и регулярным выражениям. <...> Для эффективного построения индекса разработана модификация алгоритма построения множества ключей индекса. <...> Некоторые виды поиска (например, поиск по словам) хорошо проработаны и используются во многих поисковых системах. <...> Однако существует ряд задач, требующих других видов поиска, таких, как поиск по подстроке, по регулярным выражениям или более простым шаблонам и другие. <...> Целью данной работы является создание индекса с использованием подстрок в качестве индексируемых элементов, который позволяет ускорять поиск по подстрокам и более сложным шаблонам (вплоть до регулярных выражений), а также по сходству. <...> Для этого был решен ряд задач: − выполнен анализ существующих методов индексирования строк, обоснован выбор мультиграммного индекса в качестве основы разработки; − выполнена модификация алгоритма построения индекса, позволяющая существенно повысить скорость его работы; − получены экспериментальные результаты по времени работы и требованию к памяти. <...> АНАЛИЗ МЕТОДОВ ИНДЕКСИРОВАНИЯ СТРОК Для индексирования строк разработан целый ряд структур данных – суффиксные деревья, суффиксные массивы, String-B-деревья, индексы на базе подстрок фиксированной и переменной длины (k-gram и multigram) и др. <...> К сожалению, многие структуры хорошо работают лишь в оперативной памяти, но возможность их применения существенно снижается при росте объемов входных данных. <...> Классические же индексы для внешней памяти (разновидности B-деревьев и хеш-таблицы) напрямую для рассмотренных видов 86 №5(91)2015 а Информационные системы и технологии <...>