КАРТОЧКА ПРОЕКТА,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

 

ОБЩИЕ СВЕДЕНИЯ


Номер 18-71-00002

НазваниеСжатые структуры данных

РуководительКосолобов Дмитрий Александрович, Кандидат физико-математических наук

Организация финансирования, регионфедеральное государственное автономное образовательное учреждение высшего образования "Уральский федеральный университет имени первого Президента России Б.Н. Ельцина", Свердловская обл

Срок выполнения при поддержке РНФ 07.2018 - 06.2020 

КонкурсКонкурс 2018 года по мероприятию «Проведение инициативных исследований молодыми учеными» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах, 01-715 - Системы текстового поиска

Ключевые словасжатые структуры данных, сжатые индексы, сжатие данных, разложение Лемпеля-Зива

Код ГРНТИ20.23.00


СтатусУспешно завершен


 

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ


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

Ожидаемые результаты
Предполагается разработать ряд новых сжатых индексов, основанных на широко известном в данной области разложении Лемпеля-Зива, и описать новые алгоритмы инкрементного построения таких индексов (таким образом, поддерживая вставку кусков данных в конец уже обработанных и индексированных данных). Особенностью разработанного индекса будет гарантированно быстрый поиск шаблонов (субквадратичный, в отличие от большинства существующих индексов, основанных на разложении Лемпеля-Зива). Особенностью алгоритма построения индекса будет низкое потребление памяти. В настоящее время чувствуется недостаток в таких алгоритмах и сжатых индексах для, например, коллекций геномных данных: такие данные из-за их размера невозможно приемлемо сжимать существующими методами, потребляющими слишком большой объем памяти. Также ожидается, что полученные алгоритмы найдут применение в других более широких областях, связанных с хранением, доступом и редактированием коллекций из систем контроля версий, журналов работы приложений, текстовых коллекций социальных сетей и т.д.


 

ОТЧЁТНЫЕ МАТЕРИАЛЫ


Аннотация результатов, полученных в 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 и более) наша структура превосходит простые решения более чем в два раза по времени и не уступает по памяти. Мы надеемся, что наша реализация будет только одной из первых в ряду последующих улучшений практических сжатых вариантов автомата Ахо-Корасик, хотя, как уже упоминалось, она сама по себе может представлять практический интерес для приложений с длинными образцами.

 

Публикации

1. Косолобов Д.А., Сивухин Н.С. Compressed multiple pattern matching 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), - (год публикации - 2019).


Аннотация результатов, полученных в 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). Такие коды являются классическим объектом исследований в теории сжатия данных и до настоящего времени активно применяются во множестве архиваторов на практике. Для ускорения работы операций чтения сжатых данных в таком варианте индекса совсем недавно исследователями было предложено использовать префиксные коды специального вида - структуры на основе этих специальных кодов были названы оптимальными скелетными деревьями Хаффмана (определение этих структур несколько нетривиально, поэтому не приводится в данном коротком обзоре). Но все предложенные алгоритмы для построения этих деревьев до настоящего времени имели экспоненциальное время работы в худшем случае, что очень медленно. В рамках проекта нами разработан первый эффективные (квадратичный) алгоритм построения оптимального скелетного дерева Хаффмана по заданным частотам символов. (Справедливости ради, нужно отметить, что на практике для построения оптимальных скелетных деревьев Хаффмана могли использоваться достаточно эффективные эвристические алгоритмы, но в компьютерных науках всегда предпочтительнее иметь алгоритмы с гарантированным временем работы в арсенале средств).

 

Публикации

1. Косолобов Д.А., Валензуела Д., Наварро Г., Пуглизи С.Дж. Lempel-Ziv-like parsing in small space Algorithmica, Springer, - (год публикации - 2020).

2. Косолобов Д.А., Меркурьев О.А. Optimal skeleton Huffman trees revisited Lecture Notes in Computer Science, 15th International Computer Science Symposium in Russia (CSR 2020), Springer, - (год публикации - 2020).

3. Косолобов Д.А., Сивухин Н.С. Compressed multiple pattern matching Leibniz International Proceedings in Informatics (LIPIcs), 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), vol. 128, pp. 13:1 - 13:14 (год публикации - 2019).