ВУЗ:
1.6. СЖАТИЕ ДАННЫХ*
При записи или передаче данных часто бывает полезно (а иногда просто необходимо) сократить размер обрабатывае-
мых данных. Технология, позволяющая достичь этой цели, называется сжатием данных. В этом разделе рассмотрены неко-
торые общие методы сжатия данных, а также конкретные приемы, разработанные специально для сжатия изображения.
Универсальные методы сжатия данных. Существует множество методов сжатия данных, каждый из которых харак-
теризуется собственной областью применения, в которой он дает наилучшие или, наоборот, наихудшие результаты. Метод
кодирования длины серий (run-length encoding) дает наилучшие результаты, если сжимаемые данные состоят из длинных по-
следовательностей одних и тех же значений. В сущности, такой метод кодирования как раз и состоит в замене подобных по-
следовательностей кодовым значением, определяющим повторяющееся значение и количество его повторений в данной се-
рии. Например, для записи кодированной информации о том, что битовая последовательность состоит из 253 единиц, за ко-
торыми следуют 118 нулей и еще 87 единиц, потребуется существенно меньше места, чем для перечисления всех этих 458
бит.
В некоторых случаях информация может состоять из блоков данных, каждый из которых лишь немного отличается от
предыдущего. Примером могут служить последовательные кадры видеоизображения. Для таких случаев используется метод
относительного кодирования (relative encoding). Данный подход предполагает запись отличий, существующих между после-
довательными блоками данных, вместо записи самих этих блоков, т.е. каждый блок кодируется с точки зрения его взаимо-
связи с предыдущим блоком.
Еще один метод сжатия данных предполагает применение частотно-зависимого кодирования (frequency-dependent en-
coding), при котором длина битовой комбинации, представляющей элемент данных, обратно пропорциональна частоте ис-
пользования этого элемента. Такие коды входят в группу кодов переменной длины (variable-length codes), т.е. элементы дан-
ных в этих кодах представляются битовыми комбинациями различной длины. Если взять английский текст, закодированный
с помощью частотно-зависимого метода, то чаще всего встречающиеся символы (е, t, а, i) будут представлены короткими
битовыми комбинациями, а те знаки, которые встречаются реже (z, q, х), – более длинными битовыми комбинациями. В ре-
зультате мы получим более короткое представление всего текста, чем при использовании обычного кода, подобного Unicode
или ASCII. Построение алгоритма, который обычно используется при разработке частотно-зависимых кодов, приписывают
Дэвиду Хоффману (David Huffman), поэтому такие коды часто называются кодами Хоффмана (Huffman codes). Большинство
используемых сегодня частотно-зависимых кодов является кодами Хоффмана.
Хотя обсуждавшиеся выше методы кодирования были представлены как технологии сжатия данных общего назначе-
ния, тем не менее, каждый из них имеет собственную сферу применения. В противоположность этому, системы, основанные
на использовании метода кодирования Lempel-Ziv (названного в честь его создателей Абрахама Лемпеля (Abraham Lempel) и
Джэкоба Зива (Jacob Ziv), действительно являются системами сжатия данных общего назначения. Многие пользователи
Internet (глава 3), несомненно, уже встречали и даже использовали такие универсальные программы сжатия данных произ-
вольного типа, как zip и unzip, в которых применяется технология Lempel-Ziv.
Системы кодирования по методу Lempel-Ziv используют технологию кодирования с применением адаптивного словаря
(adaptive dictionary encoding). В данном контексте термин "словарь" означает набор строительных блоков, из которых созда-
ется сжатое сообщение. Если сжатию подвергается английский текст, то строительными блоками могут быть символы алфа-
вита. Если потребуется уменьшить размер данных, которые хранятся в компьютере, то компоновочными блоками могут
стать нули и единицы. В процессе адаптивного словарного кодирования содержание словаря может изменяться. Например,
при сжатии английского текста может оказаться целесообразным добавить в словарь окончание ing и артикль the. В этом
случае место, занимаемое будущими копиями окончания ing и артикля the, может быть уменьшено за счет записи их как
одиночных ссылок вместо сочетания из трех разных ссылок. Системы кодирования по методу Lempel-Ziv используют изо-
щренные и весьма эффективные методы адаптации словаря в процессе кодирования (или сжатия). В частности, в любой мо-
мент процесса кодирования словарь будет состоять из тех комбинаций, которые уже были закодированы (сжаты).
В качестве примера давайте рассмотрим, как можно выполнить сжатие сообщения с использованием конкретной систе-
мы метода Lempel-Ziv, известной как LZ77. Процесс начинается практически с переписывания начальной части сообщения,
однако в определенный момент осуществляется переход к представлению будущих сегментов с помощью триплетов, каж-
дый из которых будет состоять из двух целых чисел и следующего за ними одного символа текста. Каждый триплет описы-
вает способ построения следующей части сообщения. Например, пусть распакованный текст имеет следующий вид (симво-
лы греческого алфавита здесь использованы для того, чтобы данному примеру не придавался никакой определенный смысл):
αβααβρβ (5, 4, α)
Строка αβααβρβ является уже распакованной частью сообщения. Для того чтобы разархивировать остальной текст со-
общения, необходимо сначала расширить строку, присоединив к ней ту часть, которая в ней уже встречается (рис. 1.19).
Первый номер в триплете указывает, сколько символов необходимо отсчитать в обратном направлении в строке, чтобы най-
ти первый символ добавляемого сегмента.
α β α α β ρ β
а)
α β α α β ρ β
б)
α β α α β ρ β α α β ρ
в)
α β α α β ρ β α α β ρ α
г)
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »
