WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     || 2 |
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Лифшиц Юрий Михайлович АЛГОРИТМЫ И АНАЛИЗ ТРУДОЕМКОСТИ ОБРАБОТКИ СЖАТЫХ ТЕКСТОВ 05.13.17 Теоретические основы информатики А В Т О Р Е Ф Е Р А Т диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2007

Работа выполнена в лаборатории математической логики Санкт-Петербургского отделения Математического института им. В.А.Стеклова РАН

Научный консультант: член-корреспондент РАН, профессор Матиясевич Юрий Владимирович

Официальные оппоненты: доктор физико-математических наук, профессор Романовский Иосиф Владимирович кандидат физико-математических наук, Шень Александр Ханьевич

Ведущая организация: Вычислительный центр им. А.А. Дородницына Российской академии наук

Защита состоится “_” 2007 г. в _ часов на заседании диссертационного совета Д 212.232.51 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 28.

С диссертацией можно ознакомиться в научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан “_” 2007 г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук, профессор Мартыненко Б. К.

-2

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В последние пятнадцать лет много усилий было направленно на разработку такого представления данных, при котором, по возможности, одновременно минимизируются и размер, и время доступа. Одним из наиболее перспективным подходов к этой проблеме является построение алгоритмов поиска в сжатых текстах, которые бы не требовали полной распаковки исходного файла [3, 4, 7, 13, 16, 18]. Очень быстро от рассмотрения конкретных алгоритмов архивирования исследователи перешли к общей модели сжатого текста прямолинейной программе. Неформально, прямолинейная программа является грамматикой, которая порождает ровно один текст. Оказалось, что тексты, сжатые практическими архиваторами (например, LZ77 [22]), быстро и без значительного увеличения размера могут быть переведены в грамматику, описывающую тот же текст [21].

Опишем кратко наиболее важные результаты по обработке текстов, представленных в виде прямолинейных программ. Задача о равенстве двух сжатых текстов впервые была решена в работе [19] в 1994 году. Была доказана оценка O(n4) на время работы этого алгоритма, где n равно сумме размеров прямолинейных программ, порождающих два сравниваемых текста. Алгоритм для поиска сжатой подстроки в сжатом тексте впервые появился в 1995 году в статье [14]. Вслед за этим удалось расширить алгоритм для вычисления различных комбинаторных свойств текста [9]. Далее, в 1997 году Миязаки, Шинохара и Такеда [17] построили алгоритм, требующий O(n2m2) времени для поиска подстрок, где m и n размеры сжатого шаблона и сжатого текста, соответственно.

В то же время, ряд классических текстовых задач до сих пор не был решен в постановке со сжатым представлением входных данных. В частности, не было предложено ни одного алгоритма поиска подпоследовательностей напрямую в сжатом тексте. Определение вложимости сжатого шаблона в сжатый текст могло оказаться как решаемым за полиномиальное -3время, так и PSPACE-полной задачей. Также, оставалась неизвестной сложность вычисления расстояния Хэмминга между сжатыми текстами. Этот вопрос является самой простой формой приближенного поиска подстрок, который полезен для анализа как биологических данных, так и медиафайлов. Кроме того, вычисление расстояния Хэмминга между сжатыми текстами является естественным продолжением задачи о равенстве сжатых текстов.

Алгоритмы на сжатых текстах имеют прямое отношение к ряду других задач теоретической информатики. Так, с их помощью впервые удалось построить полиномиальный по памяти алгоритм решения уравнений в словах [20], a также полиномиальный алгоритм верификации диаграмм сообщений [10].

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

Цели работы. Диссертационное исследование было направлено на решение следующих основных задач:

1. Построить новые алгоритмы для сравнения сжатых текстов, поиска сжатых шаблонов в сжатых текстах, вычисления периодов сжатых текстов. Упростить алгоритмы, представленные в работах [9, 12, 14, 17, 19] и/или уменьшить верхние оценки на время их работы.

2. Определить существование полиномиальных алгоритмов для следующих задач: вложимость явно заданного шаблона в сжатый текст, вложимость сжатого шаблона в сжатых текст, вычисление расстоя-4ния Хэмминга между сжатыми текстами, вычисление минимального накрытия сжатого текста.

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

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

Основные результаты.

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

2. Доказана #P-полнота задачи о вычислении расстояния Хэмминга между сжатыми текстами, NP- и coNP-трудность задачи о поиске сжатой подпоследовательности в сжатом тексте.

3. Предложено понятие разреженной периодичности. Найдено соотношение примитивного классического и примитивного разреженного периодов.

4. Разработан алгоритм поиска разреженных периодов минимального размера.

Научная новизна. Все основные результаты являются новыми.

Практическая и теоретическая ценность. Представленные алгоритмы для проверки равенства сжатых текстов и поиска сжатых подстрок в сжатых текстах могут быть полезны для проверки эквивалентности программ в рамках модели, предложенной в работе [15]. Описание текстов с -5помощью их разреженных периодов может быть использовано для обобщения ряда классических методов архивирования, таких как кодирование длин серий (RLE). Доказательство трудности вычисления расстояния Хэмминга между сжатыми текстами показывает границы применимости алгоритмов для обработки текстов, представленных в виде прямолинейных программ. Фактически, можно сделать вывод, что для эффективного приближенного сравнения сжатых текстов нужна другая модель компактного хранения.

