автореферат диссертации по радиотехнике и связи, 05.12.02, диссертация на тему:Исследование и разработка эффективных словарных методов сжатия данных для систем цифровой связи

ргб од

- 8 кий 1В55

На правах рикописи

Ситняковская Елена Игоревна

УДК 621.391

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ЭФФЕКТИВНЫХ СЛОВАРНЫХ МЕТОДОВ СЖАТИЯ ДАННЫХ ДЛЯ СИСТЕМ ЦИФРОВОЙ СВЯЗИ

Специальность 05.12.02 - Системы, и устройства передачи информации по каналам связи

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Новосибирск 1995

Работа выполнена на кафедре прикладной математики и кибернетики Сибирской Государственной Академии Телекоммуникаций и Информатики (СибГАТИ).

Научный руководитель : академик МАИ, доктор технических наук,

профессор Б.Я. Рябко

Официальные оппоненты : член-корреспондент МАИ,

доктор технических наук, профессор В.К.Трофимов ;

кандидат физико-математических наук, старший научный сотрудник Ф.И. Соловьева

Ведущее предприятие : Научный совет по комплексной проблеме

"Кибернетика" РАН

Защита диссертации состоится и/6><Лг 1995 г.

в /о часов на заседании специализированного совета Д 118.07.01 в Сибирской Государственной Академии Телекоммуникаций и Информатики по адресу : 630102. Новосибирск, ул. Кирова.86

С диссертацией можно ознакомиться в библиотеке СибГАТИ. Автореферат разослан " // " 1995 г.

Ученый секретарь

специализированного совета Д 118.07.01 член-корреспондент МАИ, к.т.н., профессор

Г

Б.И. Крук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

В последние годы в связи с широким распространением цифровых сетей связи значительно увеличился объем передаваемой и хранимой цифровой информации. Такая информация обычно избыточна, поэтому внимание многих исследователей в нашей стране и за рубежом привлекают вопросы, касающиеся неискажающего или "бесшумного" сжатия данных, о чем свидетельствуют многочисленные публикации, посвященные этой теме (при неискажающем сжатии сообщение перед началом передачи кодируется, а после получения однозначно декодируется).

К настоящему времени разработаны различные классы методов сжатия данных. Среди них особый интерес представляют адаптивные, так называемые последовательные методы, позволяющие осуществлять кодирование источников информации с неизвестной статистикой за один просмотр, т.е. практически без задержки. Они отличаются высоким быстродействием, так как не требуют предварительного просмотра кодируемого сообщения. К этому классу относятся такие известные коды, как арифметический , код "стопка книг" , интервальный , адаптивный код Хаффмена , частотный и словарные коды.

Наиболее широкое распространение в последние годы получила обширная группа адаптивных словарных методов сжатия, базирующихся на известных алгоритмах Лемиела и Зива. Так, большинство стандартных программ, предназначенных для сжатия файлов на персональных компьютерах, основано на методах из этого класса. Они также широко применяются для сжатия информации в модемах, для неискажающего сжатия изображений и во многих других системах передачи и хранения информации. Возможность словарных методов эффективно кодировать сообщения, используя сравнительно небольшой объем оперативной памяти, позволяет реализовывать их в виде интегральных микросхем, применяемых в различных цифровых системах передачи информации.

В настоящее время ведется интенсивная разработка новых и продолжается исследование известных словарных методов сжатия данных, что объясняется их высокой эффективностью и практической важностью.

Цель работы. Целью настоящей диссертационной работы является разработка новых эффективных словарных методов сжатия данных для использования в различных цифровых системах передачи и хранения информации.

Для достижения поставленной цели были сформулированы и решены следующие основные задачи.

1. Проведен сравнительный анализ словарных методов сжатия данных и других основных классов адаптивных методов.

2. Уточнена область применения и перспективы использования словарных методов сжатия данных.

3. Исследованы существующие структуры данных и разработаны новые, эффективные для словарных методов сжатия.

4. Исследованы основные известные множества кодовых слов и разработаны новые, близкие к оптимальным для словарных методов сжатия данных.

5. Разработаны алгоритмы сжатия данных, эффективные при аппаратной реализации. При этом важно, что они позволяют достигнуть достаточно высокой степени сжатия, используя сравнительно небольшой объем оперативной памяти.

6. Построены высокоэффективные словарные методы для сжатия основных типов данных.

Методы исследования. В работе использованы основные методы теории передачи информации и теории кодирования дискретных источников сообщений, а также методы компьютерного моделирования.

Наичная новизна результатов работы состоит в следующем.

1. Показано, что среди адаптивных методов неискажающего сжатия данных наиболее эффективным является класс словарных методов.

2. Исследована зависимость эффективности словарных методов сжатия от используемой структуры данных, и разработаны новые структуры данных, близкие к оптимальным для методов из этого класса, позволяющие сократить требуемый объем оперативной памяти кодера и декодера.

3. Построены и исследованы новые кодовые множества, эффективные при использовании в словарных методах сжатия.

4. Найдены новые методы сжатия данных, эффективные при аппаратной реализации.

5. Разработаны словарные методы, высокоэффективные при сжатии основных типов данных (программы на различных алгоритмических языках, тексты на естественных языках, объектные модули).

Практическая ценность результатов работы заключается в следующем :

• показано преимущество класса словарных методов сжатия перед другими классами последовательных методов при неискажающем кодировании цифровых данных;

• разработаны эффективные методы сжатия для основных типов данных, позволяющие в 2 - 2,5 раза уменьшить длину сообщений;

• построены методы сжатия данных, обладающие высокой эффективностью при аппаратной реализации.

