Введение к работе
Актуальность темы Проблема эффективного неискажа-ющего сжатия данных привлекает внимание многих исследователей в нашей стране и за рубежом. Наиболее важные результаты были получены в работах отечественных ученых В.Ф.Бабкина, Р.Е.Кричсвского, Б.Я.Рябко, В.К.Трофимова, Ю.М.Штарькова и американских исследователей Е.Н.Гилберта, Я.Зива, А.Лемпела, Э.Ф.Мура, Дж.Риссанена, Д.Хаффмена, П.Элайеса и других. В настоящее время существует множество различных методов сжатия данных, находящих широкое применение при архивации данных в компьютерных сетях, системах передачи данных, на цифровых линиях связи. Бурное развитие элементной базы дает возможность реализовывать все более сложные методы и алгоритмы кодирования и декодирования. Поэтому постоянно ведется активная разработка новых классов кодов, позволяющих добиться повышения эффективности систем связи.
Современные системы сжатия данных основаны на двух различных подходах к процессу кодирования: статическом (неадаптивном) и адаптивном. Статические методы предназначены для сжатия данных с известной статистической структурой и дают значительный эффект только в случае достаточно точно известной статистики исходных данных. Адаптивные методы эффективно сжимают и данные с неизвестной заранее статистической структурой. Однако у этих методов есть два существенных недостатка: во-первых, они позволяют эффективно сжимать только файлы достаточно большой длины (десятки килобайт и выше). Во-вторых, адаптивные методы не позволяют учесть имеющиеся сведения о структуре данных для повышения эффективности сжатия.
Ситуация, когда необходимо сжимать файлы небольшого обьема, и(или) имеются некоторые сведения о структуре сообщений, встречается довольно часто. Эта задача возникает при обработке файлов в различных банках данных, при передаче сообщений электронной почты, при хранении текстов программ на разных языках программирования в библиотеках программ и т.п. Наиболее актуально эта задача стоит перед удаленными пользователями банков данных и знаний, которые получают информацию по сетям
связи. Увеличение объемов данных и рост числа пользователей приводит к их объединению в крупные информационные сети, такие как INTERNET. Одной из основных задач этих сетей является быстрое обеспечение каждого пользователя необходимой ему информацией, которая часто является небольшой по объему (одна или несколько страниц текста). Таким образом, несмотря на огромные объемы данных, которыми располагают эти сети, при обмене информации по запросам пользователей часто передаются именно небольшие файлы.
Однако прямое использование статических или адаптивных кодов не позволяет достигнуть значительного эффекта в этом случае. Поэтому исследуется новый подход, сочетающий достоинства статических и адаптивных методов сжатия данных. Он основан на описании исходных данных с помощью формальных грамматик и позволяет разрабатывать методы сжатия для данных, при кодировании которых эффективность известных адаптивных и неадаптивных кодов сравнительно невысока.
. Цель работы Целью настоящей диссертационной работы является разработка систем, методов и алгоритмов сжатия информации для увеличения эффективности систем связи распределенных банков данных и знаний.
Задачи исследования Для достижения указанной цели в работе решаются следующие основные задачи:
1. Разработка методов сжатия данных, представленных в виде
небольших по объему файлов, для повышения эффективности
систем связи распределенных банков данных и знаний.
2. Разработка эффективных методов и алгоритмов для
кодирования источников с известной и неизвестной статистикой,
позволяющих учитывать имеющиеся сведения о синтаксической
структуре данных.
3. Построение систем сжатия информации для передачи и
хранения сообщений в распределенных банках данных и знаний.
А. Построение систем сжатия для библиотек программ на основных языках программирования.
5. Разработка автоматизированной схемы построения систем сжатия данных для использования в системах передачи и хранения информации.
Методы исследования В процессе исследований были использованы основные положения теории передачи информации и теории кодирования дискретных источников сообщений.
Научная новизна резильтатов работы
1. Разработан класс высокоскоростных методов для сжатия
информации в распределенных банках данных и знаний,
позволяющих в среднем вдвое уменьшить объем хранимой
информации и увеличить пропускную способность каналов связи при
обработке данных в режиме реального времени.
2. Предложены методы сжатия данных, использующие
сведения о структуре сообщений, для случая, когда статистика
источника известна заранее, и для случая неизвестной статистики.
-
Построены эффективные методы сжатия данных для текстов программ на основных языках программирования, обеспечивающие значительное сжатие данных при достаточно простой реализации.
-
Разработана автоматизированная схема построения систем сжатия данных, использование которой дает возможность быстро и без значительных трудозатрат создавать эффективные системы сжатия для различных типов данных.
Практическая ценность резильтатов
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%
превосходящие известные универсальные методы по степени сжатия.
Структура и объем работы
