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

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

Перцев Игорь Владимирович

УДК 621.391

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

Специальность 05.12.02. - Системы и устройства передачи

информации по каналам связи.

АВТОРЕФЕРАТ

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

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

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

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

наук, профессор Рябко Б.Я.

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

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

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

Ведущее предприятие: институт систем информатики

им. А.П. Ершова СО РАН

Защита диссертации состоится УС^С-ОС/^кф 995 года

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

С диссертацией можно ознакомится в библиотеке академии.

Автореферат разослан »/У» /¿¿ЬАгД^ 1995 года.

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

к.т.н., профессор /, Крук Б.И.

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

Актиалъностъ темы. Объем данных, передаваемых по линиям связи и хранимых на внешних носителях информации в цифровом виде, постоянно возрастает, причем известно, что большая часть таких данных высоко избыточна. Значительное уменьшение избыточности и, следовательно, объема передаваемых и хранимых данных достигается за счет неискажающего или "бесшумного" сжатия данных (под неискажающим понимается метод сжатия, обеспечивающий точное восстановление исходных данных после декодирования). Так, например, для текстовых файлов коэффициент сжатия (отношение объема закодированных данных к объему исходных) достигает 25-30%, т.е. размер файла после сжатия в 3-4 раза меньше размера исходного файла.

Исследования в области неискажающего сжатия информации активно ведутся как у нас в стране (Бабкин В.Ф., Кричевский P.E., Рябко Б.Я., Трофимов В.К., Штарьков Ю.М. и другие), так и за рубежом (Elias Р., Lempel А., Rissanen J., Ziv J. и многие другие). Бурное же развитие вычислительной техники и микроэлектроники позволяет программно и аппаратно реализовывать все более сложные и эффективные методы сжатия.

Основными критериями оценки неискажающих методов сжатия являются:

• коэффициент сжатия,

• скорость кодирования и декодирования информации,

• объем памяти, требуемый для реализации метода.

Причем, как правило, улучшение одного из этих показателей приводит к ухудшению других.

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

сжатия данных. В последнее время появились описания алгоритмов сжатия, построенных на других принципах, например, арифметическом коде, который предложили Р. Elias, J. Rissanen и др. Особый интерес арифметические коды стали представлять после того, как Б.Я. Рябко был разработан алгоритм их быстрой реализации ; при сохранении той же эффективности сжатия.

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

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

1. Разработан алгоритм эффективной реализации быстрого арифметического кода.

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

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

4. Разработаны методы экономного распределения оперативной памяти кодера и декодера.

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

6. Предложен и реализован универсальный метод кодирования с быстрообновляющимся словарем, требующий небольшой объем памяти. Данный метод обеспечивает быстрое кодирование - декодирование при достаточно высокой степени сжатия.

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

Методы исследования. Для проведения исследований в диссертационной работе использовались теория информации и

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

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

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

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

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

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

5. Разработаны и реализованы быстрые методы сжатия информации, использующие как фиксированный, так и адаптивный к изменениям статистики источника словарь, превосходящие в 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 статьи.

Личный вклад автора. Основные научные положения и результаты получены автором самостоятельно.

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

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

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

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

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

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех разделов, заключения и приложения. Содержание работы изложено на 141 страницах машинописного текста, иллюстрировано 45 рисунками и 8 таблицами. Список литературы содержит 99 наименований. В приложении на 36 страницах приведены тексты программ, реализующих предложенные в работе методы сжатия данных.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ '

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

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

Сформулирована основная задача при кодировании для источника — построение быстрого и эффективного кода, работающего при ограниченном объеме памяти.

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

Статические методы предназначены для сжатия данных с известной статистической структурой. Коротко описаны два метода данного класса — Шеннона и Гилберта - Мура. Показано, что статические коды, обладая высокой скоростью кодирования - декодирования, позволяют эффективно сжимать только сообщения, порождаемые источниками с известной статистикой, из-за чего их практическое применение ограничено.

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

Также рассмотрены коды Лемпела - Зива (или словарные коды). В таких кодах, в отличие от побуквенных, кодовые слова ставятся в соответствие не отдельным символам источника, а последовательностям символов.

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

шиеся последовательности символов источника. В случае заполнения словаря до окончания процесса кодирования он или обновляется (полностью либо частично), или процесс кодирования продолжается на основе сформированного словаря.

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

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

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

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

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

В том случае, если статистика источника заранее не известна или меняется в процессе кодирования, необходимо переходить от статического арифметического кодирования к универсальному. Таким образом, для источника с алфавитом А = {а/, а2, ар ..., а^}, где к — размер алфавита, вероятности р(а1), р(а2), р(а^), ..., р(а^) заранее не известны и их оценки вычисляются в процессе кодирования.

