Данный проект предполагает исследование задач, связанных с обработкой сжатых текстовых и текстоподобных данных. Рост объема таких данных значительно опережает рост производительности компьютеров; при этом общее развитие информационных технологий диктует всё новые требования к обработки больших объёмов данных. Возникающий разрыв между желаниями и возможностями обработки данных порождает ряд как теоретических, так и практических вызовов. Проект предусматривает исследования сжатых форм хранения данных с возможностью быстрого поиска и доступа к ним. В данной теме достаточно много конкурирующих исследований. Будут рассмотрены как чисто теоретические задачи (установление пределов возможностей для алгоритмов и структур данных в соответствующих моделях вычислений), так и задачи, имеющие прикладное значение (новые виды индексных структур данных и алгоритмы поиска в них). Руководитель уже имеет опыт успешных исследований в данной области, вылившийся в публикации высокого международного уровня. Ниже более подробно раскрыто содержание проекта.
В связи с растущими объемами обрабатываемых текстовых данных остро встает вопрос построения так называемых сжатых индексов, способных обеспечивать быстрый доступ к сжатым коллекциям текста, которые в противном случае не удалось бы за разумное время обрабатывать и осуществлять поиск в них. Подобные индексы не новы (первые относительно эффективные версии появились в начале 2000-х), но по-прежнему активно разрабатываются и совершенствуются многими международными научными коллективами, потому что для многих задач (например, обработки банков биологических последовательностей) мощностей существующих индексирующих инструментов недостаточно. Современные индексы обычно представляют собой сложные математические конструкции, основанные на эффективно вычислимых комбинаторных преобразованиях (таких, как преобразование Барроуза-Уилера или разложение Лемпеля-Зива) и содержащие ряд вспомогательных структур данных для мгновенных ответов на нетривиальные запросы типа минимума на отрезке или общего предка в дереве. В рамках проекта будут получены новые и усовершенствованы известные версии сжатых индексных структур данных.
В проекте предполагается разработать индексы, ориентированные преимущественно на так называемые сильно сжимаемые данные (базы данных систем контроля версий, базы схожих геномных последовательностей, файлы журналирования различных систем и так далее). Такие индексы, в отличие от обычных индексов, которые в большинстве основаны на так называемом разложении Барроуза-Уилера, опирается на другую технику, называемую разложением Лемпеля-Зива; отметим, что руководитель активно и успешно работал над решением ряда задач, тесно связанных с этим разложением и его модификациями, и результатом этой работы явился ряд публикаций на конференциях высокого международного уровня. Предполагается рассмотреть два вопроса: поиск шаблонов в индексированных данных (что является базовым функционалом, необходимым для задач анализа данных) и редактирование данных (функционал, который более специфичен для рассматриваемых сильно сжимаемых данных). По первому вопросу: алгоритмы поиска шаблонов в большинстве существующих на данный момент индексов, основанных на разложении Лемпеля-Зива, квадратичны по времени (что достаточно медленно); предполагается, что, скомбинировав структуры данных, разработанные руководителем проекта и недавно опубликованные, можно существенно улучшить эти алгоритмы. По второму вопросу нет никаких сколь-нибудь эффективных индексов для сильно сжимаемых данных, которые позволяли бы эффективно модифицировать сжатые данные, даже если такие модификации всего лишь добавляют новые куски ("документы" в обычной терминологии) в конец уже обработанных и индексированных данных. Такой особый тип модификаций особенно важен для многих приложений сжатых индексов. Предполагается закрыть данный пробел с помощью тех же техник, которые руководитель проекта недавно успешно применял при создании индекса, основанного на некоторой модификации разложения Лемпеля-Зива.
В рассматриваемом направлении исследования сжатых структур данных у руководителя имеются результаты и публикации мирового уровня, что позволит активно конкурировать на международном уровне и обеспечит успешное выполнение проекта.
Результатами проекта будут математические модели, структуры данных, алгоритмы, а также теоретические и экспериментальные оценки их релевантности и эффективности. Результаты обеспечат дальнейший прогресс в области информационного поиска, а также будут применимы в широком спектре практических приложений.