Модели и алгоритмы контекстно-словарного сжатия текстовых данных : Применительно к системам электронного обучения

• Автор: Максимов, Сергей Владимирович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Уфа
• Количество страниц: 133 с. : ил.

Оглавление
ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ МЕТОДОВ СЖАТИИ ИНФОРМАЦИИ.

1.1. Предварительные замечания

1.2. Модели словарного сжатия.

1.3. Модели контекстного сжатия.

1.3.1. Модели с фиксированным контекстом

1.3.2. Контекстуальносмешанные модели

1.3.3. Вероятность ухода

1.3.4. Исключения.

1.3.5. Алфавиты.

1.4. Другие методы статистического моделирования.
1.4.1. Динамическое сжатие Маркова
1.4.2. Г рамматические модели.
1.4.3. Модели новизны.
1.4.4. Выводы по первой главе.
ГЛАВА 2. КОНТЕКСТНОСЛОВАРНЫЕ МОДЕЛИ СЖАТИЯ
2.1. Предварительные замечания
2.2. Сжатие текстовых файлов
2.3. Структурная модель представления сжатия текстовой информации .
2.4. Постановка задачи приведения к предложенной схеме
структурированного вида.
2.5. Модель сжатия использующий контекстнословарный метод
2.5.1. Модель хранения сжатого текста.
2.5.2. Древовидная модель словаря.
2.5.3. Модель словаря морфем
2.6. Выводы по второй главе.
ГЛАВА 3. АЛГОРИТМЫ КОНТЕКСТНОСЛОВАРНОГО СЖАТИЯ ДАННЫХ НА ОСНОВЕ ПРЕДЛОЖЕННЫХ МОДЕЛЕЙ.
3.1. Предварительные замечания
3.2. Приведение информации к структурированному виду
. 3.3. Преобразование словаря.
3.3.1. Разбиение слова на слоги
3.3.2. Разбиение на составные части слова
3.3.3. Древовидное представление структуры словаря.
3.4. Оценка построение структуры словаря от способа разложения слов.
3.5. Кодирование текста с использованием полученного словаря
3.5.1. Построение кодов переменной длины.
3.5.2. Применение кодирования контекстных индексов арифметического
кодирования
3.6. Оценка эффективности полученных кодов алгоритма кодирования с
помощью словаря
3.6.1. Стоимость кодирования текста
3.6.2. Оценка объема необходимой памяти
3.7. Управление распределением памяти.
3.8. Выводы по третьей главе
ГЛАВА 4. ПРОГРАММНЫЙ КОМПЛЕКС КОНТЕКСТНОСЛОВАРНОГО СЖАТИЯ ТЕКСТОВЫХ ДАННЫХ V I
4.1. Основные требования к техническому облику программного
комплекса V i .
4.2. Область применения программного комплекса
4.3. Проблемы существующих систем.
4.4. Задачи разработки программного комплекса.
4.5. Этапы разработки программного комплекса
4.6. Реализация блока сжатия файлов.
4.6.1. Реализация блока .
4.6.2. Реализация блока .
4.7. Сравнительная оценка эффективности.
4.7.1. Тестовые данные
4.7.2. Методика сравнения.
4.7.3. Результаты сравнения
4.8. Пример преобразования и кодирования слов.
4.9. Выводы по четвертой главе
ПРИЛОЖЕНИЕ 1
Листинг V.
ПРИЛОЖЕНИЕ 2.
Акт внедрения
Иллюстрации
Рис. 1 Модель сжатия реляционным словарем
Рис. 2 Модель сжатия динамическим словарем.
Рис. 3 Модель контекстного сжатия
Рис. 4 Операция клонирования в .
Рис. 5. Начальная модель ДМС с одним состоянием
Рис. 6. Более сложная начальная модель.
Рис. 7. Вероятностная грамматика для круглых скобок
Рис. 8 Структурная модель представления сжатия текстовой информации
Рис. 9 Модель сжатия контекстнословарного метода
Рис. Сравнение представления словарей.
Рис. Улучшенная модель представления словаря
Рис. . Модель сжатия текстового файла
Рис. Модель представления текста в естественных языках
Рис. Модель представления словаря после разбиения слов на слоги.
Рис. Модель программного комплекса V i .
Рис. Реализация блока сжатия текстового файла.
Рис. Реализация распаковки тестового файла
Рис. Результаты сравнения программ сжатия для тестового набора файлов.
Рис. График сравнения коэффициента сжатия от языковых особенностей
Введение
Актуальность