Во второй главе описаны алгоритмы быстрого умножения вероятностей символов в кодируемом блоке и метод быстрого вычисления суммарных вероятностей символов в кодируемом блоке,

позволяющие существенно увеличить скорость арифметического кодирования.

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

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

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

Для увеличения общего количество узлов дерева был предложен следующий метод распределения памяти. Количество символов источника, вероятности которых хранятся в узлах кодового дерева, берется меньшим, чем алфавит источника ЛГС < /г. Причем в узлах дерева хранятся наиболее вероятные символы. В том случае, если вероятность кодируемого символа хранится в данном узле, он кодируется на основе этой вероятности модифицированным блоковым арифметическим кодом, описанным выше. Если же нет, кодирование производится по следующему алгоритму. В каждом узле дерева, кроме вероятностей наиболее часто" встречаемых символов источника, хранится вероятность специального символа. Этот специальный символ (обозначим его а») используется .в том случае, если кодируемого символа источника в узле нет. Тогда код символа источника

состоит из двух частей: кода специального символа а« и записи символа источника в исходном, незакодированном виде.

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

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

Так, например, в результате кодирования источника с алфавитом А = {а1% а2}, порождающего последовательность символов Д/ а/ а1 а2 а2 аи максимальной длине "ветви" кодового дерева й = 2 кодовое дерево примет следующий вид:

2

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

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

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

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

Описана структура данных для организации кодового дерева, построенная на основе хеш-таблицы. Узлы в этой таблице упорядочены по неубыванию значений хеш-функций, что позволяет быстро производить поиск, добавление и удаление информации. Поиск начинается со строки, номер которой совпадает со значением хеш-функции. Для вычисления значений хеш-функции используется формула:

H(Nyn, щ) = (Nyn + di ■ Hash_k) mod M, где Nyn — номер предыдущего узла кодового дерева, а, — символ источника, Hash_k — константа, используемая при хешировании, mod — операция вычисления остатка от деления, М — размер хеш-таблицы, то есть количество строк в ней. Автором разработан алгоритм, позволяющий быстро добавлять и удалять узлы и соответствующую им информацию в хеш-таблице, что существенно влияет

на скорость кодирования и декодирования. Пример добавления нового узла в таблицу приведен на следующем рисунке.

№ Н

0

1 1 узел 1

2

3

4 узел 4 > 4 4 узел 2

5 5 узел 3

6

7

узел 2

№ Н № Н

0 0

1 1 узел 1 1 1 узел 1

2 2

3 3

4 4 узел 4 4 4 узел 4

5 5 узел 3 \ 5 4 узел 2

6 \ - 6 5 узел 3

7 / 7

5 узел 3

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

Основная часть памяти, требуемой для реализации разработанного метода сжатия, используется для хранения оценок вероятностей символов источника в каждом узле кодового дерева. Поэтому от эффективной организации структуры данных для хранения этих оценок в значительной мере зависят характеристики метода сжатия в целом. Данная структура данных также построена на основе хеш-таблицы. Было предложено использовать динамическое распределение оперативной памяти — при создании нового узла кодового дерева память можно выделять не сразу для максимального числа

символов в узле Nc, а для меньшего количества — Ыс/2 или Лгс./4. И лишь когда число символов источника, встретившихся в данном узле, превысит это количество, объем выделяемой узлу памяти удваивается. Такой подход позволяет за счет уменьшения среднего объема памяти, выделяемой под узел кодового дерева, увеличить общее число узлов. За счет этого эффективность сжатия, обеспечиваемая методом, существенно возрастает.

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

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

символов источника позволили увеличить эффективность сжатия арифметического кода на 25-30%.

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

Таблица 1.

Коэффициенты сжатия (отношение длины закодированного файла к длине исходного) для различных методов сжатия.

разработанный метод АШ 2.41а Рк^р 2.04е 1СЕ 1.14 ЬНА 2.13 ШАгс 1.13 ИАИ 1.52

Текстовый файл на русском языке, 660 кбайт. 38% 42% 42% 49% 45% 49% 41%

Текстовый файл на английском языке, 800 кбайт. 25% 26% 26% 31% 29% 31% 25%

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

В первой части этой главы приводится описание системы сжатия с фиксированным словарем, заранее настроенным на статис-

тику источника, за счет чего эффективно сжимаются файлы небольшого размера. Данный метод, разработанный автором, используется в банке данных Государственной публичной научно-технической библиотеки Сибирского отделения Российской академии наук (ГПНТБ СО РАН).

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

