Разработка эффективных алгоритмов поиска слов в текстах для построения методов сжатия данных

• Автор: Бах, Ольга Анатольевна
• Шифр специальности: 05.13.13
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Новосибирск
• Количество страниц: 214 с.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
Глава1 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ КОДИРОВАНИЯ И ТЕОРИИ АЛГОРИТМОВ, ИСПОЛЬЗУЕМЫЕ В ДИССЕРТАЦИИ
1Л Введение

1.2 Задача поиска слов в тексте и методы ее решения

1.2.1 Основные понятия

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

1.2.3 Обзор алгоритмов поиска

1.2.4 Алгоритм Кнута - Морриса - Пратта

1.2.5 Алгоритм Бойера - Мура и его модификации

1.3 Сжатие данных

1.3.1 Общая характеристика проблемы и основные понятия
1.3.2 Алгоритмы сжатия данных
1.3.3 Влияние способов кодирования на эффективность сжатия
1.3.4 Сжатие данных и прогнозирование
1.4 Приложение методов поиска к задаче сжатия генетических текстов
1.4.1 Необходимость создания компьютерных технологий
для обработки генетических баз данных
1.4.2 Основные понятия биоинформатики и постановка задачи
Выводы

Глава 2 АЛГОРИТМЫ ИДЕНТИФИКАЦИИ ПОДСЛОВ
2Л Введение
2.2 Алгоритм "максимальногорасстояния"
2.2.1 Основная идея алгоритма
2.2.2 Подробное описание алгоритма "максимального расстояния"
2.2.3 Пример поиска с применением построенного алгоритма "максимального расстояния"
2.2.4 Ускоренный алгоритм "максимального расстояния"
2.3 Алгоритм "быстрого сдвига"
2.3.1 Основная идея алгоритма
2.3.2 Подробное описание алгоритма "быстрого сдвига"
2.3.3 Пример поиска с применением построенного алгоритма "быстрого сдвига"
2.3.4 Ускоренный алгоритм "быстрого сдвига"
2.4 Экспериментальное сравнение построенных алгоритмов поиска с ранее известными алгоритмами
Выводы
Глава 3 ВЫБОР КОДОВЫХ МНОЖЕСТВ ДЛЯ НОВОЙ
ВЕРСИИ АЛГОРИТМА ЛЕМПЕЛА - ЗИВА
3.1 Введение
3.2 Модифицированный метод Лемпела - Зива и его сравнение
3.2.1 Описание метода и пример кодирования
с его использованием
3.2.2 Экспериментальное сравнение методов сжатия
3.3 Сравнительный анализ кодовых множеств
3.3.1 Описание кодовых множеств для кодирования целых чисел
3.3.2 Экспериментальное сравнение кодовых множеств и выбор наилучших для использования в методе сжатия
3.3.3 Статистическое кодирование
Выводы
Глава 4 ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ ПОИСКА И МЕТОДА ПРОГНОЗА ДЛЯ РЕШЕНИЯ НЕКОТОРЫХ ЗАДА Ч СЖА ТИЯ ДАННЫХ
4.1 Введение
4.2 Алгоритм определения типа данных, основанный на методе прогноза, и его применение к задаче
анализа генетических текстов
4.2.1 Общее описание метода прогноза
4.2.2 Особенности реализации алгоритма
определения типа данных
4.2.3 Пример работы алгоритма
4.3 Распознавание границ
между данными различной структуры
4.4 Экспериментальные расчеты
4.4.1 Исследование метода прогноза на тестовых данных
4.4.2 Подготовка генетических данных для обработки
4.4.3 Идентификация фрагмента текста по его типу

сдвига слова при несовпадениях:
текст аЬ а Ь а Ь <1 Ьа Ьа Ь с % са Ь а Ь с а Ь а количество сравнений величина сдвига слова
слово а .Ь и Ъ с а Ь а}. 1 я —8іСЬ') =
2 а Ь а Ь с а_Ьа 3 8 = 62(б) •
3 abab с а й)а 2 8 = 52(7) =
4 и Ь а Ъ.са Ъ а 5 8 = 82(4) =
5 а Ь а Ь с а Ъ а 8 слово найдено!
Рис. 1.14 Поиск слова в тексте - алгоритм Бойера - Мура
Сравнения после каждого сдвига слова продолжаются от конца слова к его началу, при первом несовпадении (т.е. если не совпал последний символ слова) величина сдвига слова определяется по таблице 81(1ь+„^, где іь+,„ - это символ текста. Если несовпадение обнаружилось где-то в позиции слова с номером і, где 1 <і<т, то для определения величины сдвига используем таблицу 82(1)- В рассмотренном примере количество сравнений при поиске слова в тексте получилось равным 19, что заметно меньше, чем требовалось при использовании предыдущего алгоритма. Заметим, что вхождение слова в текст найдено за количество операций сравнения, меньшее длины текста.
В ситуации, когда в сообщении встречается много таких символов, которых нет в искомом слове (что характерно при большом алфавите), велика вероятность того, что после очередного смещения слова вправо его последнему символу будет в тексте соответствовать отсутствующий в слове символ. В таком случае смещение образа произойдет сразу на всю его длину. При частом повторении такой ситуации и достигается наилучшая оценка С п/т.
Таким образом, алгоритм Бойера - Мура является самым эффективным при решении задачи идентификации цепочек в случае алфавита большого объема и при поиске длинных строк. Поэтому его идеи взяты за основу для разработки быстрых алгоритмов поиска в диссертации.