автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Исследование и разработка методов и алгоритмов обработки символьных массивов в базах данных

004616645

учреждение российской академии наук институт проблем управления им. в.а. трапезникова ран

На правах рукописи

Айткулов Павел Григорьевич

Исследование и разработка методов и алгоритмов обработки символьных массивов в базах данных

Автореферат диссертации на соискание ученой степени кандидата технических наук

Специальность 05.13.11 - "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей".

-9 ДЕК 2010

Москва - 2010

004616645

Работа выполнена в ГОУ ВПО «Удмуртский государственный университет»

Научный руководитель: доктор физико-математических наук,

профессор Непейвода Николай Николаевич

Официальные оппоненты: доктор технических наук, доцент

Выхованец Валерий Святославович

доктор технических наук, профессор Сухомлин Владимир Александрович

Ведущая организация: ГОУ ВПО «Санкт-Петербургский

государственный университет»

Защита состоится Н^&й^) 2010 г. в И часов на заседании Диссертационного совета Д 002.226.03 Учреждения Российской академии наук Института проблем управления им. В.А. Трапезникова РАН по адресу: 117997, г. Москва, ул. Профсоюзная, 65.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Института проблем управления им. В.А. Трапезникова РАН.

Автореферат разослан

Ученый секретарь

Диссертационного совета Д 002.226.03

кандидат технических наук А. А. Кулинич

Общая характеристика работы.

Актуальность работы. Работа в текстовом редакторе, поисковые запросы в базе данных, задачи в биоинформатике, лексический анализ программ требуют эффективных алгоритмов работы со строками1.

Задачи поиска образца в тексте используются в криптографии, различных разделах физики, сжатии данных, распознавании речи.

В конце 1970-х годов на стыке генетики и информатики появилась биоинформатика (или вычислительная биология). Длина генотипа человека составляет 3,2 миллиарда символов (нуклеотидов). Для обработки таких больших данных требуются эффективные алгоритмы вычислений на строках.

Существует два основных подхода в алгоритмах поиска образца: преобразование образца и суффиксиые структуры данных.

В первом подходе образец является статичным, а исходный текст динамичен. Для каждого поискового запроса требуется прочитать исходный текст заново.

Если исходный текст является статичным, то стоит воспользоваться суф-фиксными структурами данных. Поисковый запрос к таким структурам требует линейных от длины образца ресурсов (количество операций и память).

К недостаткам существующих алгоритмов построения суффиксных структур данных относится то, что для построения структуры требуется вся строка целиком. Это ограничивает использование суффиксных структур данных с по-

работе рассматриваются классические вычисления. В квантовых вычислениях имеется алгоритм Гро-вера для быстрого поиска в неупорядоченной базе данных за 0(*/п). В классических вычислениях эффективность алгоритмов на строках означает время работы близкое к линейному.

токовыми данными. Малое изменение строки приведет к полной перестройке суффиксной структуры.

При использовании суффиксных структур данных для индексации текстовых записей в базах данных малое изменение (добавление, удаление или изменение одной записи) приводит к полной перестройке индекса.

Целью работы является построение эффективных алгоритмов изменения суффиксных структур данных (суффиксных массивов), построение приложений для индексации текстовых записей в базах данных. Эффективность подразумевает линейиые (близкие к линейным) затраты от длины изменившейся части строки.

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

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

Индексация строковых полей в базе данных и имен файлов в файловой си-

стеме применена на практике.

Построенные алгоритмы позволяют решать задачу о наибольшей общей подстроке для динамического случая для одной, двух и к строк. Были известны решения только для статического случая.

Построен алгоритм динамического поиска лексикографически наименьшего суффикса, лексикографически наименьшего циклического сдвига. Для поиска лексикографически наименьшего суффикса были известны потоковые решения, а для задачи лексикографически наименьшего циклического сдвига только решения для статического случая.

Построено приложение к архивации. Предлагается использовать потоковое построение суффиксных массивов для ¿^-факторизации. Построено приложение к технике «скользящего окна» (поддержка суффиксного массива только для последних символов потока).

Достоверность результатов обеспечивается строгостью доказательств и подтверждается практическими результатами реализованных алгоритмов.

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

ренней структуры данных для алгоритма потокового сжатия Лемпеля-Зива.

Реализация и внедрение результатов работы. Результаты исследования (потоковое построение суффиксных массивов) внедрены в практическую деятельность и используются в программных продуктах ОАО «НК Роснефть», что подтверждается актом о внедрении результатов диссертационной работы.

На защиту выносятся следующие основные результаты и положения:

1. Алгоритм последовательного построения суффиксного массива.

2. Алгоритм блочного построения суффиксного массива.