Перейдем к краткому описанию метода. При размере алфавита источника, равном 256 символам, на запись каждого символа источника в исходном представлении требуется один байт. При кодировании исходная последовательность символов источника разбивается на блоки длиной Ь символов. Множество же всех возможных блоков длины Ь делится на две части: высоковероятную, хранимую в памяти компьютера, и маловероятную. Это разделение производится на основе исследования статистики репрезентативного набора данных с учетом зависимости между символами исходного текста, то есть вероятность блока символов оценивается с учетом того, какие символы источника ему предшествовали.

В том случае, если кодируемый блок принадлежит к высоковероятной части множества, он кодируется словом длиной один байт. В противном случае используется кодовое слово длиной Ь+1 байт, в котором первый байт, равный нулю, — признак того, что исходный блок символов не принадлежит к высоковероятной части множества, а в следующие Ь байт записывается сам кодируемый блок.

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

Разработанный метод сжатия с фиксированным словарем позволил при высокой скорости кодирования и декодирования информации вдвое уменьшить объем данных, хранимых в ГПНТБ СО РАН.

Автором также был разработан и реализован адаптивный метод сжатия, использующий быстрообновляющийся словарь (БОС). Этот метод имеет высокую скорость кодирования и декодирования при

достаточно высокой степени сжатия и использовании небольшого объема оперативной памяти компьютера.

При использовании метода БОС последовательность символов, поступающая на вход кодера, разбивается на блоки длиной от 1 до 8 символов. Эти символы затем кодируются одним или двумя байтами (размер алфавита источника считаем равным & = 256 символов, каждый символ в исходном виде представлен одним байтом).

Процесс кодирования и декодирования осуществляется с помощью постоянно обновляющегося словаря. Для организации этого словаря используется двухмерная хеш-таблица, в элементах которой хранятся блоки из 8 символов источника. Номера строк этой хеш-таблицы принимаются равными значениям хеш-функции, вычисленным по двум предыдущим символам источника а номера столбцов — значениям хеш-функции, вычисленным по двум текущим символам (см. рисунок).

0 1 Н(хг, хг+1) 15

0

1

Н(хг_2, хи)

...

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

Структура этого байта следующая: • Один бит несет информацию о том, что хранящиеся в хеш-таблице по адресу М[Ы1,Ы2] символы совпали с кодируемыми символами источника.

• Следующие три бита содержат сведения о количестве кодируемых символов, совпавших с символами в хеш-таблице.

• в оставшиеся четыре бита записывается номер столбца хеш-таблицы Ы2, по которому при декодировании будут восстановлены закодированные символы.

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

В том случае, когда количество кодируемых символов источника, совпавших с символами, хранящимися в хеш-таблице по адресу М[М1,Ы2], оказалось равным нулю, кодирование происходит по алгоритму, описываемому ниже.

Весь алфавит из 256 символов источника разбивается на две части — высоковероятную и маловероятную. Высоковероятная часть алфавита из 127 символов хранится в постоянно обновляющейся таблице №2 (для текстовых файлов количество практически встречаемых различных символов обычно не превосходит этого числа).

Если кодируемый символ принадлежит к высоковероятной части алфавита и хранится в таблице №2, ему будет соответствовать однобайтовое кодовое слово следующей структуры:

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

• В остальные семь бит записывается номер кодируемого символа в таблице №2.

В случае отсутствия кодируемого символа и в таблице №2 ему будет соответствовать двухбайтовое кодовое слово следующей структуры:

• Первый байт несет информацию о том, что кодируемый символ отсутствует как в хеш-таблице по адресу М[МрЫ2], так и в таблице №2.

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

Разработанный метод БОС сравнивался по скорости кодирования с наиболее быстрым методом из класса Ъ2 — кодом Лемпела-Зива-Бунтона-Борелло, работающим со словами фиксированной длины. Оба метода были реализованы в виде программ на языке Си

и сравнивались на представительном наборе файлов на персональном компьютере 486 0X4-100. Скорость сжатия метода, построенного на алгоритме Лемпела-Зива-Бунтона-Борелло, была равна 150-170 килобайт в секунду. Метод БОС же обеспечивает кодирование со скоростью 320-350 килобайт в секунду при примерно равном коэффициенте сжатия.

В заключении сформулированы следующие основные научные результаты:

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

2. Получен метод эффективного предсказания распределения вероятностей текущих символов источника по нескольким предыдущим.

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

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

5. Построена система сжатия информации с фиксированным словарем. Ее использование в банке данных ГПНТБ СО РАН позволило вдвое уменьшить объем хранимых данных при высокой скорости кодирования и декодирования.

