Содержание к диссертации
Введение 4
Глава 1 Методы и средства сжатия информации на основе
существующих моделей вычислений и способов кодирования 11
-
Классификация методов сжатия 11
-
Критерии оценки методов сжатия 12
-
Методы энтропийного кодирования 16
-
Модель вычислений 18
-
Конечные вероятностные источники 22
-
Кодирование источников Бернулли с известной вероятностной структурой 25
-
Кодирование источников Бернулли с неизвестной вероятностной структурой 30
-
Методы статистического моделирования 36
-
Алгоритм сжатия сортировкой блоков 39
1.10 Словарные методы сжатия 41
Выводы по главе 46
Глава 2 Исследование процесса поиска в словаре с использованием
строкового Б'-дерева 47
-
Классификация задач поиска 47
-
Деревья поиска 48
-
Задача поиска в сжатой информации 50
-
Поиск в строковом Б-дереве 51
-
Модификация Б-дерева. Б'-дерево 59
-
Постановка задачи диссертации 61
Выводы по главе 62
Глава 3 Разработка интегрированной вероятностной модели данных для
компрессии словарной информации 63
-
Общие положения по дизайну и разработке ядра словаря 63
-
Реализация алгоритмов Б'-дерева 64
3.3 Модульная компоновка библиотеки компрессии словарной
информации 66
-
Арифметическое кодирование 69
-
Моделирование 71
-
Контексты сжатия 73
3.7 Построение вероятностной модели данных. Использование
контекстов 75
-
Формализация модели словарной статьи 79
-
Использование словаря для кодирования словарных статей 84
ЗЛО Структура многопроходного алгоритма сжатия данных 84
Выводы по главе 86
Глава 4 Параметризация интегрированной модели данных, анализ
результатов 88
-
Изменение параметров модели на этапе сжатия 88
-
Методика эксперимента 89
-
Результаты эксперимента 90
Выводы по главе 94
Заключение 95
Литература 98
Приложение А Описание UML 106
Приложение Б Результаты эксперимента 112
Приложение В Исходный код алгоритмов Б'-дерева 117
Акт внедрения результатов работы 141
Введение к работе
Актуальность проблемы. Наблюдаемое в течение последних 15 лет стремительное увеличение количества используемых вычислительных машин (сопровождаемое неуклонным ростом их возможностей) привело к значительному расширению как круга пользователей ЭВМ, так и набора решаемых с их помощью задач.
Одновременное уменьшение размеров персональных компьютеров (ПК) сделало возможным создание карманных ПК (КПК). Сфера применения таких устройств необычайно широка: от использования в качестве персонального цифрового помощника (Personal Digital Assistant, PDA) до полноценной работы с изображением и звуком. Одним из возможных применений КПК является использование в качестве карманного словаря. Все попытки разработки программного обеспечения (ПО), предпринимаемые в последнее время в этой области, сталкиваются с необходимостью разработки и адаптации специальных алгоритмов обработки словарной информации для карманных устройств. В отличие от современных настольных и переносимых ПК, КПК обладают гораздо меньшим хранилищем данных и вычислительными ресурсами. Результаты исследований, направленных на создание эффективных схем неискажающего сжатия текстовой информации изложены в работах отечественных и зарубежных ученых: А. Маркова [43], Г. Буяновского [36],
И. Уиттена[28,29,30,32,33,53], Т. Белла [29,30,34,53], М. Бурроуза [41], Д. Виллера[41] и др.
Таким образом, задача хранения словарной информации в наиболее компактном виде достаточно актуальна.
Цель работы. Цель работы заключается в разработке многоплатформенной системы компрессии словарной информации (СКСИ) для КПК на основе высокоэффективных методов и алгоритмов сжатия словарных данных, которые позволяют осуществлять быстрый поиск и отображение данных.
Фундаментом научного подхода к разработке алгоритмов, представленных в данной работе, является современная теория кодирования информации.
Объекты и задачи работы.
1 Программное ядро словаря. Основные задачи: изучение целевых платформ разработки; выработка требований к библиотеке ядра словаря.
2 Структура словаря. Основные задачи: исследование особенностей построения словарей и хранения словарной информации; разработка вероятностной модели данных; разработка бинарного формата файла.
3 Эффективные алгоритмы сжатия словарных данных.
Основные задачи: исследование эффективных алгоритмов сжатия информации; моделирование вероятностной структуры обрабатываемых данных.
4 Эффективные алгоритмы поиска в словаре. Основные задачи: исследование быстрых алгоритмов поиска по словарю; разработка адаптированного к используемому аппаратному решению алгоритма поиска по словарю.
5 Интегрированная модель хранения и обработки информации. Основные задачи: настройка параметров модели; оценка эффективности решения, сбор статистики и подготовка результатов.
Методы исследования. Решение задач диссертационной работы основано на основных положениях теории информации, теории кодирования дискретных источников сообщений, комбинаторики, дискретной математики, теории чисел.
Проверка эффективности исследуемых в работе решений проводилась на программных и аналитических моделях перед началом эксплуатации ПО в рамках продукта SOCRAT 5.0, созданного при непосредственном участии автора диссертации.
Научная новизна. В работе осуществлено решение научной проблемы создания эффективных методов обработки и компактного хранения словарной информации.
В процессе исследований и разработок получены новые научные результаты, а именно: вероятностная модель словарных данных; алгоритмическое решение задачи высокоэффективной компрессии словарной информации (до 1,4 бит на символ); решение задачи быстрого случайного доступа к элементам словаря; бинарная и логическая структура данных СКСИ; - методика параметризации интегрированной модели СКСИ. Практическая ценность работы. Предложенные методы и алгоритмы обработки и хранения словарной информации позволяют создавать высокопроизводительное ПО для словарей, справочных систем и решения других задач хранения и отображения связанных данных.
По результатам проведенных исследований (при внедрении работы) разработана многоплатформенная словарная система SOCRAT 5.0 для КПК. Полученные файлы размером около 1,5 МБ позволяют одновременно использовать в зависимости от объема памяти КПК от 3 до 7-10 различных словарей.
Реализация и внедрение результатов исследования. Предложенный алгоритм сжатия реализован автором в универсальной библиотеке ядра словаря, позволяющей компилировать словари из текстового формата обмена во внутренний бинарный формат, а также работать со словарем в бинарном формате (поиск слов, получение статей). Клиентское исполнение библиотеки (без механизма сжатия) реализовано для следующих платформ: Windows СЕ (НРС2000, Pocket PC 2000, Pocket PC 2002), Windows 95/98/Me/NT/2000 (Win32) , Palm OS (Начиная с версии 3.5). Библиотека ядра словаря распространяется в составе продукта SOCRAT Dictionary компании «Арсеналъ». Большинство полученных в работе результатов доведено до уровня инженерных методов, алгоритмов и ПО. Практическое использование результатов подтверждено актами о внедрении. Все работы по реализации и внедрению проводились под руководством и при непосредственном участии автора как руководителя и ответственного исполнителя. Официальный сайт ПО SOCRAT Dictionary в Интернет:
На защиту выносятся следующие основные научные результаты: анализ состояния проблемы и необходимость создания системы компрессии словарных данных: формализация вероятностной модели словарных данных; сложная контекстно-ограниченная модель словарных данных; универсальный алгоритм поиска по словарю и доступа к произвольным элементам за конечное время; алгоритм сжатия словарных данных с качеством порядка 1,4 бит/символ; методика параметризации интегрированной модели; способы повышения эффективности сжатия словарных данных; внедрение СКСИ в результате создания многоплатформенного ПО SOCRAT Dictionary.
Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на следующих научных конференциях:
8-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов (Москва, МИЭТ, 2001).
9-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов (Москва, МИЭТ, 2002).
Международной научно-технической конференции "Приборостроение -2001" (Черкассы., ЧИТИ, 2001).
9-й Всероссийской международной научно-технической конференции студентов и аспирантов (Москва, МЭИ, 2002).
Публикации. По материалам диссертации опубликовано 8 работ.
Работа над диссертацией проводилась в плане решения задач согласно приоритетным направлениям развития науки, технологии и техники Российской федерации на 2003 — 2004 год.
Структура и объем работы. Диссертационная работа изложена на 141 страницах машинописного текста, иллюстрирована 26 рисунками и 5 таблицами. Она состоит из введения, четырех глав, заключения, списка литературы из 73 наименований и четырех приложений.
В первой главе проводится развернутый обзор известных кодов, алгоритмов и методов сжатия. На основе этой информации в третьей главе принимается решение о методе сжатия, который будет в дальнейшем использован при разработке системы.
Вторая глава посвящена обзору методов поиска слов в словаре.
Приведенные в первой и второй главах сведения являются основой для выбора методов сжатия и поиска, а также для построения модели данных (третья глава). В четвертой главе описывается методика параметризации модели данных, приводятся результаты анализа тестовых словарей.
В заключении сформулированы основные результаты работы, описана практическая ценность изложенного материала, приведены выводы по работе.
Акт внедрения результатов работы приведен в приложении.
