Подавление нулей

Методы группового кодирования

Лекция 9. Сжатие без потерь

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

Существует две основные разновидности сжатия данных: сжатие без потерь и сжатие с потерями. При сжатии без потерь (lossless compression) информация не теряется и распакованные данные идентичны исходным несжатым данным. Как было показано в главе 19, эффективность сжатия без потерь ограничена энтропи­ей источника данных. В случае сжатия с потерями (lossy compression) распако­ванные данные могут быть приемлемым приближением (в соответствии с некото­рым критерием точности) к исходным несжатым данным. Например, при сжатии изображений или видеоданных критерий может заключаться в том, что для чело­веческого глаза распакованное изображение неотличимо от оригинала.

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

Групповое кодирование (run-length encoding) представляет собой простой метод сжатия данных без потерь, довольно эффективный для сжатия текста. Этот метод также находит применение в факсимильном сжатии.

Один из старейших и простейших методов сжатия данных известен как подавление нулей (null suppression), или подавление пробелов (blank suppression). Он до сих пор применяется в протоколе уровня передачи данных BISYNC (Binary Synchronous Communications protocol — двоичный синхронный протокол связи) IBM 3780. В тексте или потоке символов часто встречаются длинные строки пробелов или нулей. В методе подавления нулей передатчик сканирует данные в поиске строк пробелов и заменяет каждую такую строку двухсимвольным кодом. Код состоит из специального управляющего символа, за которым следует число пробелов в стро­ке. Например, пусть имеется код с символами пробела, обозначенными знаком b:

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

Такая схема позволяет сделать короче все строки из трех и более пробелов. В методе подавления нулей приемник ищет в потоке входящих символов спе­циальный символ, используемый для индикации удаленных пробелов. Получив такой символ, получатель понимает, что следующий символ содержит количество удаленных пробелов. По этой информации может быть восстановлен исходный поток данных. При том что метод подавления нулей представляет собой крайне примитивную форму сжатия данных, его преимущество заключается в том, что он очень легко реализуется. Кроме того, выигрыш даже от применения такого простого метода может быть значительным. Как сообщалось в [113], выигрыш от перехода с прото­кола IBM 2780 на протокол 3780 в ряде компьютерных конфигураций составил от 30 до 50%, и все это благодаря данному методу сжатия данных.