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

РГБ ОД

1 5 ЛЕН 1996

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

Курапова Елена Викторовна

УДК 621.391

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

Специальность 05.12.13 - Системы и устройства

радиотехники и связи

АВТОРЕФЕРАТ

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

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

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

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

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

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

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

Ведущее предприятие: Институт космических исследований РАН

Защита диссертации состоится "40 " ае-кЮ^А^ 1996 г. в 4О часов па заседании специализированного совета Д 118.07.01 в Сибирской Государственной Академии Телекоммуникаций и Информатики по адресу: 630102, г. Новосибирск, ул. Кирова, 86.

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

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

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

к.т.н., профессор

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

Актуальность темы Проблема эффективного неискажа-ющего сжатия данных привлекает внимание многих исследователей в нашей стране и за рубежом. Наиболее важные результаты были получены в работах отечественных ученых В.Ф.Бабкина, Р.Е.Кричевского, Б.Я.Рябко, В.К.Трофимова, Ю.М.Штарькова и американских исследователей Е.Н.Гилберта, Я.Зива, А.Лемпела, Э.Ф.Мура, Дж.Риссанена, Д.Хаффмена, П.Элайеса и других. В настоящее время существует множество различных методов сжатия данных, находящих широкое применение при архивации данных в компьютерных сетях, системах передачи данных, на цифровых линиях связи. Бурное развитие элементной базы дает возможность реализовывать все более сложные методы и алгоритмы кодирования и декодирования. Поэтому постоянно ведется активная разработка новых классов кодов, позволяющих добиться повышения эффективности систем связи.

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

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

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

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

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

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

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

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

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

А. Построение систем сжатия для библиотек программ на основных языках программирования.

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

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

Научная новизна резилътатов работы

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

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

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

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

Практическая ценность результатов

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

2. Впервые разработаны системы сжатия для библиотек программ, написанных на основных языках программирования,

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

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

Внедрение результатов работы Основные результаты диссертации получены в рамках работы по проекту № 96-01-00052 "Асимптотически оптимальные коды для стационарных источников информации", финансируемому Российским фондом фундаментальных исследований, и в процессе выполнения НИР Министерства связи РФ "АСПЕКТ-НЭИС" по теме "Разработка высокоскоростных методов неискажающего сжатия данных".

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

Результаты диссертации используются в учебном процессе при чтении курсов "Информатика", "Программирование", "Структуры и алгоритмы обработки данных в ЭВМ" в СибГАТИ.

Апробация работы и публикации

Основные результаты работы докладывались и обсуждались на Всероссийских и международных конференциях. Среди них: 4-я НТК молодых ученых, специалистов и студентов "Передача, прием и обработка сигналов в радиотехнических системах и устройствах" (Ростов-иа-Дону, 1991), Всероссийская НТК "Цифровые системы передачи городских и сельских сетей связи ЦСП-92" (Новосибирск, 1992), International Congress on Computer Systems and Applied Mathematics (St.-Petersburg, 1993), Международный симпозиум "Информационные модели и обработка случайных сигналов и полей" (Тернополь, 1993), Российская НТК "Информатика и проблемы телекоммуникации" (Новосибирск, 1994,1996), IEEE International Workshop on Information Theory (Moscow, 1994), Межрегиональные конференции "Обработка сигналов в системах двусторонней телефонной связи" (Москва, 1994, 1995),

Международная НТК "Информатика и проблемы телекоммуникаций" (Новосибирск, 1995), Seventh Joint Swedish-Russian International Workshop on Information Theory (St.-Petersburg, 1995).

По теме диссертации опубликовано 15 печатных работ, в том числе 2 статьи, подготовлены 2 отчета о НИР.

Основные положения. выносимые на защити:

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

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

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

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

5. Применение подхода, основанного на описании синтаксической структуры данных, для библиотек программ на основных языках программирования дает возможность создавать высокоэффективные системы сжатия текстов программ, на 10-30% превосходящие известные универсальные методы по степени сжатия.