Реализация результатов работы Результаты диссертации получили практическое применение при построении высокоскоростного специализированного архиватора для Новосибирского представительства фирмы "LenBell Telephone" и в процессе разработки аппаратуры передачи речи со скоростью передачи менее 4800 бит/с, в рамках выполнения НИОКР по теме "Вокодер-4". Результаты диссертации используются в учебном процессе при чтении курсов "Системы программирования" и "ВТ и программирование".

Апробация работы. Основные результаты диссертационной работы обсуждались на Всесоюзной НТК "Исследование и разработка современных радиоэлектронных элементов и устройств" (Рига, 1990), на Всесоюзной НТК "Проблемы и перспективы развития цифровой звуковой техники" (Ленинград, 1990), на Международной НТК "Проблемы функционирования информационных сетей" (Новосибирск, 1991), на Всероссийской НТК "Цифровые системы передачи городских и сельских сетей связи - ЦСП-92" (Новосибирск, 1992), на Межрегиональной НТК "Обработка сигналов в системах двусторонней телефонной связи" (Суздаль, 1992), на Международном симпозиуме "Компьютерные системы

и прикладная математика" (С.-Петербург, 1993) и на Международном симпозиуме по теории информации (Москву, 1994).

Публикации. По теме диссертации опубликовано 17 печатных

работ.

Основные положения, представляемые к защите.

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

2. Структуры данных, базирующиеся на поисковом дереве "бор", являются близкими к оптимальным для словарных методов сжатия данных. Использование таких структур позволяет значительно повысить скорость кодирования и декодирования.

3. Использование в словарных методах сжатия известного кода ф! и разработанного автором кода ере позволяет приблизить степень сжатия к предельной энтропии Ь„ при сохранении достаточно высокой скорости кодирования и декодирования.

4. При аппаратной реализации высокоэффективными являются разработанный автором словарный алгоритм АЗ, базирующийся на известном методе Лемпела-Зива-Бендера-Вольфа (ЛЗБВ) , и специально разработанный для реализации аппаратно быстрый адаптивный словарный код (БСК), относящийся к группе методов, использующих адаптивный словарь, предложенный в совместной работе И.В. Перцева, Б.Я. Рябко и автора диссертации . Этот код несколько уступает АЗ по степени сжатия, однако, у него высокая скорость кодирования и декодирования, превосходящая, в среднем, скорость метода АЗ - в 3 раза. Перечисленные методы позволяют эффективно "сжимать" данные, используя сравнительно небольшой объем оперативной памяти кодера и декодера.

5. Наиболее эффективными при сжатии программ на различных алгоритмических языках, текстов на естественных языках и объектных модулей являются предложенные автором словарные алгоритмы А2 и АЗ, базирующиеся на известном методе ЛЗБВ.

Стриктура и объем диссертации. Диссертационная работа состоит из введения, четырех разделов, заключения и приложения. Содержание работы изложено 163 страницах машинописного текста, иллюстрировано 38 рисунками и 24 таблицами. Список литературы

содержит 99 наименований. В Приложении на 44 страницах приведены тексты программ, реализующих предложенные в работе словарные методы сжатия данных.

КРАТКОЕ СОДЕРЖАНИЕ

Во ВВЕДЕНИИ обосновывается актуальность темы, формируются цели и задачи исследований, приводятся основные защищаемые положения

Некоторые важные в теории кодирования источника величины, используемые в диссертации, такие, например, как средняя длина кодового слова, приходящегося на одну букву сообщения, энтропия и избыточность, позволяющие оценить эффективность того или иного метода кодирования, определены в первой главе.

Приведены краткие характеристики основных представителей класса адаптивных последовательных методов сжатия данных, таких как адаптивный код Хаффмена, код " стопка книг ", интервальный и частотный коды, класс арифметических и класс словарных кодов. На основании анализа литературы дана сравнительная оценка эффективности перечисленных адаптивных методов сжатия. Показано, что среди адаптивных последовательных методов сжатия данных, наиболее используемыми в практических задачах являются словарные методы, базирующиеся на известных алгоритмах Лемиела и Зива. Широкое распространение методов из этого класса обусловлено такими их достоинствами, как высокая скорость кодирования и декодирования, быстрая адаптация к изменению типа данных и возможность учитывать далекие статистические связи кодируемых сообщений, что позволяет достигнуть степени сжатия, близкой к предельной энтропии Ь„ . Кроме того, важной особенностью этих методов является относительно невысокая сложность их реализации.

Общая схема кодирования сообщений с помощью словарных методов сжатия данных может быть описана следующим образом : • Сообщение разбивается на слова переменной длины. Кодируя очередное слово, сначала ведется поиск ему подобного в закодированной части сообщения. Далее, если такое слово найдено, передается соответствующий ему код, в противном случае, передается специальный

символ, сигнализирующий об его отсутствии, и само слово. Каждое новое, не встречавшееся ранее слово запоминается, и ему присваивается индивидуальный код. • При декодировании по принятому коду определяется закодированное слово и добавляется к декодированной части сообщения. В случае получения специального символа, сигнализирующего о передаче нового слова, принятое слово запоминается, и ему присваивается такой же, как и при кодировании, код. Декодирование является однозначным, т.к. каждому слову соответствует свой собственный код.

Существуют некоторые принципиальные различия • между ' словарными методами сжатия. Они, например, могут отличаться друг от друга способом кодирования слов и максимальным количеством символов, составляющих слово. Однако, основное различие, позволяющее разделить эти методы на две группы, заключается в организации хранения и поиска слов. Так, одна группа объединяет алгоритмы, использующие адаптивный словарь, включающий все встретившиеся слова. Если словарь заполняется до окончания кодирования, то в некоторых методах он обновляется (на место ранее встреченных слов записываются новые), а в некоторых кодирование продолжается без обновления словаря. Другая группа методов объединяет алгоритмы, осуществляющие поиск слов из какой-либо части ранее закодированного текста, называемой обычно "окном". Количество символов, образующих "окно", называют его длиной.

