Введение к работе
Актиальность темы. Объем данных, передаваемых по линиям связи и хранимых на внешних носителях информации в цифровом виде, постоянно возрастает, причем известно, что большая часть таких данных высоко избыточна. Значительное уменьшение избыточности и, следовательно, объема передаваемых и хранимых данных достигается за счет неискажающего или "бесшумного" сжатия данных (под неискажающим понимается метод сжатия, обеспечивающий точное восстановление исходных данных после декодирования). Так, например, для текстовых файлов коэффициент сжатия (отношение объема закодированных данных к объему исходных) достигает 25-30%, т.е. размер файла после сжатия в 3-4 раза меньше размера исходного файла.
Исследования в области неискажающего сжатия информации активно ведутся как у нас в стране (Бабкин В.Ф., Кричевский Р.Е., Рябко Б.Я., Трофимов В.К., Штарьков Ю.М. и другие), так и за рубежом (Ellas P., Lempel A., Rissanen J., Ziv J. и многие другие). Бурное же развитие вычислительной техники и микроэлектроники позволяет программно и аппаратно реализовывать все более сложные и эффективные методы сжатия.
Основными критериями оценки неискажающих методов сжатия являются:
коэффициент сжатия,
скорость кодирования и декодирования информации,
объем памяти, требуемый для реализации метода.
Причем, как правило, улучшение одного из этих показателей приводит к ухудшению других.
В настоящее время практически используются различные методы сжатия информации, основанные в большинстве случаев на словарных кодах Лемпела-Зива (LZ) и адаптивных вариантах кода Хаффмена, позволяющие значительно уменьшать избыточность данных и находящие широкое применение в компьютерных системах при архивации файлов, в модемах, на цифровых линиях связи и т.д. Однако, исследования в данной области продолжаются с целью создания новых и повышения эффективности уже известных методов
сжатия данных. В последнее время появились описания алгоритмов сжатия, построенных на других принципах, например, арифметическом коде, который предложили P. Elias, J. Rissanen и др. Особый интерес арифметические коды стали представлять после того, как Б.Я. Рябко был разработан алгоритм их быстрой реализации '" при сохранении той же эффективности сжатия.
Цели и задачи исследования. Целью настоящей диссер-
., тационной работы является разработка высокоскоростных методов
,: сжатия информации, основанных на новых классах кодов, позво-
. ляющих эффективно сжимать сообщения при ограниченном объеме
оперативной памяти.
Для достижения поставленной цели были решены следующие задачи:
-
Разработан алгоритм эффективной реализации быстрого арифметического кода.
-
Получен метод предсказания распределения вероятностей текущих символов источника по нескольким предыдущим.
-
Исследованы существующие и предложены новые эффективные структуры данных для быстрого поиска информации.
-
Разработаны методы экономного распределения оперативной памяти кодера и декодера.
-
Исследована зависимость степени сжатия от начального распределения вероятностей символов источника и найдены новые начальные распределения вероятностей, улучшающие коэффициент сжатия.
-
Предложен и реализован универсальный метод кодирования с быстрробновляющимся словарем, требующий небольшой объем памяти. Данный метод обеспечивает быстрое кодирование - де-
г.:<.: кодирование при достаточно высокой степени сжатия.
... 7. Разработан метод кодирования с фиксированным словарем, скорость которого в несколько раз выше, чем у известных методов. Он особенно эффективен при сжатии файлов небольшого размера и в случае, когда известна статистика источника.
Методы исследования. Для проведения исследований в диссертационной работе использовались теория информации и
теория кодирования дискретных источников информации, методы компьютерного моделирования. Все разработанные алгоритмы сжатия данных были реализованы программно и исследованы на персональном компьютере, а часть методов и на ЭВМ серии ЕС.
Научная новизна результатов диссертационной работы состоит в следующем:
-
Разработан и реализован метод сжатия информации, основанный на быстром арифметическом кодировании, превосходящий по эффективности известные методы.
-
Построен метод предсказания вероятностей текущих символов источника по нескольким предыдущим символам. Использование этого метода позволяет существенно улучшить коэффициент сжатия без снижения скорости кодирования и декодирования.
-
Применено динамическое распределение памяти для хранения узлов кодового дерева, позволяющее более экономно использовать оперативную память компьютера.
-
Разработаны методы оптимизации распределения начальных вероятностей символов источника в узлах кодового дерева, позволяющие увеличить эффективность кодирования.
-
Разработаны и реализованы быстрые методы сжатия информации, использующие как фиксированный, так и адаптивный к изменениям статистики источника словарь, превосходящие в 2-3 раза по скорости известные методы.
Практическая ценность результатов работы заключается в следующем: разработан и программно реализован ряд эффективных методов сжатия информации, которые могут использоваться как самостоятельно, так и в составе специализированных программных и аппаратных комплексов.
Реализация результатов работы. Разработанный автором метод сжатия информации используется в Государственной научно-технической библиотеке Сибирского отделения Российской академии наук (ГПНТБ СО РАН) для сжатия банков данных. Результаты диссертационной работы используются в учебном процессе при чтении курсов "Системное программирование" и "Вычислительная техника и программирование", в НИР СибГАТИ
"Разработка оптимальных методов кодирования информации". Основные научные положения использованы при проектировании статистического транскодера "Объединение", применяемого в настоящее время в центрах космической связи.
Апробация работы. Основные положения и результаты
диссертационной работы обсуждались на международных и всерос
сийских конференциях, в том числе: НТК "Передача, прием и
обработка сигналов в радиотехнических системах и уст
ройствах" (Ростов, 1991), межрегиональной конференции
"Обработка сигналов в системах двухсторонней телефонной
связи" (Суздаль, 1992), всероссийской НТК "Цифровые системы
передачи городских и сельских сетей связи ЦСП-92".
(Новосибирск, 1992), International congress on computer systems
and applied mathematics (St.Petersburg, 1993), международном
симпозиуме "Информационные модели и обработка случайных
сигналов и полей" (Львов-Харков-Тернополь, 1993), НТК
"Информатика и проблемы телекоммуникации (Новосибирск,
1994), International Workshop on Information Theory (Moscow,
1994), межрегиональной конференции "Обработка сигналов в
системах двусторонней телефонной связи" (Москва, 1994), между
народной НТК "Актуальные проблемы электронного приборо
строения" (Новосибирск, 1994), межрегиональной конференции
"Обработка сигналов в системах двусторонней телефонной связи"
(Москва, 1995), международной НТК "Информатика и проблемы
телекоммуникаций" (Новосибирск, 1995), Seventh Joint Swedish-
Russian international Workshop on Information Theory (St.-
Petersburg, 1995), Пятом международном семинаре "Распределенная
обработка информации" (Академгородок, Новосибирск, 1995).
Пибликации. По материалам диссертационной работы опубликовано 19 печатных работ, в том числе 4 статьи.
Личный вклад автора. Основные научные положения и результаты получены автором самостоятельно.
Основные положения, представляемые к защите.
-
Модифицированный арифметический код и разработанные автором структуры данных дают возможность построить эффективные методы сжатия данных с высокой скоростью кодирования - декодирования.
-
Оценка начального распределения вероятностей символов источника значительно влияет на коэффициент сжатия при кодировании, особенно на файлах небольшого размера. Найденные оценки распределения начальных вероятностей позволяют значительно повысить эффективность сжатия данных.
-
Разработанная структура данных для реализации арифметического кода позволяет экономно использовать оперативную память и учесть зависимость вероятностей символов источника от ранее закодированной части сообщения.
-
Самая высокая скорость кодирования и декодирования достигается для кодов, использующих фиксированный словарь. При использовании этих кодов на кодирование и декодирование каждого символа требуется всего несколько машинных команд. Введение адаптивного словаря лишь незначительно увеличивает время кодирования - декодирования.
Стриктира и объем диссертации. Диссертационная работа состоит из введения, четырех разделов, заключения и приложения. Содержание работы изложено на 141 страницах машинописного текста, иллюстрировано 45 рисунками и 8 таблицами. Список литературы содержит 99 наименований. В приложении на 36 страницах приведены тексты программ, реализующих предложенные в работе методы сжатия данных.