3. Алгоритм удаления подстроки из суффиксного массива.

4. Приложение для индексации текстовых записей в базах данных.

5. Алгоритм динамического поиска наибольшей общей подстроки для к строк.

6. Алгоритм динамического поиска лексикографически наименьшего суффикса, лексикографически наименьшего циклического сдвига.

7. Приложение к архивации; использование в технике «скользящего окна».

Апробация работы. Результаты работы докладывались и обсуждались на семинаре «Теоретические основы и приложения информатики» г. Ижевск, 2009 г.; VI всероссийской школе-семинаре молодых ученых «Управление большими системами» г. Ижевск, 2009 г.; семинаре в ИПУ РАН г. Москва 2010 г.; VII

всероссийской школе-семинаре молодых ученых «Управление большими системами» г. Пермь, 2010 г.;

Публикации результатов исследования. Основные результаты научных исследований по теме диссертации содержатся в 4 печатных работах, в том числе 2 - в изданиях, рекомендованных ВАК РФ.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. Объем работы составляет 97 страниц текста, включая 12 рисунков. Библиография включает 57 наименований.

Содержание работы

Во введении показывается актуальность темы, перечислены основные полученные результаты.

В первой главе даны базовые определения, обзор алгоритмов точного поиска образца в тексте, основанных на преобразовании образца, обзор суффиксных структур данных, обзор алгоритмов построения суффиксных массивов.

Рассмотрены следующие основные алгоритмы точного поиска, основанные на преобразовании образца:

• «наивный» алгоритм,

• поиск с использованием детерминированного конечного автомата,

• алгоритм Кнута-Морриса-Пратта,

• алгоритм Рабина-Карпа,

• алгоритм Бойера-Мура,

• ^-алгоритм,

• алгоритм Ахо-Корасик.

На данный момент существует порядка 40 алгоритмов точного поиска, основанных на преобразовании образца. В алгоритмах этого класса образец является статичным, а исходный текст динамичен. Для каждого поискового запроса требуется прочитать исходный текст заново. Если же текст является статичным, то имеет смысл использовать суффиксные структуры данных. При таком подходе необходимо однократно преобразовать исходный текст в суффиксную структуру данных. Поиск в суффиксной структуре данных требует линейных от длины образца временных затрат.

Проанализированы следующие суффиксные структуры данных:

• бор,

• суффиксный автомат,

• суффиксное дерево,

• суффиксный массив.

Основной недостаток существующих алгоритмов построения суффиксных структур состоит в том, что при малом изменении исходной строки необходимо заново перестроить суффиксную структуру данных.

В последующих главах построены алгоритмы модификации суффиксного массива при изменении исходной строки.

Определение.

Суффиксный массив строки - перестановка, выражающая лексикографический порядок суффиксов. Например, для строки "banana" суффиксный массив равен [6,4,2,1,5,3] (лексикографически упорядоченные суффиксы: "а", "ana", "anana", "banana", "па", "nana").

Поиск строки длины т в суффиксном массиве строки длины п осуществляется при помощи бинарного поиска за 0(т 1од(п)) (если использовать массив наибольшего общего префикса 1ср, то асимптотика уменьшается до 0(т + 1од(п))).

Элемент массива наибольшего префикса lepi выражает длину общего префикса между смежными суффиксами sa¡ и sai+x. Имеются линейные алгоритмы построения массива наибольшего общего префикса по суффиксному массиву.

Определение.

1ср-естественная строка - строка, для которой максимальное значение 1ср не превосходит некоторой константы. 1ср-регулярная строка - строка, для которой максимальное значение 1ср превышает некоторую константу 2 . Например, естественный язык является /ер-естественным, а строка "ааа..аа" является 1ср-регуляриой.

Во второп главе построены алгоритм последовательного построения суффиксного массива, алгоритм блочного построения суффиксного массива, алго-

2Константа определяет допустимый размер дублирования в тексте. Для естественных языков эта величина не превышает 50.

ритм удаления подстроки из суффиксного массива.

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

Сформулируем основные леммы.

Лемма о наихудшем случае.

При добавлении одного символа к строке может потребоваться 0(п) операций для изменения суффиксного массива.

Если строке "аа..а" приписать символ "6", то это приведет к обращению суффиксного массива. Это требует 0(п) операций.

Лемма о граничных суффиксах.