Далее в первой главе приведена краткая характеристика основных представителей класса словарных методов сжатия.

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

Эффективность любого метода сжатия в значительной степени зависит от используемой при его реализации структуры данных. К настоящему времени разработаны различные структуры, например, использующие лексикографический поиск информации, бинарное дерево поиска, дерево "бор" и др.. Автором исследованы известные и на их основе разработаны новые структуры данных, эффективные при реализации словарных методов.

Для проведения исследований были выбраны словарные методы кодирования, нашедшие наиболее широкое практическое применение;

такие как метод Лемпела-Зива-Бунтона-Борелло (ЛЗББ), основанный на использовании адаптивного словаря, и метод Лемпела-Зива-Бендера-Вольфа (ЛЗБВ), основанный на использовании "скользящего окна".

В методе ЛЗББ перед началом кодирования в словарь включаются все буквы заданного алфавита. Далее, в процессе кодирования, читаются текущие символы сообщения х^ Xj Х3 ...xr (R > 1), и в словаре ведется поиск слова наибольшей длины, состоящего из входных символов в порядке их поступления. Когда слово, например, XjX2 найдено, передается номер содержащей его строки в словаре. После этого в свободную строку словаря записывается новое слово, образованное только что закодированным словом и первым не вошедшим в него символом, т.е. слово Xj Х2 Х3. В случае заполнения словаря до окончания кодирования, ранее записанные слова удаляются, а новые слова помещаются на их место.

Пример : используя метод ЛЗББ, сообщение "abababaabacabac" может быть закодировано как "0135527", где код 0 - соответствует символу а, 1 - Ь, 3 - слову ab, 5 - aba, 2 - с, 7 - abac (рис.1).

Вход кодера: a b ab aba aba с abac

Выход кодера: 0 1 3 5 5 2 7

Рис.1. Схема кодирования методом ЛЗББ

При декодировании по принятому коду сразу определяется номер строки, в которой находится переданное слово, что не требует просмотра словаря. По этой причине декодирование является значительно более быстрой процедурой, чем кодирование.

При реализации метода ЛЗББ наиболее сложными процедурами, существенно влияющими на скорость кодирования и декодирования, являются, во-первых, поиск слов в словаре (при кодировании), во-вторых, удаление "старых" слов из словаря в случае отсутствия свободных строк для записи новых.

С целью ускорения поиска слов в словаре, авторы метода ЛЗББ предложили использовать один из вариантов алгоритма поиска "бор". Назовем этот вариант F-деревом. Каждому узлу такого дерева

соответствует определенная строка словаря, а индивидуальным номером узла является номер соответствующей ему строки. Кроме метода поиска авторами предложена специальная система меток, позволяющая быстро осуществлять удаление "старых" слов из словаря и запись на их место новых.

Словарный метод ЛЗБВ, основанный на использовании "окна", состоит в следующем. Пусть кодируется сообщение XI Хг ...Хл (И > 1). На вход кодера поступают текущие буквы хч хч+1 хч+2 ...хк (1< q< К). В подслове хч.„ х[|.и,+1 ... хч_1 , называемом "окном" длины осуществляется поиск слова, состоящего из наибольшего количества входных символов, т.е. слова хч хч+2 ... . Как только такое слово найдено, передается символ 1 и координаты кодируемого слова, представленные парой чисел О,.)), где 1 - номер позиции "окна", с которой начинается данное слово, 3 - длина этого слова. В случае отсутствия в "окне" первой буквы поиск прекращается, и на выход кодера передается символ 0 и двоичное представление буквы хч . После каждого шага кодирования "окно" обновляется, т.е. сдвигается вправо на 3 символов. Далее кодирование осуществляется с первой незакодированной буквы и продолжается до тех пор, пока не закончатся входные данные.

На рис.2 показан фрагмент кодирования части "аЬасаЬас" сообщения "ЬаЬаЬааЬасаЬас" методом ЛЗБВ при длине "окна", равной 6. В результате такого кодирования передана следующая последовательность кодовых слов " (1,3,3) (0,"с") (1,4,4) ".

При декодировании (см. пример на рис.3), если первым битом является символ 1, то по номеру позиции 1 и количеству символов ] определяется закодированное слово, которое добавляется к декодированной части сообщения. Если в качестве первого бита кодового слова передан символ О, то декодированная часть текста дополняется буквой, код которой следует за 0. Обновление "окна" на каждом шаге декодирования осуществляется так же, как и-при кодировании.

Для словарного метода ЛЗБВ была предложена эффективная структура данных, построенная на базе известного метода поиска"бор".

шаг 1

шаг 2

шаг 3

baba

- И -

6 5 4 3 2 1

ь а Ь а Ь а

abacabac

кодовое слово : (1,3,3)

6 5

3 2 1

ЬаЬ а b а а b а cabac

6

кодовое слово : (0,'с')

1

b а а Ь а с

abac

кодовое слово : (1,4,4) Рис. 2. Кодирование методом ЛЗБВ при W=6.

шаг 1 :

6 5 4 3 2 1

Ь а b | а Ь а

кодовое слово : (1,3,3) 6 5 4 3 2 1

ЬаЬ а Ь а а Ь а

шаг 2 :

