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

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

Автор: Лифшиц, Юрий Михайлович

Количество страниц: 82 с.

Артикул: 3320838

Автор: Лифшиц, Юрий Михайлович

Шифр специальности: 05.13.17

Научная степень: Кандидатская

Год защиты: 2007

Место защиты: Санкт-Петербург

Стоимость: 250 руб.

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

Оглавление
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 и Яндекс. Алгоритмы на сжатых текстах. Нижние оценки трудоемкости обработки сжатых текстов . Новый подход к архивированию: разреженная периодичность . Рассматриваемые вопросы. Результаты. Обзор литературы. Исследования по периодичности текстов и по обобщениям этого понятия. Структура работы. Поиск сжатой подстроки в сжатом тексте. Поиск подстрок с помощью таблицы прогрессий . Вычисление таблицы прогрессий. Процедура локального поиска. Вспомогательные структуры данных. Вычисление вспомогательных структур данных . Итоговый алгоритм и его трудоемкость. Расстояние Хэмминга между сжатыми текстами. МР-трудность. Свойства разреженной периодичности. Количество разреженных периодов. Алгоритм поиска разреженных периодов минимального размера. Выводы и открытые вопросы.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.224, запросов: 244