Пусть дан суффиксный массив за. При приписывании новой строки пя ко всем суффиксам суффиксного массива да, свое местоположение могут поменять только суффиксы, для которых выполнено 1ср{ = |даг|.

При добавлении нового символа имеет смысл обрабатывать только граничные суффиксы. При добавлении нового символа некоторые граничные суффиксы могут поменять свое местоположение, причем только «вниз».

Обработка одного граничного суффикса занимает 0(1од2(п)) операций. Сложность алгоритма составляет 0(п 1од2(п)) для /ср-регулярных строк, и 0(1од2(п)) для ¿ср-естественных строк.

Имеется возможность препроцессинга, то есть по строке и суффиксному массиву построить все необходимые структуры данных и продолжить построение суффиксного массива. Сложность препроцессинга составляет 0(п 1од(п)) операций.

Недостаток алгоритма последовательного построения суффиксного массива заключается в том, что для построения «с нуля» суффиксного массива для /ср-регулярных строк потребуется квадратичное время (на каждой итерации необходимо обрабатывать все граничные суффиксы).

Этот недостаток устраняется в алгоритме блочного построения суффиксного массива. Будем добавлять к суффиксному массиву строку, а не символ, как в предыдущем алгоритме. В качестве блока из потока выбирается минимальная подстрока, не входящая в текущий суффиксный массив. Показано, как обработать граничный суффикс за 0(1од2(п)) операций. Построение суффиксного массива «с нуля» требует 0(п 1од2(п)) операций.

Построен алгоритм удаления подстроки из суффиксного массива. Сложность алгоритма удаления подстроки размером к составляет 0(к 1од2(п)) операций для 1ср-естественных строк и 0(п 1од2(п)) для /ср-регулярных строк.

В третьей главе построены приложения для алгоритмов блочного построения суффиксного массива и удаления подстроки из суффиксного массива.

Алгоритм применен к индексации имен файлов в файловой системе и текстовых записей в базах данных. Суффиксный массив поддерживается для всех элементов, записанных в одну строку и разделенных метаданными. Такая строка

будет /ср-естественной. Операция изменения элемента соответствует удалению исходного элемента и добавлению в конец строки. Операции добавления и удаления элемента осуществляются алгоритмами блочного построения суффиксного массива и удаления подстроки из суффиксного массива.

Оценка количества операций - О (к 1од2(п)), где к - размер объекта.

Рассматривается задача о наибольшей общей подстроке.

Постановка задачи.

Дана строка. Найти два суффикса, общий префикс которых максимален.

Тривиальные решения требуют 0(п5) или 0(п3) операций и O(l) памяти. Решение динамическим программированием требует 0(п2) операций и 0(п2) памяти. Производя бинарный поиск по длине результата и применяя алгоритм Рабина-Карпа, получим решение с асимптотикой 0(п log(n)) операций и 0(п) памяти.

Рассматривается решение для статического случая с использованием суф-фиксных структур данных. Построив суффиксное дерево, необходимо найти внутреннюю вершину с наибольшей высотой. Путь от корня до вершины соответствует результату. Решение с использованием суффиксных деревьев требует 0(п) операций и 0(п) памяти.

Строится суффиксный массив, и далее массив наибольшего общего префикса 1ср. Решением является элемент суффиксного массива, значение 1ср которого максимально.

Строится решение для динамического случая.

Суффиксный массив находится при помощи алгоритмов блочного построения и удаления подстроки. При запросе необходимо найти максимальное значение в 1ср. Все значения lep хранятся в структуре данных для быстрого поиска максимума (двоичная куча) 1сртах. При изменении массива наибольшего общего префикса lep в процессе построения суффиксного массива модифицируется 1сртах, что не влияет на асимптотику алгоритма построения суффиксного массива. Тогда запрос о наибольшей общей подстроке производится за 0(1).

Далее задача обобщается на две строки.

Постановка задачи.

Дано две строки Si и S2■ Необходимо выделить в каждой строке по суффиксу так, чтобы их общий префикс был максимален.

Проанализированы статические решения. В решении с использованием суф-фиксных массивов необходимо построить суффиксный массив для строки si#s2, построить массив наибольшего общего префикса для объединенной строки и найти максимальное значение /ср;, так что i и i + 1 суффиксы принадлежат разным строкам si, $2-

Строится решение для динамического случая. В процессе построения суффиксного массива для объединенной строки Si#S2 поддерживаются значения lep в структуре данных для эффективного поиска максимума (только для тех суффиксов, у которых смежный суффикс принадлежит противоположной строке). Запрос на получение наибольшей общей подстроки для двух строк осуществляется за 0(1).

Задача обобщается па к строк.

Постановка задачи.

Дано к строк si,..., s^. Необходимо выделить в каждой строке по суффиксу так, чтобы их общий префикс был максимален.

Проанализированы статические решения. Тривиальное решение и решение с использованием динамического программирования не применимо на практике, так как требуется экспоненциальные время и память.

Решение с применением бинарного поиска и алгоритма Рабина-Карпа применимо и также требует 0(п login)) операций и линейных затрат по памяти. В решении с использованием суффиксных массивов необходимо построить суф-фиксный массив для объединенной строки Si#S2# •• •#«*:, построить массив наибольшего общего суффикса lep и найти отрезок, которому принадлежат все строки и значение минимума lep на этом отрезке максимально. Общий префикс на этом отрезке является решением.