6 кодовое слово : (0,'с1) 5 4 3 2 1

baba b а а Ь а с

шаг 3 :

6 кодовое слово : (1,4,4) 5 4 3 2 1

bababaab а с а b а с

слово : aba

буква : с

слово : abac

Рис. 3. Декодирование методом ЛЗБВ при W=6.

Предлагаемая структура представляет собой дерево, каждый узел которого содержит следующую информацию:

• номер уровня, означающий каким по счету является узел на ветви, начиная с первого узла после корня (ветвь - часть дерева от корня до листового узла, т.е. до узла, не имеющего сыновей);

• номер отца, т.е. номер предыдущего узла на ветви;

• количество разветвлений данного узла, т.е. количество сыновей;

• слово, соответствующее данному узлу;

• номер позиции с которой начинается слово.

Исключением является корневой узел, не содержащий никакой информации и имеющий постоянный индивидуальный номер, равный 1. Для краткости будем называть такое дерево Т-деревом.

Поясним процесс поиска слов в "окне" с помощью Т-дерева на конкретном примере, когда длина "окна" АУ равна 6 (см. рис. 4а). Пусть после кодирования первых шести символов сообщения "окно" имеет следующий вид: "аЬс1аЬс". Требуется закодировать оставшуюся часть текста: "<1Г. Для этого сначала буква "с!" записывается в позицию "окна", на которую указывает стрелка, т.е. в позицию 1 (номера позиций возрастают слева направо, начиная с единицы), а находящийся в ней символ удаляется (см. "окно" на рис. 46). Заметим, что при удалении символа из какой-либо позиции "окна", удаляется и концевой узел ("лист") дерева, содержащий номер этой позиции. Далее на первом уровне дерева проверяется наличие узла, которому соответствует буква "с1". Такой узел находится на дереве под номером 4 (см. рис. 4а). После этого читается следующий символ "Р сообщения и, после его записи в "окно", осуществляется поиск узла, которому соответствовало бы слово "с!Г. Так как такой узел отсутствует на дереве, и у узла 4 нет "сыновей" (рис. 4а), поиск слова наибольшей длины продолжается в "окне", начиная с позиции, равной сумме двух значений: уровня этого узла и соответствующего ему номера позиции. В данном случае поиск начинается с четвертой позиции "окна", в которой находится буква "а". Так как символы "а" и "Г не совпадают, поиск прекращается, а к узлу 4 добавляются два "сына" ( узлы 8 и 9 ). После этого дерево пополняется узлом, соответствующим слову "Р (рис. 4в), а слово "(1" кодируется

последовательностью (1,3,1).

В процессе кодирования описанное выше дерево может быстро разрастаться. Можно легко показать, что при обработке некоторых файлов количество узлов достигает значения \У , где - длина "окна". С увеличением количества узлов дерева заметно возрастает и объем используемой оперативной памяти. Так, при длине "окна" (Л¥) 2 кбайта, объем памяти, требуемый для хранения Т-дерева, превосходит 4 Мгбайта,

а) НЕЕШЕИ^ ^ ЕЕИЕНЗ' в) нм-мчьИ

Рис 4. Использование Т-дерева для поиска слов в "окне" при \\г=6

что превышает возможности современных персональных компьютеров.

По этой причине возникает задача построения алгоритма, позволяющего ограничить количество хранимых, узлов, образующих Т-дерево. Однако, уменьшение числа узлов влечет за собой понижение коэффициента сжатия, а иногда и снижение скорости кодирования из-за усложнения метода. В связи с этим, были разработаны и экспериментально исследованы три алгоритма, позволяющие хранить только часть узлов Т-дерева и не допускающие при этом существенного снижения эффективности сжатия. Они базируются на методе ЛЗБВ и обозначены через А1, А2 и АЗ.

Эффективный способ программной реализации словарных методов сжатия предложен в § 2.4. Для представления Р-дерева и Т-дерева в

памяти компьютера использовалась двумерная таблица, каждая строка которой содержит сведения о соответствующем ей узле. При использовании такой таблицы, в процессе кодирования постоянно возникает необходимость нахождения информации о каком-либо узле дерева. Эта процедура осуществляется очень быстро в методе ЛЗББ, основанном на использовании адаптивного словаря, построенном для реализации на специализированном устройстве, которое позволяет по слову определить его номер в таблице за один такт работы без какого -либо поиска, за счет устройства с глубоким распараллеливанием вычислений. Для реализации метода ЛЗББ на компьютере (а не на специализированном устройстве) автором диссертации был разработан алгоритм, названный Б1.

Для упрощения и ускорения процесса поиска слов в таблице, алгоритм Б1, как и коды А1, А2 и АЗ, использует метод поиска, основанный на известном принципе хеширования, что можно рассматривать как отыскание адреса некоторого элемента в памяти ЭВМ с помощью хеш-функции.

Алгоритмы сжатия А1, А2 и АЗ, базирующиеся на адаптивном словарном методе ЛЗБВ, использующем "скользящее окно", и алгоритм Б1, основанный на методе ЛЗББ, использующем адаптивный словарь, были реализованы в виде программных комплексов, выполненных на языке Паскаль. Для их экспериментального исследования был сформирован представительный набор тестов, состоящий из файлов следующих типов:

• программы на алгоритмических языках (Паскаль, Си, Ассемблер);

• документация на естественных языках (английский, русский);

• объектные модули.

В ходе экспериментального исследования реализованных методов сжатия, все файлы, используемые в качестве тестов, были не только закодированы, но и декодированы. Причем, после каждого декодирования полученный файл сравнивался с исходным ( это служит гарантией правильности работы программ).

В табл. 1 приведены значения коэффициентов сжатия, полученных при кодировании файлов исследуемыми методами (коэффициент сжатия определяется как отношение длины закодированного сообщения к длине

Таблица 1.

Значения коэффициентов сжатия (%)

Название файла Длина файла, байт Название метода сжатия

А1 А2 АЗ Б1

Длила "окна" Объем словаря

1024 2048 2048 4096 2048 4096 1024 2048 4096

Программа на Паскале 58308 42 39 38 36 38 36 53 45 43

Текст на английском 71267 49 46 46 45 46 45 57 47 43

Текст на русском 34963 54 51 52 50 50 48 61 54 51

Объектный модуль 11136 71 72 72 74 71 72 75 76 79

исходного, выраженное в процентах). Расчеты проводились при различных значениях объема памяти, отводимой для выполнения программы. В связи с тем, что общий объем памяти кодера и декодера зависит от используемого алгоритма, от размера хеш-таблицы и ряда других характеристик, выбираемых программистом, в табл. 1 приведен только один параметр, определяющий общий объем памяти - длину "окна" для алгоритмов А1, А2 и АЗ и объем словаря для метода Б1.

Анализ полученных результатов показал, что независимо от объема занимаемой оперативной памяти, при кодировании программ на различных алгоритмических языках и документации на английском языке, лучшего сжатия позволяет достигнуть использование метода А2, а при кодировании русских текстов и объектных модулей - использование алгоритма АЗ. Исключением являются английские тексты объемом свыше нескольких килобайт, кодирование которых эффективнее осуществлять методом Б1, использующим словарь объемом, равным 4096. В целом, при сжатии данных различных типов наиболее эффективен код АЗ. Однако, в случае необходимости обеспечить высокую скорость кодирования и декодирования, для сжатия данных лучше использовать метод Б1.

Существенное влияние на эффективность, а именно на коэффициент сжатия словарных методов, основанных на использовании "окна", оказывет способ кодирования величин 1 и обозначающих соответственно номер позиции "окна", с которой начинается кодируемое слово, и длину

- le -

этого слова. Таким образом, практически важной задачей является выбор пары кодов для i и j, использование которой обеспечивало бы максимальное сжатие.

Эффективные кодовые множества для словарных методов сжатия, использующих "окно", в частности, для ^ методов Al, А2 и A3, представлены в третьей главе.

Глава начинается с краткой классификации известных кодовых множеств. Затем, для описания исследуемых множеств кодовых слов вводятся следующие обозначения :

Р(ш) - запись целого числа m (m>0) в двоичной системе счисления (начиная с 1-ой левой единицы);

р (ш) - Р(ш) без первой крайней левой единицы;

L(x) - длина слова х;

{0}п - строка, состоящая из п нулей;

а(ш) - {0}L«4»OH.

Например : (3(9)=1001; р (9)=001; L(p(9))=4; {0}2=00; а(9)=000.

Тогда код, состоящий из бесконечного множества кодовых слов и обозначенный как cpt , можно задать в виде последовательности двух подслов :

cpj(m) = a(m+i) P(m+1).

Например, кодовое слово числа 9 записывается следующим образом: 000.1010 (точка в этом и всех последующих примерах стоит только для удобства чтения ).

Используя для кодирования подслова a(m+l) код <pi, получим другой код, обозначим его через ф2, состоящий из трех подслов

cp2(m) = a(k) p(k) р (т+1), где k = L(P(m+l)).

Например, ф2<9) = 00.100.010.

Используя код (р( для записи подслова а(к), можно получить из срг новый код фз- Например, фз (9)=0.11.00.010.

Таким образом, каждый раз кодируя число нулей а кодом фь можно получать все новые и новые коды. Например, ф4(9)=0.10.1.00.010.

Далее в третьей главе описываются коды, предназначенные для кодирования конечных множеств. Для их описания вводятся дополнительные обозначения : N(9) - количество слов в кодовом множестве ср, у(шД) - двоичная запись натурального числа т, в которой берется Ь крайних справа знаков. Если р(ш) < то Р(т) дополняется слева нулями. Например. у(5,2)=01, у(5,8)=00000101.

Тогда один из таких кодов, обозначим его через 95, можно задать следующим образом:

ф5(ш) = у(М) Нт+1), (1)

где к=Цр (т+1)),

при не целом loglogN и

у(М) р (т+1) при т = 0.....N-3,

ср5(т) = {I}4 р (N-1)0 при т = N-2, (2)

р (N-1)1 при т = N-1, где к=Ь(р (т+1)), при целом loglogN.

Например, при Ы(ф)=16 значение loglogN - целое. Следовательно, для построения кода 95 используем формулу (2), 1 = = 2

(ф5(0)=00, ф5(1)=01.0, Ф5<2)=01.1.....ф5(15)=11.111.1).