Стриктира и объем работы

Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложений. Содержание работы изложено на 167 страницах машинописного текста, иллюстрировано 32 рисунками и 23 таблицами. Список литературы содержит 98 наименований. В приложении на 26 страницах приведены таблицы и тексты программ, реализующих предложенную в работе схему построения систем сжатия данных.

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

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

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

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

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

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

статистическую структуру кодируемых данных. Это позволяет адаптивным методам эффективно сжимать данные с неизвестной заранее статистической структурой. К наиболее распространенным методам относятся адаптивный код Хаффмеиа, частотный код, словарные коды Лемнела-Зива. В работе дается краткая сравнительная характеристика этих кодов.

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

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

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

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

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

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

• данные полностью известны до построения системы кодирования;

• известна только представительная выборка.

Для кодирования источников с известной статистикой предлагается использовать разработанный подход к задаче сжатия небольших файлов, основанный на описании данных при помощи формальных грамматик. Поясним на простом примере основной принцип использования грамматического описания при сжатии данных. Рассмотрим структуру данных библиотечного банка, содержащего рефераты печатных работ. Каждой книге или статье соответствует реферат, хранящийся в памяти компьютера. Объем такого реферата 1-3 Килобайта. Каждый реферат состоит из трех частей:

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

• текст реферата на английском языке;

• текст реферата на русском языке.

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

английскому тексту реферата, а состояние С - русскому тексту реферата:

А -> ОА 11А |... | 9АI аВ IЬВ I... I гВ, В -> аВ | ЬВ I... | гВ | аС 16С |... |яС, С -» аС 16С |... | яС I ОА 11А I... 19А.

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

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

• описание данных с помощью формальной грамматики;

• исследование статистической структуры исходных данных;

• выбор кодов, обеспечивающих наилучшее сжатие данных;

• разработка программ кодирования и декодирования.

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

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

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

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

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

Для описания выбранной схемы кодирования и грамматического анализа рассмотрим сообщение х^.-.х^х;... из алфавита А = { а1( а2) ..., а^ }. Пусть необходимо закодировать символ X;, и пусть 8;„1 - состояние грамматики, описывающей источник после кодирования символов х^г.-.х;^. В нашем алгоритме определяющей будет пара (З^х^), характеризующая текущее состояние грамматики и зависимость кодируемого символа от определенного предыдущего символа. При кодировании очередного символа X; используются оценки условных вероятностей Р(х;/(5;.1,х;.1)), вычисленные при статистическом анализе исходных данных. При этом в оперативной памяти компьютера должна хранится таблица, в которой каждому символу X; соответствует частота его появления после символа х;.1 в состоянии

я/.

Далее во второй главе рассматриваются быстрые побуквенные коды, используемые для источников с известной статистикой. Применение этих кодов объясняется тем, что во многих системах сжатия (например, для распределенных банков данных и знаний) требуется высокая скорость кодирования и декодирования, т.к. процесс декодирования данных не должен замедлять работу пользователя. Основная идея метода построения быстрых побуквенных кодов заключается в следующем. Все символы исходного алфавита размера к упорядочиваются по убыванию частот их появления в тексте. Затем в алфавите выделяется подмножество из М наиболее часто встречающихся символов, где М представимо в виде 2п-1. Тогда любой символ из М наиболее вероятных символов алфавита кодируется коротким словом из п бит, представляющих двоичную запись номера этого символа в упорядоченной последовательности. Остальные маловероятные символы кодируются более длинной комбинацией из (п+г) бит, включающей п-битовую двоичную запись числа М и г-битовую двоичную запись кодируемого символа равномерным кодом, где г^ПоЯгкТ Схема этого кода, названного кодом типа а, приведена на рис.1.

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

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

Высоковероятные | N | символы п бит

Маловероятные , М , , символ символы п бит г бит

а) код типа а

Три самых вероятных символа

Высоковероятные символы

Маловероятные символы

N = (00,01,10)

2 бита

2 бита

,1 ,1м

N-3

п бит М

2 бита п бит

J 1_

символ

г бит

б) код типа р