Строится решение для динамического случая. Решение для динамического случая задачи наибольшей общей подстроки для к строк состоит в поддержании информации об интервалах, содержащих все строки, и значения lep на этих интервалах. Запрос выполняется за 0(1).

Задача о поиске наибольшей общей подстроки на практике используется для поиска плагиата, дублирования кода в больших программных проектах, поиска документов-дубликатов, в биоинформатике.

Далее рассматривается задача о лексикографически наименьшем суффиксе.

Постановка задачи.

Дана строка s. Трсбустся найти лексикографически наименьший суффикс.

Тривиальное решение (линейный проход по всем суффиксам и выбор минимума) требует 0(п2) операций и 0(1) памяти.

Определение.

Простая строка — строка, которая строго меньше любого своего собственного суффикса. Например, простыми строкам являются следующие: "a", "abc", "ababbb", a "abaa" и "bac" не являются простыми.

Определение.

Декомпозиция Лиидона строки s есть разложение s = Wivj¡ ■ ■ - Wk, где все строки w¡ простые и u»i ^ w¡ ^ ... ^ Wk.

Строим декомпозицию Линдона (алгоритм Дюваля) для строки s. Последняя простая строка в декомпозиции Линдона строки s будет лексикографически наименьшим суффиксом.

Построив суффиксный массив для строки, необходимо вернуть первое значение суффиксного массив sai.

Динамическое решение состоит в поддержании суффиксного массива. Запрос на получение лексикографически наименьшего суффикса просто возвращает первый элемент массива.

Перейдем к более сложной задаче: лексикографически наименьший циклический сдвиг.

Постановка задачи.

Пусть дано циклическое слово S = s[0..n — 1], в котором за каждым символом s, следует символ sI+i moij п. Необходимо выбрать позицию г для разрезания слова, так чтобы получившееся линейное слово S' = s,... sn_iSo ... было лексикографически минимальным среди всех таких линейных слов.

Лексикографически наименьший суффикс не является лексикографически наименьшим циклическим сдвигом (например для строки "baa" решениями являются "а" и "ааЬ" соответственно).

Проанализированы статические решения. Построим декомпозицию Линдо-на для строки S ++S. Лексикографически наименьшим циклическим сдвигом будет элемент разложения, который начинается в первой части строки, а заканчивается во второй.

Статическое решение с использованием суффиксных массивов аналогично. Построим суффиксный массив для удвоенной строки S ++S, в качестве ответа выдадим первый суффикс, начало которого принадлежит первой части строки.

Предлагается динамическое решение. Будем поддерживать суффиксный массив для строки S. При запросе лексикографически наименьшего циклического сдвига достраиваем (алгоритм блочного построения) суффиксный массив до удвоенной копии строки S++S. Для /ср-естественных строк сложность запроса составляет 0(1) операций, для ¿ср-регулярных - 0(п log2(n)).

Задача поиска лексикографически наименьшего циклического сдвига используется в химических базах данных.

Построенные алгоритмы применены для задачи архивирования.

Семейство алгоритмов Лемпеля-Зива работает следующим образом. Инициализируется пустой словарь. Далее из потока выбирается минимальная строка, не входящая в словарь. Тогда строка на единицу короче (назовем такую строку «родительской») уже содержится в словаре. Строка добавляется в словарь с дополнительными атрибутами (номер добавленной строки; идентификатор «родительской» строки). Строка кодируется парой: новый символ, идентификатор «родительской» строки.

Если в качестве словаря выбрать бор, то получим алгоритм Лемпеля-Зива-Велча, работающий в реальное время.

В качестве словаря предлагается использовать суффиксный массив. Блок кодируется тройкой: номер «родительского» суффикса, длина общего префикса с «родительским» суффиксом, новый символ.

На практике применяется техника «скользящего окна». Идея состоит в том, что бы поддерживать словарь только для п последних символов потока. Тогда для кодирования индекса потребуется константное число битов, то есть из суф-фиксного массива необходимо удалять самый длинный суффикс. Сложность алгоритма составляет 0(1од(п)) операций.

Рассмотрены возможности распараллеливания алгоритмов.

В Заключении сформулированы основные выводы и результаты, полученные в диссертационной работе.

1. Построены следующие алгоритмы и приложения:

