Алгоритмы и анализ трудоемкости обработки сжатых текстов

• Автор: Лифшиц, Юрий Михайлович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Санкт-Петербург
• Количество страниц: 82 с.

Оглавление
1 Введение

1.1 Алгоритмы на сжатых текстах.

1.1.1 Постановка решаемых задач

1.1.2 Результаты

1.2 Нижние оценки трудоемкости обработки сжатых текстов .

1.3 Новый подход к архивированию разреженная периодичность .

1.3.1 Основное понятие

1.3.2 Рассматриваемые вопросы. И

1.3.3 Результаты.

1.4 Обзор литературы.

1.4.1 Исследования по алгоритмам обработки сжатых текстов
1.4.2 Исследования по периодичности текстов и по обобщениям этого понятия.
1.5 Структура работы.
2 Грамматика как модель сжатого текста
3 Алгоритмы обработки сжатых текстов
3.1 Поиск сжатой подстроки в сжатом тексте.
3.1.1 Поиск подстрок с помощью таблицы прогрессий . .
3.1.2 Вычисление таблицы прогрессий.
3.1.3 Процедура локального поиска.
3.1.4 Обсуждение алгоритма
3.2 Алгоритм вычисления периодов и накрытий
3.3 Алгоритм поиска оконных подпоследовательностей
3.3.1 Вспомогательные структуры данных.
3.3.2 Вычисление вспомогательных структур данных . .
3.3.3 Итоговый алгоритм и его трудоемкость.
3.4 Выводы и открытые вопросы
4 Нижние оценки на трудоемкость обработки сжатых текстов
4.1 Расстояние Хэмминга между сжатыми текстами.
4.2 Сжатые подпоследовательности в сжатых текстах
4.2.1 ЫРтрудность
4.2.2 аМРтрудность.
4.3 Выводы и открытые вопросы
5 Разреженная периодичность
5.1 Примитивный разреженный период не единственен
5.2 Свойства разреженной периодичности.
5.2.1 Количество разреженных периодов.
5.2.2 Соотношение между разреженными и классическими периодами
5.2.3 Алгоритм поиска разреженных периодов минимального размера.
5.3 Выводы и открытые вопросы.
Литература


Я посвящаю эту работу своим замечательным родителям — Михаилу Анатольевичу Лифшицу и Надежде Алексеевне Комаровой. Я благодарю своего научного руководителя Юрия Владимировича Матиясевича за постоянное внимание, поддержку и конструктивную критику моих исследований. Мои соавторы Ирен Гессарян, Юхани Карью-мяки, Маркус Лори, Патрик Сигельски знакомили меня с интересными открытыми проблемами и были самыми первыми критиками полученных мной результатов. Многочисленные читатели черновых версий этой работы Михаил Брудно, Николай Гравин, Михаил Дворкин, Вадим Джанмухамедов, Алексей Ильин. Шунсуке Иненага, Арисг Кожевников, Александр Кузнецов, Денис Кулагин, Иван Лагунов, Свен Лаур, Илья Миронов. Александр Охотин, Надежда Поликарпова, Юрий Притыкин, Матье Раффино, Войцех Риттер, Анатолий Федуков, Алексей Хворост, Арсений Шур прислали много важных замечаний и комментариев. Наконец, весь коллектив лаборатории математической логики ПОМИ РАН создавал замечательную научную атмосферу, в которой было легко и приятно работать. Федерального агентства по науке и инновациям № . Ведущие научные школы” НШ-1 и НШ-1, а также специальными программами компаний ntel и Яндекс. Алгоритмы на сжатых текстах. Нижние оценки трудоемкости обработки сжатых текстов . Новый подход к архивированию: разреженная периодичность . Рассматриваемые вопросы. Результаты. Обзор литературы. Исследования по периодичности текстов и по обобщениям этого понятия. Структура работы. Поиск сжатой подстроки в сжатом тексте. Поиск подстрок с помощью таблицы прогрессий . Вычисление таблицы прогрессий. Процедура локального поиска. Вспомогательные структуры данных. Вычисление вспомогательных структур данных . Итоговый алгоритм и его трудоемкость. Расстояние Хэмминга между сжатыми текстами. МР-трудность. Свойства разреженной периодичности. Количество разреженных периодов. Алгоритм поиска разреженных периодов минимального размера. Выводы и открытые вопросы.