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

Оглавление
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 Выводы и открытые вопросы.
Литература