• Алгоритм последовательного построения суффиксного массива. Изменение суффиксного массива при добавлении одного символа в конец исходной строки.

• Алгоритм блочного построения суффиксного массива. Изменение суффиксного массива при добавлении строки.

• Алгоритм удаления подстроки из суффиксного массива. Изменение суффиксного массива при удалении подстроки.

• Приложение к индексации текстовых записей в базах данных и имен файлов в файловой системе. Использование суффиксных массивов в качестве индекса для операций добавления, удаления и изменения объекта.

• Динамический поиск наибольшей общей подстроки для к строк. Позволяет искать дублирование в программных кодах, производить проверку на плагиат.

• Динамический поиск лексикографически наименьшего суффикса, лексикографически наименьшего циклического сдвига.

• Приложение к архивации, использование в технике «скользящего окна». Использование суффиксных массивов в качестве внутренней структуры данных для потокового алгоритма сжатия Лемпеля-Зива.

2. Доказаны асимптотические оценки для решенных задач.

Публикации по теме диссертации

1. Айткулов П. Г. Блочное построение суффиксного массива. Труды 6 Всероссийской школы-семинара молодых ученых. Управление большими системами. Том 1. Ижевск, 2009. С. 17-26.

2. Айткулов П. Г. Обработка символьных массивов / Управление большими системами. Выпуск 28. М.: ИПУ РАН, 2010. С. 126-178.

3. Айткулов П. Г. Динамический поиск лексикографически наименьшего суффикса и циклического сдвига / Труды 2 Всероссийской научно-практической конференции «Перспективы развития информационных технологий». Новосибирск, 2010. С. 10-12.

4. Айткулов П. Г. Приложение потокового построения суффиксных массивов к архивированию. // Материалы VII Всероссийской школы-конференции молодых ученых. Управление большими системами. Том 2. Пермь, 2010. С. 193-197.

Личный вклад. Все результаты получены диссертантом самостоятельно.

Отпечатано с оригинал-макета заказчика

Подписано в печать 08.11.10. Формат 60x84 '/,„. Тираж 100 экз. Заказ № 1815.

Типография ГОУВПО «Удмуртский государственный университет» 426034, Ижевск, ул. Университетская. I. корн. 4.

ВВЕДЕНИЕ

1 Обзор

1.1 Алгоритмы работы со строками

1.2 Обзор алгоритмов точного поиска преобразования образца

1.3 Обзор суффиксных структур данных.

1.4 Обзор алгоритмов построения суффиксных массивов

1.5 Аналогия с отсортированной коллекцией.

1.6 Замечание по используемым структурам данным.

1.7 Основные понятия.

1.8 Обзор алгоритмов по изменению суффиксных структур данных

1.9 О 1ср и поиске минимума на отрезке.

2 Разработка алгоритмов обработки символьных массивов

2.1 Алгоритм последовательного построения суффиксного массива

2.1.1 Оценка алгоритмической сложности и затрат памяти

2.1.2 Преимущества алгоритма и недостатки алгоритма

2.2 Алгоритм блочного построения суффиксного массива

2.2.1 Оценка алгоритмической сложности и затрат памяти

2.2.2 Выбор блока

2.2.3 Преимущества и недостатки алгоритма.

2.3 Удаление подстроки.

2.3.1 Оценка алгоритма.

Актуальность работы. Работа в текстовом редакторе, поисковые запросы в базе данных, задачи в биоинформатике, лексический анализ программ требуют эффективных алгоритмов работы со строками1.

Задачи поиска образца в тексте используются в криптографии, различных разделах физики, сжатии данных, распознавании речи.

В конце 1970-х годов на стыке генетики и информатики появилась биоинформатика (или вычислительная биология). Длина генотипа человека составляет 3,2 миллиарда символов (нуклеотидов). Для обработки таких больших данных требуются эффективные алгоритмы вычислений на строках.

Существует два основных подхода в алгоритмах точного поиска образца : преобразование образца и суффиксные структуры данных2.

В первом подходе образец является статичным, а исходный текст динамичен. Для каждого поискового запроса требуется прочитать исходный текст заново.

Если исходный текст является статичным, то стоит воспользоваться суф-фиксными структурами данных. Поисковый запрос к таким структурам требует линейных от длины образца ресурсов (количество операций и паработе рассматриваются классические вычисления. В квантовых вычислениях имеется алгоритм Гровера [28] для быстрого поиска в неупорядоченной базе данных за 0(\/п). В классических вычислениях эффективность алгоритмов на строках означает время работы близкое к линейному.

2В области неточного поиска используются другие меюды, например, на основе п-грамм [40]. мять).

