Разработка многоплатформенной системы компрессии словарной информации для карманных персональных компьютеров

• Автор: Шеломовский, Петр Леонидович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 141 с. : ил.

Содержание
Введение.
Глава 1 Методы и средства сжатия информации на основе существующих моделей вычислений и способов кодирования

1.1 Классификация методов сжатия

1.2 Критерии оценки методов сжатия

1.3 Методы энтропийного кодирования.

1.4 Модель вычислений.

1.5 Конечные вероятностные источники

1.6 Кодирование источников Бернулли с известной вероятностной структурой

1.7 Кодирование источников Бернулли с неизвестной вероятностной структурой

1.8 Методы статистического моделирования

1.9 Алгоритм сжатия сортировкой блоков
1. Словарные методы сжатия
Выводы по главе.
Глава 2 Исследование процесса поиска в словаре с использованием строкового Бдерева
2.1 Классификация задач поиска
2.2 Деревья поиска
2.3 Задача поиска в сжатой информации.
2.4 Поиск в строковом Бдерсве
2.5 Модификация Бдерева. Бдерево.
2.6 Постановка задачи диссертации.
Выводы по главе.
Глава 3 Разработка интегрированной вероятностной модели данных для компрессии словарной информации.
3.1 Общие положения по дизайну и разработке ядра словаря
3.2 Реализация алгоритмов Бдерева.
3.3 Модульная компоновка библиотеки компрессии словарной информации
3.4 Арифметическое кодирование.
3.5 Моделирование
3.6 Контексты сжатия.
3.7 Построение вероятностной модели данных. Использование контекстов
3.8 Формализация модели словарной статьи.
3.9 Использование словаря для кодирования словарных статей
3. Структура многопроходного алгоритма сжатия данных.
Выводы по главе
Глава 4 Параметризация интегрированной модели данных, анализ результатов.
4.1 Изменение параметров модели на этапе сжатия
4.2 Методика эксперимента
4.3 Результаты эксперимента
Выводы по главе
Заключение
Литература


Решение задач диссертационной работы основано на основных положениях теории информации, теории кодирования дискретных источников сообщений, комбинаторики, дискретной математики, теории чисел. Проверка эффективности исследуемых в работе решений проводилась на программных и аналитических моделях перед началом эксплуатации ПО в рамках продукта 8 ОС КАТ 5. Научная новизна. В работе осуществлено решение научной проблемы создания эффективных методов обработки и компактного хранения словарной информации. СКСИ. Практическая ценность работы. ПО для словарей, справочных систем и решения других задач хранения и отображения связанных данных. По результатам проведенных исследований (при внедрении работы) разработана многоплатформенная словарная система ЗОСЛАТ 5. КПК. Полученные файлы размером около 1,5 МБ позволяют одновременно использовать в зависимости от объема памяти КПК от 3 до 7- различных словарей. Реализация и внедрение результатов исследования. Клиентское исполнение библиотеки (без механизма сжатия) реализовано для следующих платформ: Windows СЕ (НРС, Pocket PC , Pocket PC ), Windows //Me/NT/ (Win) , Palm OS (Начиная с версии 3. Библиотека ядра словаря распространяется в составе продукта SOCRAT Dictionary компании «Арсеналъ». Большинство полученных в работе результатов доведено до уровня инженерных методов, алгоритмов и ПО. Практическое использование результатов подтверждено актами о внедрении. Все работы по реализации и внедрению проводились под руководством и при непосредственном участии автора как руководителя и ответственного исполнителя. СКСИ в результате создания многоплатформенного ПО SOCRAT Dictionary. Апробация работы. Всероссийской межвузовской научно-технической конференции студентов и аспирантов (Москва, МИЭТ, ). Всероссийской межвузовской научно-технической конференции студентов и аспирантов (Москва, МИЭТ, ). Международной научно-технической конференции "Приборостроение -" (Черкассы. ЧИТИ, ). Всероссийской международной научно-технической конференции студентов и аспирантов (Москва, МЭИ, ). Публикации. По материалам диссертации опубликовано 8 работ. Работа над диссертацией проводилась в плане решения задач согласно приоритетным направлениям развития науки, технологии и техники Российской федерации на — год. Структура и объем работы. Диссертационная работа изложена на 1 страницах машинописного текста, иллюстрирована рисунками и 5 таблицами. Она состоит из введения, четырех глав, заключения, списка литературы из наименований и четырех приложений. В первой главе проводится развернутый обзор известных кодов, алгоритмов и методов сжатия. На основе этой информации в третьей главе принимается решение о методе сжатия, который будет в дальнейшем использован при разработке системы. Вторая глава посвящена обзору методов поиска слов в словаре. Приведенные в первой и второй главах сведения являются основой для выбора методов сжатия и поиска, а также для построения модели данных (третья глава). В четвертой главе описывается методика параметризации модели данных, приводятся результаты анализа тестовых словарей. В заключении сформулированы основные результаты работы, описана практическая ценность изложенного материала, приведены выводы по работе. Акт внедрения результатов работы приведен в приложении. Вне зависимости от принципов, положенных в основу того или иного алгоритма, его целью является уменьшение количества избыточной информации в сообщении. Такие алгоритмы используются при обработке мультимедийных данных и при значительно большем коэффициенте сжатия не позволяют получить на выходе из декомпрессора сообщения идентичного первоначальному. По определению, методы сжатия общего назначения — неискажающие; искажающими могут быть только специальные методы сжатия. Как правило, искажения допустимы при обработке всевозможных сигналов (звука, изображения, данных с физических датчиков), когда известно, каким образом и до какой степени можно изменить данные без потери их потребительских качеств. Указанный критерий является ограничением для большинства алгоритмов сжатия информации, поскольку их требования к свободной памяти превышают объем памяти, доступный для работы на КПК.