Один самый вероятный

символ Высоковероятные символы

Маловероятные символы

0

1 бит 1

1 бит

N-1

п бит М

1 бит п бит в) код типа у

символ

г бит

Два самых вероятных , N Г (00,01)

символа 2 бита

Высоковероятные 1 1 1°| , N-2

символы 2 бита п бит

Маловероятные I1 I1.. символ

символы 2 бита г бит

г) код типа 8 Рис. 1. Схемы кодов

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

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

• текстов программ на Бейсике,

• данных библиотечного банка,

• управляющих программ базы данных FOXBASE.

В процессе исследований определялись коэффициенты сжатия этих данных указанными адаптивными методами с использованием грамматического описания и без него. Полученные результаты показывают, что практически во всех случаях применение формальной грамматики значительно улучшает сжатие данных адаптивными методами. Использование арифметических кодов и словарных кодов из класса Лемпела-Зива в сочетании с грамматическим описанием структуры сообщений позволяет в среднем на. 10-30% увеличить степень сжатия данных по сравнению с обычным применением этих адаптивных методов. Например, использование арифметического кода для библиотечных данных позволяет уменьшить длину файла до 27% по отношению к исходной длине файла. Применение этого же метода совместно с грамматикой из двух состояний позволяет уменьшить длину файла до 14%, т.е. увеличить степень сжатия данных на 45% по сравнению с исходным арифметическим кодом.

В четвертой главе описывается построение систем сжатия для текстов программ на основных языках программирования (Ассемблер, Бейсик, Паскаль). Вначале обосновывается выбор класса грамматик, используемого при сжатии текстов программ. Это 1Х( к)-грамматики, применение которых объясняется особенностями структуры программ: в них, как правило, существуют различные цепочки символов, рассматриваемые как единые смысловые элементы. Это команды, стандартные функции, типы данных и другие ключевые слова. Если названия ключевых слов (например, команд) в программе состоят не более, чем из к символов, то ЬЬ(к)-грамматика позволяет при кодировании просмотреть текст на несколько символов вправо от кодируемого символа, чтобы идентифицировать команду языка программирования. Затем при кодировании последовательность символов команды рассматривается как единый элемент и кодируется 1 одним кодовым словом, что позволяет повысить эффективность сжатия текстов программ. Подчекнем, что грамматический анализ производится за один просмотр текста, что дает возможность не замедлять процесс кодирования и декодирования.

Далее в четвертой главе рассмотрены системы сжатия текстов программ, разработанные для основных языков программирования (Ассемблер, Бейсик, Паскаль) в соответствии с приведенной выше схемой построения систем сжатия данных для источников с известной статистикой. Структура программ описывалась с помощью грамматик класса Щк), при этом величина к определялась максимальной длиной ключевого слова конкретного языка программирования. На этапе анализа статистики исходных данных оценивались вероятности различных символов и команд в разных состояниях грамматики. При этом были исследованы два случая анализа статистической структуры текстов программ:

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

• по всей библиотеке кодируемых программ.

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

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

Таблица 2

Коэффициенты сжатия текстов программ на Бейсике (%)

Название файла Длина файла в байтах Разработанная система Стандартные архиваторы

ARJ PKZIP

Ы.ЬаБ 1378 35.9 47.6 47

Ьг.Ьав 1503 34.8 48.9 48

ЬЗ.Ьая 3154 40.4 47.6 47

Ь4.Ьа5 1995 38.8 46.7 46

Ьб.Ьав 1567 39.1 51.8 52

Ьб.Ьаэ 1593 39.2 46.3 46

Ь7.Ьаз 1684 40.6 52.3 52

Ь8.ЬаБ 1457 37.7 51.5 51

ЬЭ.Ьав 1518 33.6 46.2 46

ЫО.Ьав 1107 38.3 51.8 52 -—1

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

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

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

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

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