Апробация работы. Основные результаты обсуждались на следующих конференциях и семинарах:

• Международный симпозиум Mathematical Foundations of Computer Science, Словакия, 2006.

• Международный симпозиум Computer Science in Russia, СанктПетербург, 2006.

• Школа-семинар “Синтез и сложность управляющих схем”, СанктПетербург, 2006.

• Школа-семинар в Дагштуле “Combinatorial and Algorithmic Foundations of Pattern and Association Discovery”, Германия, май 2006.

• Русско-французская конференция молодых ученых, Москва, • Научные семинары ПОМИ РАН, СПИИРАН, МГУ, ИППИ РАН, университетов Таллина и Турку.

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

Публикации. Основные результаты диссертации опубликованы в пяти работах [23, 24, 25, 26, 27], перечисленных в конце автореферата.

-6Работы [23, 24] опубликованы в издании, входившем в перечень ВАК на момент публикации.

Структура и объем работы. Диссертация объемом 82 страницы состоит из введения и четырех основных глав, разбитых на разделы и подразделы. Список цитируемой литературы состоит из 47 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Определение. Прямолинейной программой называется контекстносвободная грамматика P, в которой нетерминальные символы X1,..., Xm упорядочены (Xm стартовый символ), и где у каждого нетерминального символа есть только одно правило: Xi a, где a терминал, или Xi XjXk для некоторых j, k < i.

Третья глава посвящена построению алгоритмов для следующих трех задач:

1. Даны два сжатых текста, представленные в виде прямолинейных программ. Определить, совпадают ли исходные тексты.

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

3. Дан шаблон (явно заданный) и сжатый текст. Определить, образуют ли буквы шаблона подпоследовательность в тексте. Другими словами, можно ли вычеркнуть часть букв в тексте так, чтобы остался шаблон -7В разделе 3.1 этой работы приводится новый алгоритм, который решает задачу о поиске подстрок за O(n2m) шагов. Применение этого алгоритма к задаче о равенстве приводит к оценке O(n3) на время работы. Таким образом, улучшены результаты всех предыдущих работ по этим двум задачам [12, 17, 14, 19, 9].

В разделе 3.2 алгоритмическая техника, использованная для решения задачи о поиске подстроки, применяется к вычислению длин минимального периода и минимального накрытия сжатого текста.

Далее, в разделе 3.3 приводится алгоритм, который определяет вложимость шаблона в текст. Этот алгоритм также выдает количество минимальных подстрок и количество подстрок определенной длины, в которые вкладывается шаблон. Трудоемкость алгоритма равна O(mk2 log k), где k длина шаблона, а m размер прямолинейной программы, порождающей текст. Таким образом, время работы линейно относительно размера сжатого текста.

Четвертая глава посвящена доказательству вычислительной трудности следующих двух задач:

1. Дано два сжатых текста одинаковой длины. Определить количество несовпадающих символов (расстояние Хэмминга) между ними.

2. Дано два сжатых текста. Определить, является ли один текст подпоследовательностью второго.

В разделе 4.1 доказана следующая теорема.

Теорема 4.1.1. Задача о вычислении расстояния Хэмминга между сжатыми текстами является #P-полной.

Напомним, что #P это класс функций, своеобразное расширение класса предикатов NP. Далее, в разделе 4.2 доказаны две теоремы о трудности поиска сжатой подпоследовательности в сжатом тексте (задача определения вложимости).

-8Теорема 4.2.1. Задача определения вложимости сжатого шаблона в сжатый текст является NP-трудной.

Теорема 4.2.2. Определение вложимости сводится (по Карпу) к определению невложимости. Определение невложимости сводится к определению вложимости.

Утверждение теоремы можно переформулировать следующим образом. Для каждой пары прямолинейных программ F и G можно быстро построить такую пару программ F и G, что текст, порожденный F, вкладывается в текст, порожденный G, тогда и только тогда, когда текст, по рожденный F, не вкладывается в текст, порожденный G. Таким образом, задача вложимости лежит вне класса NP(при предположении NP =coNP).

Последний результат оказался большой неожиданностью, так как по своей природе постановка задачи очень напоминает представителей класса NP.

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

k Слово S называется чисто периодическим, если S = W = W... W.

Другими словами, чистая периодичность соответствует делимости p|n и равенству si = si+p для всех 1 i < i + p n.

Два слова на иллюстрации внизу не являются чисто периодическими. Однако, они обладают некоторой структурной закономерностью. Так, в соответствии с введенным в диссертации новым обобщенным понятием периодичности эти строки становятся периодическими.

A A B B A A B B A A B B C C D D C C D D -9Частично определенное слово это слово в алфавите { }, где это специальная прозрачная (или неопределенная) буква [2, 5, 6]. Другими словами, частично определенное слово представляет собой последовательность обычных слов (блоков), разделенных пропусками фиксированной (но необязательно одинаковой) длины.

Частично определенное слово S называется разреженным периодом (обычного) слова T, если T можно разделить на одну или несколько параллельно сдвинутых копий S, которые будут удовлетворять следующим условиям:

• Все определенные (видимые) буквы S-копий совпадают с соответствующими буквами в тексте;

• Каждая буква текста покрыта в точности одной определенной (видимой) буквой из S-копий.

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

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

Pages:     || 2 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.