Удобным представлением конечных множеств кодовых слов являются двоичные деревья. На рис.5 изображено дерево, соответствующее коду фэ, количество слов N которого равно шестнадцати.

На базе кода ф5 автором построены новые конечные кодовые множества. Приведем ниже их описание.

Добавив к каждому концевому узлу дерева на рис.5 по два сына или, другими словами, "расщепив" эти узлы на два, получим новое кодовое множество, которое мы обозначим через Ф51, состоящее из 32 слов. Таким образом, можно сказать, что код Ф51 получен из кода Ф5 для алфавита объемом N=16 путем одного "расщепления".

t = Гь^гм!

£ (Ш+1)

О/ \1

Рис.5. Представление в виде дерева кода <¡>5, состоящего из 16-ти слов (N=16).

"Расщепляя" кодовое множество ср5, состоящее из 16-ти слов, два, три и более раз, можно получать соответственно множества Ф52, Ф53, Ф54 и т.д.

Опишем эти множества более формально. Для этого обозначим количество "расщеплений" через п. Тогда код 95" для целого т, О <т < N-1 задается равенством

Ф5п(ш) = Ф5(Ьп/2п_]) у(щ - 2»-(1т/2»]), п).

На основе рассмотренного выше кода 95 и его модификаций, автором было разработано еще одно кодовое множество, обозначим его через фб, предназначенное для кодирования конечных алфавитов. Код фв может быть задан следующим образом :

гу((Ц р (к+т))-1одк)Л) р (к+т) при т = 0,...,(М-2)-к,

ф6(т) =

{I}4 р (N-1) 7(ш-Х+1+к,1ояк) {!}' р (N-1) Р(к-1)0

{1}' р (N-1) Р(к-1)1

