Аннотация результатов, полученных в 2018 году
Одной из стандартных задач информационного поиска является поиск фиксированного набора образцов в потоке данных. Типичные приложения, где эта задача возникает в явном виде, - это детектирование вирусов в интернет трафике (здесь образцы - это фрагменты известных вирусов, а поток данных - это трафик), поиск больших наборов ключевых слов в текстовых базах данных (здесь образцы - это ключевые слова, а поток данных - это тексты) и поиск фрагментов ДНК в геноме (если не вдаваться в детали, современные технологии читают ДНК не полностью, а кусками по 100-500 нуклеотидов, и нередко встаёт задача поиска вхождений большого набора таких кусков в уже имеющемся геноме). Для решения этой задачи обычно используют хорошо известную изобретённую ещё в 1975-м году структуру данных, называемую автоматом Ахо-Корасик. Автомат Ахо-Корасик позволяет искать образцы в потоке данных, последовательно обрабатывая каждый байт потока за фиксированное время в среднем и находя вхождения образцов, как только те появляются; таким образом, это в некотором смысле лучшее возможное решение данной задачи. Но во многих случаях в вышеперечисленных и подобных им приложениях множество образцов очень велико, так что автомат Ахо-Корасик становится слишком большим и не вмещается в доступную память (особенно когда ресурсы системы ограничены, как при анализе интернет трафика в маршрутизаторах). Для решения этой проблемы за последние два десятилетия было разработано несколько вариантов автомата Ахо-Корасик, которые нетривиальным образом используют технологии сжатия данных для уменьшения потребляемой автоматом памяти, -- благодаря сжатию автомат в некоторых случаях может занимать даже меньше памяти, чем несжатые образцы, входящие в него. Лучшие теоретические сжатые варианты автомата Ахо-Корасик были описаны в статье Белаззоги в 2010-м году [Belazzougui. Succinct dictionary matching with no slowdown. SPIRE 2010] и группой Хона и др. в 2013-м году [Hon et al. Faster compressed dictionary matching. Theor. Comp. Sci. 2013]: этим авторам почти удалось добиться так называемого энтропийного сжатия k-го порядка (это одна из наилучших метрик измерения эффективности методов сжатия) без существенного замедления работы автомата. В результатах Белаззоги и Хона и др. есть два существенных недостатка, один из которых теоретический, другой практический. Во-первых, эти авторы не смогли оценить, можно ли ещё теоретически улучшить потребляемую их решениями память и достигнуть в итоге энтропию k-го порядка (без замедления автомата); они оставили это в качестве открытой проблемы. Во-вторых, в силу технической нагруженности полученных Хоном и др. построений эти авторы не смогли предоставить реализаций своих алгоритмов и не провели экспериментальных сравнений с существующими подходами для решения задачи поиска образцов; Белаззоги, чьё решение теоретически уступает решению Хона и др. (оно метит в энтропию нулевого порядка, а не k-го), тоже не проделал такой работы, хотя его построения вполне допускает это. В рамках проекта нам удалось существенно продвинуться в решении этих проблем (в некотором смысле можно даже считать их решёнными). Нами разработана новая структура данных, которая так же как и все предыдущие представляет собой автомат Ахо-Корасик, закодированный некоторым нетривиальным образом с применением технологий сжатия данных, и достигает энтропии k-го порядка без существенного замедления времени работы автомата (в частности, асимптотически замедления вообще нет - наш вариант работает за то же время, что и классический несжатый автомат). По сравнению с решениями Белаззоги и Хона и др. новая структура позволяет сократить потребление памяти вплоть до 2 битов на каждое состояние автомата, что очень существенно. Это наше теоретическое улучшение памяти разрешает открытый вопрос, поставленный Белаззоги в его статье 2010-го года. Более того, нам удалось теоретически обосновать, что при некоторых естественных ограничениях (а именно, если количество образцов константной длины невелико) дальнейшие продвижения в теоретическом улучшении потребления памяти в данной задаче в принципе невозможны и, таким образом, проблема в некотором смысле решена. Наша новая структура данных не только теоретически превосходит известные до неё варианты, но и является менее технически нагруженной, чем структура Хона и др. (хотя всё ещё очень нетривиальна), что позволило нам реализовать её и протестировать; в целях тестирования нами также разработана первая реализаций решения Белаззоги. Тесты подтвердили, что, как и предсказывалось теорией, потребление памяти в сжатых вариантах Ахо-Корасик на порядок (т.е. более чем в десять раз) меньше, чем в классическом несжатом варианте. Далее, в экспериментах было показано, что, действительно, наша новая структура данных превосходит по потребляемой памяти своих предшественников, но на практике на реальных данных может проигрывать по времени и по памяти некоторым теоретически неэффективным более простым (но всё ещё достаточно нетривиальным) решениям в случае, когда длины образцов не слишком велики. Тем не менее, в приложениях поиска достаточно длинных образцов в потоке данных (например, как в случае поиска фрагментов ДНК длины 100 и более) наша структура превосходит простые решения более чем в два раза по времени и не уступает по памяти. Мы надеемся, что наша реализация будет только одной из первых в ряду последующих улучшений практических сжатых вариантов автомата Ахо-Корасик, хотя, как уже упоминалось, она сама по себе может представлять практический интерес для приложений с длинными образцами.

