Содержание главы

Методы сжатия информации

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

Одним из простейших способов сжатия является метод RLE (Run Length Encoding — кодирование с переменной длиной строки). Действие метода RLE заключается в поиске одинаковых пикселей в одной строке. Если в строке, допустим, имеется 3 пикселя белого цвета, 21 — черного, затем 14 — белого, то применение RLE дает возможность не запоминать каждый из них (38 пикселей), а записать как 3 белых, 21 черный и 14 белых в первой строке.

Метод сжатия LZW (Lempel Ziv & Welch) разработан в 1978 году Лемпелом и Зивом и доработан позднее в США. Сжимает данные путем поиска одинаковых последовательностей (они называются фразами) во всем файле. Выявленные последовательности сохраняются в таблице, им присваиваются более короткие маркеры (ключи). Так, если в изображении имеются наборы из розового, оранжевого и зеленого пикселей, повторяющиеся 50 раз, LZW выявляет это, присваивает данному набору отдельное число (например, 7) и затем сохраняет эти данные 50 раз в виде числа 7. Метод LZW, как и RLE, лучше действует на однородных участках, свободных от шума цветов. Он действует гораздо лучше, чем RLE, при сжатии произвольных графических данных, но процесс кодирования и распаковки происходит медленнее.

Метод сжатия Хаффмана (Huffman) разработан в 1952 году и применяется как составная часть в ряде других схем сжатия, таких как LZW, Дефляция, JPEG. В методе Хаффмана берется набор символов, который анализируется, чтобы определить частоту каждого символа. Затем для наиболее часто встречающихся символов используется представление в виде минимально возможного количества битов. Например, буква "е" чаще всего встречается в английских текстах. Применяя кодировку Хаффмана, можно представить "е" всего лишь двумя битами (1 и 0) вместо восьми битов, необходимых для представления буквы "е" в кодировке ASCII.

Метод сжатия CCITT (International Telegraph and Telephone Committie) был разработан для факсимильной передачи и приема. Является более узкой версией кодирования методом Хаффмана. CCITT Group 3 идентичен формату факсовых сообщений, CCITT Group 4 — формат факсов, но без специальной управляющей информации.

Содержание главы