В методе, реализованном в системе с автоматическим выбором состояний грамматики, применяются кодовые слова с длиной, кратной 8 битам, что обеспечивает высокую скорость кодирования и декодирования. При кодировании вся исходная последовательность символов разбивается на слова длиной 3 байта. Множество всех таких слов предварительно делится на две части - высоковероятные слова и маловероятные. Это разбиение производится программным путем на основе исследования статистики репрезентативного набора данных, при этом учитывается зависимость между символами исходного текста. В случае, если кодируемое слово принадлежит высоковероятной части множества, оно кодируется кодовой комбинацией длиной в 1 байт. В противном случае используется кодовое слово длиной А байта, в котором первый байт содержит 0 -признак того, что исходное слово не закодировано, а следующие 3 байта - само исходное слово (см. рисунок).

Высоковероятные слова j

1 байт

Маловероятные слова ^ исходное слово

1 байт 3 байта

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

• номер строки таблицы (0 определяется путем хеширования двух предыдущих символов кодируемой последовательности;

• номер столбца таблицы (3) вычисляется путем хеширования трех текущих символов кодируемой последовательности;

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

• в противном случае просматривается соседний элемент таблицы. Если и в нем нет кодируемого слова, то выводится комбинация длиной 4 байта, содержащая 0 и исходное слово.

Пример хеш-таблицы приведен на следующем рисунке.

0 1 • • • • • • Ш\ • • 255

0 ] . " : * •

ш . Г;7 *' 'Г ¿ас

• • • * С- * -

* * ! сЛа

• • •

255

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

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

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

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

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

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

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

ПУБЛИКАЦИИ

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

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

3. Курапова Е.В. Технология построения систем сжатия данных, описываемых формальными грамматиками // Российская НТК, посвященная Дню Радио: Новосибирск, НЭИС, 1993. - Тез. докл. - с.120.

4. Kurapova E.V. Data Compression Using Formal Grammars // International Congress on Computer Systems and Applied Mathematics: St.-Petersburg, 1993. - Abstracts - p.236.

5. Курапова E.B. Использование формальных грамматик при построении систем сжатия данных // Информационные технологии и распознавание образов: Сб. науч. трудов международного симпозиума "Информационные модели и обработка случайных сигналов и полей". - Львов-Харьков-Тернополь, 1993. - т.З. - ч.1. -с.113-118.

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

7.Курапова Е.В. Формальные грамматики как средство, повышающее эффективность сжатия данных // Российская НТК "Информатика и проблемы телекоммуникаций": Новосибирск, НЭИС, 1994. - Тез. докл. - с. 13-14.

8.Kurapova E.V. Data Compression Methods Based on Formal Grammars // IEEE International Workshop on Information Theory: Moscow, 1994. - Proceedings - p.56-57.

Э.Курапова Е.В. Сжатие данных с использованием формальных грамматик // 3-я Межрегиональная конференция "Обработка сигналов в системах двусторонней телефонной связи": Москва-Пушкино, 1994. - Тез. докл. - с.96-99.

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

11.Курапова Е.В. Методы сжатия данных библиотек программ // 4-я Межрегиональная конференция "Обработка сигналов в системах двусторонней телефонной связи": Москва, 1995. - Тез. докл. -с.60-62.

12.Курапова Е.В., Рябко Б.Я. Применение формальных грамматик при кодировании источников информации // Проблемы передачи информации. - М., Наука, 1995. - т.31. - №1. - с.28-32.

13.Курапова Е.В. Эффективные методы сжатия программ на основных языках программирования // Международная НТК "Информатика и проблемы телекоммуникаций": Новосибирск, СибГАТИ, 1995. - Тез. докл. - т.1. - с.81-83.

14.Kurapova E.V. Efficient Compression of Program Texts in Programming Languages // Seventh Joint Swedish-Russian International Workshop on Information Theory: St.-Petersburg, 1995. - Proceedings - pp.167-169.

15.Курапова Е.В. Методы сжатия информации для банков данных и знаний, основанные на использовании формальных грамматик // Российская НТК "Информатика и проблемы телекоммуникаций": Новосибирск, СибГАТИ, 1996. - Тез. докл. - т. 1. - с.64-65.

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

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