Аннотация результатов, полученных в 2019 году
В рамках второго года реализации проекта получено два новых результата, перечисленных далее. (1) Задача сжатия данных является одной из старейших и наиболее изученных в компьютерных науках. Каждый пользователь регулярно сталкивается с архивами zip, 7z, rar и т.п., а также, даже не подозревая этого, сталкивается со сжатием в других форматах, как, например, png, pdf и другие. С относительно недавнего времени эта тема обогатилась областью разработки так называемых сжатых структур данных: целью таких структур является выполнение над сжатыми данными некоторых операций, например, чтения и поиска, без необходимости каждый раз выполнять разархивацию всего архива. Если в обыденных ситуациях подобное не всегда представляет интерес, то в областях, где обрабатываемые данные занимают сотни гигабайт, сжатие и обработка архивов без разархивации становятся жизненно необходимыми функциями. Приложения в биоинформатике, которые в особенности интересуют нас в данном проекте, являются типичной иллюстрацией такой ситуации. Обычный объект анализа биолога - это база данных геномов многих индивидов одного вида (скажем, для пример, коллекция из 10 тыс. геномов одного микроба). Эти геномы имеют поразительно много сходства между собой, что позволяет выполнять их сжатие специально заточенными методами. Одним из наиболее популярных таких методов является так называемое относительное разложение Лемпеля-Зива (Relative Lempel-Ziv) или, коротко, RLZ. Но на нужды современных коллекций геномов мощностей даже такого специального метода становится недостаточно, что вынуждает исследователей искать альтернативные более эффективные методы. В рамках проекта нами разработан новый метод сжатия таких коллекций, показывающий более эффективные, чем RLZ и ряд других методов, результаты на практике. Новый метод назван ReLZ (аббревиатура от Repeated Lempel-Ziv). В отличие от аналогичных альтернативных методов, предложенных другими исследователями для сжатия коллекций геномов, в проекте было выполнено строгое математическое обоснование эффективности метода ReLZ с помощью оценки размера кодируемых данных так называемой эмпирической энтропией k-го порядка. Оценка с помощью этой метрики неформально считается среди исследователей необходимым условием для любого приличного эффективного метода сжатия данных, чтобы считать его достойным рассмотрения в качестве хорошего общего метода сжатия, что позволяет считать ReLZ таковым. Существенно менее эффективный RLZ этой метрики не достигает и это является одним из объяснений, почему в практических приложениях RLZ перестал удовлетворять нуждам исследователей. Предполагается, что ReLZ может послужить основой для сжатых индексных структур на сжатых коллекциях геномов, как это произошло с RLZ. Но всё же полученный результат является более теоретическим, чем практическим, и больше служит продвижению в понимании природы наших современных представлений об оценке эффективности методов сжатия, чем развитию инженерных методов, применяющихся на практике (хотя ReLZ очень хорошо показал себя в экспериментах на больших объёмах данных). А именно, дело в том, что нами доказана оценка с помощью метрики эмпирической энтропии k-го порядка не только на ReLZ, но на целый очень широкий класс методов сжатия, производных от знаменитого метода Лемпеля-Зива. Этот результат можно интерпретировать как знак того, что для многих приложений возможно следует пересмотреть наши представления на энтропию k-го порядка, как на лучшую возможную метрику сжатия, и попытаться найти более адекватные метрики (хорошим кандидатом на такую новую метрику могут послужить совсем недавно изобретённые так называемые строковые аттракторы, но это требует дальнейших исследований). (2) В продолжение темы сжатия данных и сжатых индексов в проекте рассмотрена задача построения так называемых оптимальных кодов, в том числе известных в компьютерных науках кодов Хаффмана, но специального вида. Рассматриваемая задача является компонентой в более сложной структуре данных - в FM-индексе. Именно FM-индекс и его вариации, наряду с RLZ индексами, являются наиболее используемыми структурами для быстрого поиска и чтения сжатых данных без необходимости разархивации. FM-индексы, например, применяются в таких известных биоинформатикам инструментах, как Bowtie, BLAST, BWA и др. Одна из наиболее популярных вариаций FM-индекса использует в качестве ключевого компонента коды Хаффмана и, более общо, вообще произвольные оптимальные префиксные коды для заданных частот символов сжимаемых данных (эти коды используются довольно необычным образом - в качестве каркаса так называемого всплескового дерева, wavelet tree). Такие коды являются классическим объектом исследований в теории сжатия данных и до настоящего времени активно применяются во множестве архиваторов на практике. Для ускорения работы операций чтения сжатых данных в таком варианте индекса совсем недавно исследователями было предложено использовать префиксные коды специального вида - структуры на основе этих специальных кодов были названы оптимальными скелетными деревьями Хаффмана (определение этих структур несколько нетривиально, поэтому не приводится в данном коротком обзоре). Но все предложенные алгоритмы для построения этих деревьев до настоящего времени имели экспоненциальное время работы в худшем случае, что очень медленно. В рамках проекта нами разработан первый эффективные (квадратичный) алгоритм построения оптимального скелетного дерева Хаффмана по заданным частотам символов. (Справедливости ради, нужно отметить, что на практике для построения оптимальных скелетных деревьев Хаффмана могли использоваться достаточно эффективные эвристические алгоритмы, но в компьютерных науках всегда предпочтительнее иметь алгоритмы с гарантированным временем работы в арсенале средств).