6. Предложен и реализован универсальный код с быстрообновляю-щимся словарем, использующий ограниченный объем оперативной памяти. Данный метод обеспечивает достаточно высокую степень сжатия и в 2-3 раза превосходит известные методы по скорости кодирования и декодирования.

Публикации по теме диссертации.

1. Звонкович В.Р., Перцев И.В., Рябко Б.Я., Ситняковский И.В.

Бесшумное сжатие многоканального телефонного сигнала ИКМ // Сборник научных трудов учебных заведений связи. Ленинград, 1990. - с.178-186.

2. Звонкович В.Р., Перцев И.В., Рябко Б.Я., Ситняковский И.В.

Неискажакмцее сжатие телефонного сигнала на многоканальных линиях связи // Проблемы передачи информации. 1991, Том 27, Вып. 4. - с. 105-109.

3; Курапова Е.В., Перцев И.В. Быстрые методы неискажающего сжатия информации в библиотечных базах данных // 4-я НТК молодых ученых, специалистов и студентов "Передача, прием и обработка сигналов в радиотехнических системах и устройствах": Ростов, 1991. - Тез. докл. - с.43.

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

5. Перцев И.В., Рябко Б.Я. Быстрый универсальный метод сжатия компьютерных файлов // Всероссийская научно-техническая конференция "Цифровые системы передачи городских и сельских сетей связи ЦСП-92". Новосибирск, ноябрь, 1992. - с.33.

6: Курапова Е.В., Перцев И.В., Рябко Б.Я. Эффективные методы сжатия информации для банков знаний // Всероссийская НТК "Цифровые системы передачи городских и сельских сетей связи ЦСП-92": Новосибирск, НЭИС, 1992. - Тез. докл. - с.32.

7. Курапова Е.В., Перцев И.В., Рябко Б.Я. Построение систем сжатия библиографической информации для передачи по линиям связи и хранения в библиотечных банках данных // Синтез и анализ алгоритмов оптимальной обработки сигналов: Сб. науч. тр. уч. заведений связи. - С.-Петербург, 1993. - с.96-101.

8. Перцев И.В. Высокоскоростные методы сжатия цифровой информации // Российская научно-техн. конференция, посвященная Дню Радио: Тез.докл. Новосибирск, апрель, 1993.- с.110.

9. Pertsev I.V. Effective method of data compression on basis of modified arithmetic codes // International congress on computer systems and applied mathematics. St.Petersburg, july, 1993.- p.237.

10. Перцев И.В. Эффективное сжатие данных при помощи модифицированных блоковых кодов // Информационные технологии и распознавание образов: Сб. науч. трудов международного симпозиума "Информационные модели и обработка случайных сигналов и полей". Т.З, 4.1, Львов-Харков-Тернополь, 1993. с.31.

11. Перцев И.В. Эффективный алгоритм реализации быстрых неискажающих кодов // Российская научно - техн. конференция "Информатика и проблемы телекоммуникации": Тез. докл. Новосибирск, апрель, 1994.- с.13.

12. Pertsev I.V. New algorithms of memory allocation Enhancing the arithmetic code efficiency // Seventh Joint Swedish-Russian international Workshop on Information Theory: St.-Petersburg, 1995. - Proceedings - pp. 189-190.

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

14. Перцев И.В. Разработка метода сжатия информации на основе быстрого арифметического кодирования // Межрегиональная конференция "Обработка сигналов в системах двусторонней телефонной связи" Москва, 1994,- с.89-91.

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

16. Перцев И.В. Сравнительный анализ эффективности быстрых арифметических кодов и кодов класса LZ // Межрегиональная конференция "Обработка сигналов в системах двусторонней телефонной связи" Москва, 1995. с.57-59.

17. Pertsev I.V. Efficient Algorithm for Implementation of Fast Non-distoring codes // IEEE International Workshop on Information Theory: Proceedings - Moscow, july, 1994. - p.p.77-78.

18. Перцев И.В. Оптимизация начального распределения вероятностей в арифметических кодах // Международная научно-техническая конференция "Информатика и проблемы телекоммуникаций". Новосибирск, 1995.

19. Перцев И.В. Новые алгоритмы распределения оперативной памяти, увеличивающие эффективность арифметического кодирования // Пятый международный семинар "Распределенная обработка информации": - Академгородок, Новосибирск, октябрь, 1995.

Лицензия №020475, октябрь 1992 г. Подписано к печати 01.11.95 г. Изд.л. 1,0. Формат А4. Заказ № 19бТираж 100 экз.

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