где t = LloglogNJ - при не целом loglogN, 1 = loglogN-l - при целом

при т = (1Ч-1)-к,..., N-3, при т = N-2, (3)

при ш = N-1,

N

г = 2*, к = 2? .

Кроме неравномерных кодовых множеств исследовался также и равномерный код, обозначим его через ф7. Кодовые слова ф7(т) множества ф7 образованы двоичным представлением числа т, под запись которого отводится ГlogNl знаков, где N - объем кодируемого алфавита или, другими словами, количество слов в кодовом множестве. Таким образом, код ф7 можно задать равенством

ф7(ш) = уОМ) , где 1 = Г1оя>Л .

Среди исследуемых словарных методов, наиболее эффективными по сжатию оказались алгоритмы А2 и АЗ. Поэтому экспериментальное исследование эффективности всех возможных сочетаний рассмотренных выше кодовых множеств проводилось с целью выбора наилучшей пары кодов для чисел 1 и } в методах А2 и АЗ.

Оказалось, что наилучшими кодами для номера позиции "окна" О) и длины найденного слова (3) являются разработанный автором код фй и известный код <р1, соответственно, что справедливо для всех типов файлов.

В табл.2 приведены значения коэффициентов сжатия, полученные при кодировании сообщений различных типов методами А2 и АЗ, использующими наиболее эффективное сочетание исследованных кодов.

Для оценки эффективности наилучших кодовых множеств, используемых для кодирования чисел I и была вычислена оценка энтропии (Н), которая по известной теореме Шенпопа, является нижней оценкой для средней длины кодового слова. Величина Н определялась равенством :