Сложность поставленной задачи состоит в том, чтобы правильно построить структуру, которая отвечала бы всем требованиям эффективного использования сжимаемой информации, с учетом их неоднородность. Таким образом, задача по разработке контекстно-словарного сжатия текстовых данных является весьма актуальной, а ее разрешение позволяет заметно повысить эффективность сжатия текстовых данных. Целью работы является разработка метода контекстно-словарного сжатия, обеспечивающего одновременно высокую степень сжатия текстовых данных и высокую скорость их распаковки при передаче и хранении. Разработка контекстно-словарных моделей сжимающих текстовые данные. Разработка древовидной логической модели пополняемой базы элементарных единиц словообразования (морфем) на основе известных правил словообразования в естественных языках. Разработка алгоритмов контекстно-словарного сжатия текстовых данных на основе предложенных моделей. Создание программного обеспечения, реализующего разработанные алгоритмы. Проверка эффективности разработанного программного обеспечения на примере организации хранения и передачи учебной информации. Объектно-когнитивная модель контекстно-словарного сжатия. Древовидная логическая модель пополняемой базы элементарных единиц словообразования (морфем). Контекстно-словарные алгоритмы сжатия текстовых данных с использованием элементов статистического прогнозирования. Программное обеспечение, реализующее разработанные алгоритмы контекстно-словарного сжатия данных. Новизна разработанной модели контекстно-словарного сжатия заключается в том, что она основана на предварительной структуризации сжимаемой текстовой информации с помощью известных правил для словообразования в естественных языках. Это позволяет повысить показатели качества сжатия текстовой информации в системах электронного обучения. Новизна предложенных алгоритмов, реализующих сжатие текстовой информации, заключается в использовании тезаурусных моделей ее сжатия, основанных на раздельном сжатии элементов текстовой информации: слов, ссылок на них, хранящихся в словаре, самого словаря, морфем, служебных символов. Новизна предложенного способа кодирования текстовой информации на основе статистических прогнозирующих моделей заключается во взаимосвязанном (контекстном) сжатии следующих классов символьных конструкций: слов, ссылок на них, хранящихся в словаре, самого словаря, морфем, служебных символов. Это позволяет более точно определить условные вероятности появления символов. Это позволяет обеспечить высокую степень сжатия текстовой информации в условиях возможного изменения условных вероятностей появления символов. Разработан программный комплекс MSV Quick Reader, использующий реализованные алгоритмы сжатия. Экспериментальная проверка эффективности предложенных алгоритмов контекстно-словарного сжатия текстовых данных с помощью данного комплекса показала, что они обеспечивают увеличение степени сжатия для текстовых данных по сравнению с известными его вариантами и как следствие, снижение трафика компьютерных сетей на 5 - 7 %. Использование программного комплекса MSV Quick Reader при электронном обучении позволяет существенно увеличить объемы хранимой в компьютере и передаваемой по компьютерным сетям учебной информации, при зодних и тех же характеристиках используемых компьютеров. Программный комплекс MSV Quick Reader внедрен в Башкирском государственном педагогическом университете и в настоящее время используется на кафедре программирования и вычислительной математики. Программное обеспечение данного комплекса имеет открытую архитектуру, что позволяет развивать данный программный комплекс с помощью добавления соответствующих модулей. Диссертационная работа выполнялась в рамках госбюджетного финансирования кафедре информатики Уфимского государственного авиационного технического университета и кафедре программирования и вычислительной математики Башкирского государственного педагогического университета, а также в рамках внутривузовского гранта « Информационные технологии в образовании» (БГПУ).