Введение к работе
Актуальность работы. Работа в текстовом редакторе, поисковые запросы в базе данных, задачи в биоинформатике, лексический анализ программ требуют эффективных алгоритмов работы со строками1.
Задачи поиска образца в тексте используются в криптографии, различных разделах физики, сжатии данных, распознавании речи.
В конце 1970-х годов на стыке генетики и информатики появилась биоинформатика (или вычислительная биология). Длина генотипа человека составляет 3,2 миллиарда символов (нуклеотидов). Для обработки таких больших данных требуются эффективные алгоритмы вычислений на строках.
Существует два основных подхода в алгоритмах поиска образца: преобразование образца и суффиксные структуры данных.
В первом подходе образец является статичным, а исходный текст динамичен. Для каждого поискового запроса требуется прочитать исходный текст заново.
Если исходный текст является статичным, то стоит воспользоваться суф-фиксными структурами данных. Поисковый запрос к таким структурам требует линейных от длины образца ресурсов (количество операций и память).
К недостаткам существующих алгоритмов построения суффиксных структур данных относится то, что для построения структуры требуется вся строка целиком. Это ограничивает использование суффиксных структур данных с по-
В работе рассматриваются классические вычисления. В квантовых вычислениях имеется алгоритм Гро-вера для быстрого поиска в неупорядоченной базе данных за 0(*/п). В классических вычислениях эффективность алгоритмов на строках означает время работы близкое к линейному.
токовыми данными. Малое изменение строки приведет к полной перестройке суффиксной структуры.
При использовании суффиксных структур данных для индексации текстовых записей в базах данных малое изменение (добавление, удаление или изменение одной записи) приводит к полной перестройке индекса.
Целью работы является построение эффективных алгоритмов изменения суффиксных структур данных (суффиксных массивов), построение приложений для индексации текстовых записей в базах данных. Эффективность подразумевает линейные (близкие к линейным) затраты от длины изменившейся части строки.
Методы исследования. В работе применяются методы теории алгоритмов и сложности, амортизационного анализа, алгебры, динамического программирования. Используются алгоритмы и структуры данных из таких областей, как теория автоматов, теория графов, строковые алгоритмы.
Научная новизна. В работе построены алгоритмы модификации такой суффиксной структуры данных, как суффиксный массив. Построены алгоритмы потокового построения суффиксного массива и удаления подстроки из суф-фиксного массива. В отличие от существующих алгоритмов, в процессе работы алгоритма поддерживается массив наибольшего общего префикса 1ср. Построен алгоритм препроцессинга (создание всех дополнительных структур данных на основе текущего суффиксного массива и строки).
Индексация строковых полей в базе данных и имен файлов в файловой си-
стеме применена на практике.
Построенные алгоритмы позволяют решать задачу о наибольшей общей подстроке для динамического случая для одной, двух и к строк. Были известны решения только для статического случая.
Построен алгоритм динамического поиска лексикографически наименьшего суффикса, лексикографически наименьшего циклического сдвига. Для поиска лексикографически наименьшего суффикса были известны потоковые решения, а для задачи лексикографически наименьшего циклического сдвига только решения для статического случая.
Построено приложение к архивации. Предлагается использовать потоковое построение суффиксных массивов для L-Z-факторизации. Построено приложение к технике «скользящего окна» (поддержка суффиксного массива только для последних символов потока).
Достоверность результатов обеспечивается строгостью доказательств и подтверждается практическими результатами реализованных алгоритмов.
Практическая и теоретическая ценность. Результаты, полученные в диссертационной работе, позволяют динамически изменять суффиксные массивы, индексировать текстовые записи в базах данных и имен файлов в файловой системе (добавление, удаление и изменение объекта). Решен класс динамических задач (динамическая задача о наибольшей общей подстроке, лексикографически наименьший суффикс, циклический сдвиг). Построено приложение к архивации: предлагается использовать суффиксные массивы в качестве внут-
ренней структуры данных для алгоритма потокового сжатия Лемпеля-Зива.
Реализация и внедрение результатов работы. Результаты исследования (потоковое построение суффиксных массивов) внедрены в практическую деятельность и используются в программных продуктах ОАО «НК Роснефть», что подтверждается актом о внедрении результатов диссертационной работы.
На защиту выносятся следующие основные результаты и положения:
-
Алгоритм последовательного построения суффиксного массива.
-
Алгоритм блочного построения суффиксного массива.
-
Алгоритм удаления подстроки из суффиксного массива.
-
Приложение для индексации текстовых записей в базах данных.
-
Алгоритм динамического поиска наибольшей общей подстроки для к строк.
-
Алгоритм динамического поиска лексикографически наименьшего суффикса, лексикографически наименьшего циклического сдвига.
-
Приложение к архивации; использование в технике «скользящего окна».
Апробация работы. Результаты работы докладывались и обсуждались на семинаре «Теоретические основы и приложения информатики» г. Ижевск, 2009 г.; VI всероссийской школе-семинаре молодых ученых «Управление большими системами» г. Ижевск, 2009 г.; семинаре в ИПУ РАН г. Москва 2010 г.; VII
всероссийской школе-семинаре молодых ученых «Управление большими системами» г. Пермь, 2010 г.;
Публикации результатов исследования. Основные результаты научных исследований по теме диссертации содержатся в 4 печатных работах, в том числе 2 - в изданиях, рекомендованных ВАК РФ.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. Объем работы составляет 97 страниц текста, включая 12 рисунков. Библиография включает 57 наименований.