К недостаткам существующих алгоритмов построения суффиксных структур данных относится то, что для построения структуры требуется вся строка целиком. Это ограничивает использование суффиксных структур данных с потоковыми данными. Малое изменение строки приведет к полной перестройке суффиксной структуры.

При использовании суффиксных структур данных для индексации текстовых записей в базах данных малое изменение (добавление, удаление или изменение одной записи) приводит к полной перестройке индекса.

Целью работы является построение эффективных алгоритмов изменения суффиксных структур данных (суффиксных массивов), построение приложений для индексации текстовых записей в базах данных. Эффективность подразумевает линейные (близкие к линейным) затраты от длины изменившейся части строки.

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

Научная новизна. В работе построены алгоритмы модификации такой суффиксной структуры данных, как суффиксный массив. Построены алгоритмы потокового построения суффиксного массива и удаления подстроки из суффиксного массива. В отличие от существующих алгоритмов, в процессе работы алгоритма поддерживается массив наибольшего общего префикса 1ср. Построен алгоритм препроцессинга (создание всех дополнительных структур данных на основе текущего суффиксного массива и строки).

Индексация строковых полей в базе данных и имен файлов в файловой системе применена на практике.

Построенные алгоритмы позволяют решать задачу о наибольшей общей подстроке для динамического случая для одной, двух и к строк. Были известны решения только для статического случая.

Построен алгоритм динамического поиска лексикографически наименьшего суффикса, лексикографически наименьшего циклического сдвига. Для поиска лексикографически наименьшего суффикса были известны потоковые решения, а для задачи лексикографически наименьшего циклического сдвига только решения для статического случая.

Построено приложение к архивации. Предлагается использовать потоковое построение суффиксных массивов для ¿^-факторизации. Построено приложение к технике «скользящего окна» (поддержка суффиксного массива только для последних символов потока).

Достоверность результатов обеспечивается строгостью доказательств и подтверждается практическими результатами реализованных алгоритмов.

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

Реализация и внедрение результатов работы. Результаты исследования (потоковое построение суффиксных массивов) внедрены в практическую деятельность и используются в программных продуктах ОАО «НК Роснефть», что подтверждается актом о внедрении результатов диссертационной работы.

На защиту выносятся следующие основные результаты и положения:

1. Алгоритм последовательного построения суффиксного массива.

2. Алгоритм блочного построения суффиксного массива.

3. Алгоритм удаления подстроки из суффиксного массива.

4. Приложение для индексации текстовых записей в базах данных.

5. Алгоритм динамического поиска наибольшей общей подстроки для к строк.

6. Алгоритм динамического поиска лексикографически наименьшего суффикса, лексикографически наименьшего циклического сдвига.

7. Приложение к архивации; использование в технике «скользящего окна».

Апробация работы. Результаты работы докладывались и обсуждались на семинаре «Теоретические основы и приложения информатики» г. Ижевск, 2009 г.; VI всероссийской школе-семинаре молодых ученых «Управление большими системами» г. Ижевск, 2009 г.; семинаре в ИПУ РАН г. Москва 2010 г.; VII всероссийской школе-семинаре молодых ученых «Управление большими системами» г. Пермь, 2010 г.;

Публикации результатов исследования. Основные результаты научных исследований по теме диссертации содержатся в 4 печатных работах [1, 2, 3, 4], в том числе 2 - в изданиях, рекомендованных ВАК РФ.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. Объем работы составляет 97 страниц текста, включая 12 рисунков. Библиография включает 57 наименований.

ЗАКЛЮЧЕНИЕ

В работе построены алгоритмы последовательного построения суффикс-ного массива, блочного построения суффиксиого массива, удаления блока из суффиксного массива.

В алгоритме последовательного построения суффиксного массива производится модификация суффиксного массива при добавлении одного символа к текущей строке. Асимптотика алгоритма составляет для 1ср-естественных языков 0(1од2(п)), для /ф-регулярных - 0{п1од2{п)). Последовательное добавление т символов для /ср-регулярных строк в худшем случае требует 0(т2 1од2(п)) операций.

В алгоритме блочного построения суффиксного массива производится модификация суффиксного массива при добавлении строки. Добавление строки размером т требует 0{гп1од2{п)) операций.

В алгоритме удаления блока из суффиксного массива производится модификация суффиксного массива при удалении подстроки. Удаление подстроки размером т требует 0(т1од2(п)) операций.

Во всех построенных алгоритмах затраты на память составляют 0(п).

Построенные алгоритмы позволяют работать с потоковыми данными.

В отличие от существующих алгоритмов, в процессе работы поддерживается массив наибольших префиксов 1ср, имеется возможность преироцес-спнга.

Построено практическое применение для индексации имен файлов в файловой системе и текстовых записей в базах данных.