„ (Нп /0>+р(1)(Н(1)+Нд))+р(О)Н(а))(71(О)+ 7Г(1)> Н — ^ . £ ,

где f - длина исходного кодируемого файла в байтах;

Н(1/о) " оценка энтропии кодовых слов, используемых для передачи сведений о способе дальнейшего кодирования (по содержимому "окна" или не по "окну");

Н(0 - оценка энтропии кодового слова, кодирующего номер позиции I "окна", с которой начинается найденное слово (0 < 1 < \У-1);

Таблица 2.

Нижние границы эффективности кодов (Н) и значения коэффициентов сжатия (Ксж), полученные в результате кодирования методами А2 и АЗ, использующими

лучшее сочетание кодов

Тип и размер файла (байт) Метод А2 Метод АЗ

W = 2048 W = 4096 W = 2048 W = 4096

Фб, Ф1 н, % Фб. Ф1 н, % Фб, Ф1 н, % Фб. Ф* н, %

Ксж.,% Ксж.,% Ксж.,% Ксж.,%

Паскаль (58308) 38 35 36 32 38 35 37 32

Английский (71267) 46 42 45 39 47 41 47 40

Русский (34963) 52 46 50 44 50 46 49 44

Объектный модуль (11136) 72 65 74 63 71 65 74 63

H(j) - оценка энтропии кодового слова, кодирующего длину j найденного слова (1 < j < W);

Н(а) - оценка энтропии кодовых слов, кодирующих буквы aeA={ai,...,at}, не найденные в "окне";

я(0), л(1) - частоты встречаемости признаков 0 и 1 соответственно; р(0), р(1) - оценки вероятностей появления признаков 0 и 1, соответственно, в закодированном сообщении.

Легко видеть, что вычисление величины Н подобно вычислению коэффициента сжатия, определяемого как отношение длины закодированного сообщения к длине исходного.

Как показывают результаты (см. табл.2), использование в словарных методах сжатия пары кодов : фб для i и cpi для j позволяет достигнуть коэффициента сжатия, не намного превосходящего нижнюю границу Н, в среднем, на 3 - 6 %.

Необходимо отметить, что нижняя граница, возможно, "занижена",

т.к. она была вычислена для кодов, требующих два просмотра кодируемого сообщения, а верхние оценки получены для кодов, "сжимающих" данные за один просмотр.

Следовательно, дальнейшее усовершенствование кодовых множеств, предлагаемых для использования в словарных методах, если и даст выигрыш, то сравнительно небольшой.

Методы сжатия данных, эффективные при аппаратной реализации исследуются в четвертой главе.

Для использования в различных цифровых системах, таких как модемы и системы спутниковой связи, методы сжатия данных часто должны быть реализованы аппаратно, а не в виде программных комплексов. Требование аппаратной реализации накладывает ряд дополнительных ограничений на конструкцию кода.

В этом случае наиболее важным параметром метода сжатия, в значительной степени определяющим сложность его реализации, является объем оперативной программируемой памяти, требуемой для работы кодера и декодера. Этот параметр также влияет на эффективность сжатия. Так, ограничение объема используемой оперативной памяти влечет за собой заметное ухудшение коэффициента сжатия. Второе важное требование, предъявляемое к кодам, предназначенным для реализации в виде интегральных микросхем, - они должны обеспечивать высокую скорость кодирования и декодирования.

Таким образом, основная задача, возникающая при разработке методов сжатия для аппаратной реализации - построение эффективных методов, обладающих высоким быстродействием и использующих небольшой объем оперативной памяти.

Как показал анализ литературы, наиболее перспективными методами сжатия данных, отвечающими основным требованиям, предъявляемым при аппаратной реализации, являются словарные и интервальные коды. Возможность применения словарных методов объясняется такими их достоинствами, как высокое быстродействие и хорошая степень сжатия, достигаемая при использовании сравнительно небольшого объема оперативной памяти. Они также являются достаточно простыми для реализации в виде интегральных микросхем. К основным достоинствам интервальных кодов относятся простота алгоритма и небольшой объем

оперативной памяти, требуемый для работы (значительно меньший, чем у словарных методов), что привлекает к ним внимание специалистов, разрабатывающих коды для аппаратной реализации.

Интервальный метод и его модификации рассматриваются в § 4.2.

В исходном интервальном алгоритме при кодировании очередной буквы х; определяется расстояние Х(х;) до ее предыдущего появления в подслове • ■ •х1-1 ("окне" длины \\0, ¡>0. Запись этого расстояния

и является кодом Х|. В случае отсутствия буквы X; в "окне", Х(щ) присваивается значение + 1 и X; кодируется словом, состоящим из >.(х|) и кодового обозначения буквы X;. Каждая закодированная буква записывается в "окно".

Сжатие данных интервальным методом достигается за счет того, что расстояние между встречами более вероятных букв мало, а чем меньше расстояние, тем короче соответствующее ему кодовое слово, следовательно, часто встречающиеся буквы будут кодироваться короткими словами.

На основе интервального метода сжатия автором разработаны новые алгоритмы, требующие при реализации сравнительно небольшой объем оперативной памяти. Эти алгоритмы названы первой и второй модификациями интервального кода и, для краткости, обозначены через И1 и И2 соответственно. При кодировании исходным интервальным методом, в "окне" много места занимают повторения одних и тех же букв, что удлиняет кодовые слова. Этот недостаток отсутствует у модифицированных интервальных алгоритмов, у которых каждая буква алфавита записывается в "окно" только один раз, что упрощает кодирование. Подобно интервальному методу, в алгоритмах И1 и И2 используется "окно" фиксированной длины

В методе И1 номера позиций "окна" (0 кодируются словами равномерного кода, длина п которого зависит от размера "окна" и равна Кодируя очередную букву X; сообщения, сначала ведется поиск ее в "окне". Затем, если буква X; найдена, формируется кодовое слово, первым битом которого является 1, а следующие п бит представляют собой код номера позиции, в которой находится эта буква. В случае отсутствия буквы х, в "окне", первым битом кодирующего ее слова является 0, за

которым следует кодовое обозначение этой буквы. После передачи слова (О,'х;'), буква х; записывается в свободную позицию "окйа".

В отличие от И1, в алгоритме И2 номера позиций "окна" (1) кодируются словами равномерного кода, длина п которого равна Г1ой(\У+ 1)]. Так как количество позиций "окна" равно легко видеть, что одно слово используемого кода остается незадействованным. Оно применяется при кодировании тех букв сообщения, которые отсутствуют в "окне". Таким образом, в методе И2, если буква XI есть в "окне", она кодируется кодовым словом, соответствующим номеру содержащей ее позиции "окна". В случае отсутствия буквы X; в "окне", соответствующее ей кодовое слово состоит из следующих двух подслов :

• незадействованное кодовое слово, используемого равномерного кода;

• кодовое обозначение буквы X;.

При использовании модифицированных интервальных методов И1 и И2, сжатие данных осуществляется за счет того, что наиболее часто встречающиеся в сообщении буквы попадут в "окно" и, следовательно, будут кодироваться короткими кодовыми словами, длина 1 которых определяется равенством

1 = +1 в методе И1

и

1 = Г1(^(ЛУ + 1)1 о методе И2.

В § 4.4 исследовалась возможность аппаратной реализации рассмотренных во второй главе словарных методов сжатия А1, А2, АЗ и Б1 и быстрого адаптивного словарного кода (БСК), предложенного в совместной работе И.В.Перцева, Б.Я.Рябко и автора диссертации [17], разработанного специально для аппаратной реализации. Кроме того, исследовались исходный интервальный метод и построенные на его основе новые модификации И1 и И2.

В ходе экспериментального исследования эффективности перечисленных выше интервальных и словарных методов были вычислены коэффициенты сжатия, обеспечиваемые этими методами при использовании небольшого объема оперативной памяти. Кроме коэффициентов сжатия, экспериментально была определена средняя

скорость кодирования и декодирования исследуемыми алгоритмами.

Исследование интервальных методов показало, что модификации И1 и И2 интервального метода превосходят его исходный вариант и по степени сжатия, и по скорости кодирования и декодирования. Однако, в целом, эффективность интервальных алгоритмов невысока. Поэтому их можно рекомендовать лишь в том случае, когда под реализацию метода сжатия отведен очень маленький объем оперативной памяти или (и) когда данные очень избыточны.

В табл.3 приведены коэффициенты сжатия, обеспечиваемые наиболее быстрыми из исследованных словарных методов. Результаты показывают, что наилучшего сжатия позволяет достигнуть алгоритм АЗ, описанный в гл.2.

Быстрый адаптивный словарный код (БСК), предложенный в [17], основанный на использовании адаптивного словаря, несколько уступает методу АЗ по коэффициенту сжатия. Однако, среди исследованных алгоритмов у него самая высокая скорость кодирования и декодирования, превосходящая, в среднем, скорость метода Б1 в 1.5 раза, а метода АЗ - в 3 раза (точные значения средней скорости кодирования и декодирования не приводятся, т.к. эта величина существенно зависит от быстродействия

Таблица 3 .

Средние значения коэффициентов сжатия (%), полученных при кодировании основных типов файлов словарными кодами

Объем Тип файлов Среднее

словаря Метод Тексты Докумен- Тексты Объектные по всем

или сжатия программ тация на на модули файлам

"окна" английском русском

АЗ 52 54 60 76 61

512 БСК 47 54 64 85 63

Б1 59 60 63 77 65

АЗ 48 50 56 75 57

1024 БСК 43 51 60 85 60

Б1 59 59 62 78 64

АЗ 41 47 51 75 53

2048 БСК 41 48 57 85 58

Б1 50 50 54 79 58

компьютера, тогда как отношение скоростей остается практически постоянным).

В ЗАКЛЮЧЕНИИ сформулированы основные научные результаты диссертационной работы.

1. Проведен сравнительный анализ известных классов последовательных методов сжатия данных. Показано, что наиболее эффективными при неискажающем кодировании цифровых сообщений являются словарные методы.

2. Разработаны структуры данных, эффективые при реализации словарных методов сжатия. Предлагаемые структуры данных базируются на алгоритме дерева поиска "бор". Кроме того, проведено сравнение с ранее применявшимися структурами данных.

3. Построено множество кодовых слов, обозначенное в работе через Фб. На основе экспериментальных исследований показано, что это множество дает максимальную степень сжатия при использовании его в словарных методах.

4. Разработаны методы сжатия данных, высокоэффективные при аппаратной реализации.

5. Построены словарные методы, высокоэффективные при сжатии основных типов данных (программы на различных языках программирования, документация на английском языке, тексты на русском языке и объектные модули).

ПУБЛИКАЦИИ

1.Рябко Б.Я., Ситняковская Е.И. Методы увеличения пропускной способности цифровых линейных трактов // Всесоюзн. НТК "Исследование и разработка современных радиоэлектронных элементов и устройств": Рига: Рижский политехи. ин-т,1990. - Тез. докл. - с.51.

2. Рябко Б.Я., Ситняковская Е.И. Анализ методов неискажающего сжатия компьютерных файлов // Всесоюзн. НТК "Исследование и разработка современных радиоэлектронных элементов и устройств": Рига: Рижский политехи, ин-т, 1990.- Тез. докл. -с.61.

3. Рябко Б.Я., Ситняковская Е.И. Сравнительный анализ методов сжатия компьютерных файлов // 2 Всесоюзн. НТК "Проблемы и

перспективы развития цифровой звуковой техники": Ленинград: Ин-г радиовещательного приема и акустики им. А.С.Попова, 1990,- Тез. докл. - с.42.

4. Рябко Б.Я., Ситняковская Е.И. Анализ эффективности универсальных методов сжатия компьютерных файлов, передаваемых по информационным сетям // Международн. НТК "Проблемы функционирования информационных сетей": Новосибирск: НЭИС, 1991,- Тез. докл. -т.2, с.270.

5. Ситняковская Е.И. Сравнительный анализ посимвольных универсальных методов сжатия файлов // Региональн. НТК "Актуальные проблемы моделирования на ЭВМ систем передачи информации": Омск: Омский политехи, ин-т, 1990.- Тез. докл.

6. Ситняковская Е.И. Анализ побуквенных методов кодирования информации при сжатии компьютерных файлов // 3-я НТК молодых ученых, специалистов и студентов "Передача, прием и обработка сигналов в радиосвязи": Москва-Ростов: Московское гор.правление ВНТО РЭС им. А.С.Попова, 1990,- Тез. докл. -с.48.

7. Ситняковская Е.И. Сравнительный анализ и экспериментальное исследование методов сжатия класса LZ // Межрегиональн. НТК "Обработка сигналов в системах двусторонней телефонной связи": Москва-Суздаль, 1992.- Тез. докл. -с.23.

8. Перцев И.В., Ситняковская Е.И. Эффективные методы сжатия данных для реализации в виде интегральных микросхем // Межрегион. НТК "Обработка сигналов в системах двусторонней телефонной связи": Москва-Суздаль, 1992.- Тез. докл. -с.22.

9. Ситняковская Е.И. Экспериментальное исследование эффективности универсальных кодов из класса LZ // Всероссийск. НТК "Цифровые системы передачи городских и сельских сетей связи - ЦСП - 92": Новосибирск: НЭИС, 1992,- Тез. докл. -с. 17.

10. Ситняковская Е.И. Скорость и эффективность универсальных LZ - кодов // Российск. НТК, посвященная Дню радио: Новосибирск: НЭИС, 1993,- Тез. докл.- с.121.

11. Sitnyakovskaya E.I. The research of new universal LZ codes // International congress on computer systems and applied mathematics, S.-Peterburg, 1993,- p.239.

12. Ситняковская Е.И. Методы повышения эффективности универсальных кодов // 2-ой международн. симпозиум "Вероятностные

модели и обработка случайных сигналов и полей": Тернополь, 1993.-Доклады: т.З-ч.2-е.23-30.

13. Ситняковская Е.И. Построение оптимальных побуквенных кодов для словарных методов сжатия текстовых файлов // Российск. НТК "Информатика и проблемы телекоммуникаций" : Новосибирск, 1994.-Тез. докл. - с.12.

14. Sitnyakovskaya E.I. Selection of Optimum Codes for the Lempel-Ziv Methods Class // Proceedings IEEE Int. Workshop on Information Theory, Moscow, Russia. - 1994. - p.93.

15. Ситняковская Е.И. Разработка оптимальных побуквенных кодов для последовательных словарных методов сжатия данных //3-я Межрегиональная НТК и выставка интеллектуальных продуктов "Обработка сигналов в системах двусторонней телефонной связи": Москва-Пушкино, 1994.- Тез. докл. - с.92 - 95.

16. Бах O.A., Курапова Е.В., Перцев И.В., Ситняковская Е.И. Оценка эффективности методов сжатия данных при аппаратной реализации // 2-я международная НТК "Актуальные проблемы электронного приборостроения ЛПЭП - 94": Новосибирск, НГТУ, 1994.- Тезисы докладов: т.2. - с.68 - 70.

17. Перцев И.В., Рябко Б.Я., Ситняковская Е.И. Эффективные методы сжатия данных для аппаратной реализации // Сб. науч. тр. уч. институтов связи "Анализ и моделирование сигналов и ситем связи", 1994. - №159. - с. 45-49.

Лицензия №020475, октябрь 1992г. Подписано к печати 03.04.95г. Объем 1.3 изд.л. Формат А4. Заказ №71. Тираж 100 экз.

Отпечатано на ризографе СибГАТИ. 630102, Новосибирск, ул.Кирова, 86.