В работе решена динамическая задача о наибольшей общей подстроки (для одной строки, для двух строк и общая задача для к строк). Были известны решения только для статического случая.

Решена динамическая задача поиска лексикографически наименьшего суффикса, лексикографически наименьшего циклического сдвига. Для поиска лексикографически наименьшего суффикса были известны потоковые решения, а для задачи лексикографически наименьшего циклического сдвига только решения для статического случая.

Построено приложение к архивации. Предлагается использовать потоковое построение суффиксных массивов к ¿^-факторизации. Построено приложение к технике «скользящего окна» (поддержка суффиксного массива только для последних символов потока).

1. Айткулов П. Г. Блочное построение суффиксного массива // Труды б Всероссийской школы-семинара молодых ученых. Управление большими системами. Том 1. Ижевск, 2009. С. 17-26.

2. Айткулов П. Г. Обработка символьных массивов // Управление большими системами. Выпуск 28. М.: ИПУ РАН, 2010. С. 126-178.

3. Айткулов П. Г. Динамический поиск лексикографически наименьшего суффикса и циклического сдвига // Труды 2 Всероссийской научно-практической конференции «Перспективы развития информационных технологий». Новосибирск, 2010. С. 10-12.

4. Айткулов П. Г. Приложение потокового построения суффикспых массивов к архивированию // Материалы VII Всероссийской школы-конференции молодых ученых. Управление большими системами. Том 2. Пермь, 2010. С. 193-197.

5. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

6. Вирт Н. Алгоритмы и структуры данных. СПб.: Невский диалект, 2008.

7. Гасфилд Д. Строки, деревья, последовательности в алгоритмах. -СПб.: Невский Диалект; БХВ-Петербург, 2003.

8. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003.

9. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.

10. Препарата Ф., Шеймос М. Вычислительная геометрия: введение. -М.: Мир, 1989.

11. Слисенко А. О. Нахождение в реальное время всех периодичностей в слове И Доклады АН СССР. 1980. - Т. 251. - С. 48-51.

12. Слисенко А. О. Поиск периодичностей и идентификация подслое в реальное время // Зап. научн. сем. ЛОМИ. 1981. - Т. 5. - С. 62-173.

13. Слисенко А. О. Распознавание предиката симметрии многоголовчатыми машинами Тьюринга со входом // Труды Мат. института АН СССР. 1973. - Т. 129. - С. 30-202.

14. Смит Б. Методы и алгоритмы вычислений на строках. Вильяме, 2006.

15. Aho A., Corasick М. Efficient string matching: an aid to bibliographic search // Communications of the ACM. 1975. - Vol. 18. - P. 333-340.

16. Appel A., Jacobsen G. The World's Fastest Scrabble Program // Communications of the ACM. 1988. -P. 572-578.

17. Baase S. Computer Algorithms. 2nd ed. Reading, MA: Addison-Wesley, 1988.

18. Boyer R. S., Moore J. S. A fast string searching algorithm // Comm. ACM. 1977. - Vol. 20. - R 762-772.

19. Charras C., Lecroq T. Handbook of Exact String-Matching Algorithms, 2004.

20. Duval J.-P. Factorizing words over an ordered alphabet // Journal Algorithms. 1983. -Vol. 4. - P. 363-381.

21. Farach M. Optimal suffix tree construction with large alphabets //In Proc. IEEE 38th Annual Symposium on Foundations of Computer Science. -1997. P. 137-143.

22. Farach M., Muthukrishnan S. Optimal logarithmic time randomized suffix tree construction //In Proc. IEEE 23th International Conference on Automata, Languages and Programming. 1996. - P. 550-561.

23. Farach M., Ferragina P., Muthukrishnan S. On the sorting-complexity of suffix tree construction // J. ACM. 2000. - Vol. 47(6). -P. 987-1011.

24. Ferragina P., Grossi R. Fast incremental text editing // Proceedings of the sixth annual ACM-SIAM Symposium on Discrete Algorithms. -1995. -P. 531-540.

25. Ferragina P., Fisher J. Suffix array on words // Combinatorial pattern matching: 18th annual symposium. -2007. -P. 328-339.

26. Gerlach W. Dynamic FM-Index for a collection of texts with application to space-efficient construction of the compressed suffix array, Master's thesis, Universität Bielefeld, Germany, 2007.

27. Gwehenberger G. Anwendung einer binaren Verweiskettenmethode beim Außau von Listen. Elektronische Rechenanlagen 1968. -Vol 10, -P. 223226

28. Grover L.K. A fast quantum mechanical algorithm for database search // Proceedings, 28th Annual ACM Symposium on the Theory of Computing. 1996. P. 212

29. Hubbard T.J. P., Lest A.M., Tramontane A. Gathering item into the fold // Nature Structural Biology. April, 1996. - Vol. 4. - P. 313.

30. Karkkainen J., Sanders P., Simple Linear Work Suffix Array Construction // Proceedings of the 30th International Colloquium on Automata, Languages and Programming, LNCS 2719, Springer, 2003. -P. 943-955.

31. Karkkainen J., Fast BWT in Small Space by Blockwise Suffix Sorting // Theoretical Computer Science, 2006.

32. Kasai T., Lee G., Arimura H., Arikawa S., Park K. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications // CPM. 2001. - P. 181-192.

33. Kitajima J. P., Navarro G., Ribeiro B., Ziviani N. Distributed Generation of Suffix Arrays: a Quicksort-Based Approach // Proceedings of the 4th South American Workshop on String Processing, Valparaiso, Chile, 1997. -P. 53-59.

34. Karp R., Rabin M. Efficient randomized pattern matching algorithms // IBM J. Res. Development. 1987. - Vol. 31. - P. 246-260.

35. Knuth D. E., Morris J. H., Pratt V. B. Fast pattern matching in strings // SIAM Journal on Computing. 1977. - Vol. 6. - P. 323-350.

36. Knuth D. E. The Art of Computer Programming, Volume 2: Sorting and Searching, Second Edition. Addison-Wesley, 1997.

37. Ko P., Aluru S., Space-efficient linear time construction of suffix arrays, Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching, 2003. - P. 200-210.

38. Larsson J. Extended application of suffix trees to data compression. Data Compression Conference. 1996.

39. Manber U., Mayers G. Suffix arrays: a new method for on-line string searches // SIAM Journal on Computing. 1993. - №22. - P. 953-948.

40. Manning C., Schutze H. Foundations of Statistical Natural Language Processing, MIT Press. 1999.

41. McCreight E. M. A Space-Economical Suffix Tree Construction Algorithm // Journal of the ACM. 1976. - Vol. 23(2). - P. 262-272.

42. Morrison D. PATRICIA-Practical Algorithm To Retrieve Information Coded in Alphanumeric // Journal of ACM. 1968. -Vol. 15(4). - P. 514534.

43. Navarro G., Kitajima J. P., Ribeiro B., Ziviani N., Distributed Generation of Suffix Arrays // Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, LNCS 1264. 1997. - P. 102-115.

44. Kim D. K, Sim J., Park H., Park K., Linear-time construction of suffix arrays // Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching, 2003 - P. 186-199.

45. Russo L., Navarro G., Oliveira A., Fully-compressed suffix trees // Proceedings of the 8th Latin American conference on Theoretical informatics, LNCS. 2008. -P. 362-373.

46. Rytter W. A correct preprocessing algorithm for Boyer-Moore string searching // SIAM J. Comput. 1980. - Vol. 9. - P. 509-512.

47. Salson M., Lecroq T. Leonard M., Mouchard L. Dynamic extended, suffix arrays // Journal of Discrete Algorithms. 2010. -Vol. 8. -P.241-257.

48. Salson M., Lecroq Т., Leonard M., Mouchard L. A ■Four-Stage Algorithm for Updating a Burrows- Wheeler Transform // Theoretical Computer Science, 2009.

49. Shibuya Т., Kurochkin I. Match chaining algorithm for cDNA Mapping // Algorithms in Bioinformatics: Third International Workshop, Budapest, WABI, 2003.

50. Ukkonen E. On-line construction of suffix trees // Algorithmica. 1995. - Vol. 14(3). - P. 249-260.

51. Weiner P. Linear pattern matching algorithm // 14th Annual IEEE Symposium on Switching and Automata Theory. 1973. - P. 1-11.

52. Welch T. A Technique for High Performance Data Compression // IEEE Computer. 1984. - Vol. 17 - P. 8-19.

53. Ziv J., Lempel A. A Universal Algorithm for Sequential Data Compression // IEEE Transactions on Information Theory. 1977. -Vol. 23(3). -P. 337-343.

54. Система ConQAT электронный ресурс] http: //conqat. cs. turn. edu/ index.php/ConQAT (дата обращения 13.08.2010).

55. Система Simian электронный ресурс] http: //www. redhillconsulting.com.au/products/simian/ (дата обращения 13.08.2010).

56. Система РМБ электронный ресурс] http://pmd.sourceforge.net/ (дата обращения 13.08.2010).

57. ТЭеагсЬ, индекс для полнотекснового поиска в Postgгes электронный ресурс] http://www.sai.msu.su/~megera/postgres/gist/ tsearch/V2/ (дата обращения 13.08.2010).