Алгоритмы сжатия

Алгоритм JPEG

Данный Алгоритм сжатия используются и предназначен для сжатия картинок то есть растровых изображений(растровое изображение - это когда каждуй пиксель на картинки задаётся числом которое представляет собой номер цвета в текущей палитре) растровое изображение хранится в формате BMP. Поэтому любая картинка представляет собой массив пикселей например Эта девушка Лена не что иное как двухмерный массив пикселей В паскале это выглядит так 
Pixels: Array [1..256,1..256] of Byte 
Цвет каждого пикселя кодируется Байтом(байт это восемь бит- а бит это либо ноль либо один поэтому один байт это 256 в десятичной системе ).Так есть массив который содержит полную информацию о картинке картинка размером 256*256*256 - третье измерение это цвет.Размер этой картинки, 65536 байт- ровно 64 Кбайта. Много это или мало? Давайте подумаем ...при средней скарости интернета в России 2Kb/sec Вы смогли бы полюбоваться этой девушкой лишь спустя 32 секунды. Подумайте и о том что интернет в России не бесплатный.Может ли картинка занимать меньше байт -ответ. Да А теперь я расскажу что я делаю с картинкой что бы она занимала меньше места то есть о том как я их могу сжимать. 
 

 


В алгоритме JPEG исходное изображение представляется двумерной матрицей размера N*N, элементами которой являются цвет или яркость пиксела. Упаковка значений матрицы выполняется за три этапа, представленных на рисунке 1.
 

Рис. 1. Этапы работы алгоритма JPEG

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

Дискретное косинус преобразование

Основным этапом работы алгоритма является
дискретное косинусное преобразование (ДКП),
представляющее собой разновидность преобразования
Фурье. Оно позволяет переходить от пространственного представления
изображения к его спектральному представлению и обратно.
Что нужно сделать на первом этапе первом этапе ?
Следует создать ДКП матрицу, используя такую формулу :
        DCT   = 1/sqr(N), если i=0
           ij
        DCT   = sqr(2/N)*cos[(2j+1)*i*3.14/2N], если i > 0
           ij
        N = 8,  0 < i < 7 , 0 < j < 7

в результате имеем:

      |.353553  .353553  .353553  .353553  .353553  .353553  .353553  .353553|
      |.490393  .415818  .277992  .097887 -.097106 -.277329 -.415375 -.490246|
      |.461978  .191618 -.190882 -.461673 -.462282 -.192353  .190145  .461366|
DCT = |.414818 -.097106 -.490246 -.278653  .276667  .490710  .099448 -.414486|
      |.353694 -.353131 -.354256  .352567  .354819 -.352001 -.355378  .351435|
      |.277992 -.490246  .096324  .416700 -.414486 -.100228  .491013 -.274673|
      |.191618 -.462282  .461366 -.189409 -.193822  .463187 -.460440  .187195|
      |.097887 -.278653  .416700 -.490862  .489771 -.413593  .274008 -.092414|

например, нам нужно сжать следующий фрагмент изображения:

      | 95  88  88  87  95  88  95  95|
      |143 144 151 151 153 170 183 181|
      |153 151 162 166 162 151 126 117|
IMG = |143 144 133 130 143 153 159 175|
      |123 112 116 130 143 147 162 189|
      |133 151 162 166 170 188 166 128|
      |160 168 166 159 135 101  93  98|
      |154 155 153 144 126 106 118 133|

      |-33 -40 -40 -41 -33 -40 -33 -33|
      | 15  16  23  23  25  42  55  53|
      | 25  23  34  38  34  23  -2 -11|
IMG = | 15  16   5   2  15  25  31  47|
      | -5 -16 -12   2  15  19  34  61|
      |  5  23  34  38  42  60  38   0|
      | 32  40  38  31   7 -27 -35 -30|
      | 26  27  25  16  -2 -22 -10   5|
                                                     T
вот формула, по которой производится ДКП: RES*IMG*DCT
                                                               T
для начала нужно посчитать промежуточную матрицу: TMP = IMG*DCT
      |-103   -3    1    2    4    0   -1    5|
      |  89  -40   12   -2   -7    5    1    0|
      |  57   31  -30    6    2    0    5    0|
TMP = |  55  -28   24    1    0   -8    0    0|
      |  32  -60   18   -1   14    0   -8    1|
      |  84  -11  -37   17  -24    4    0   -4|
      |  19   81  -16  -20    8   -3    4    0|
      |  22   40   11  -22    8    0   -3    2|

затем умножаем ее на ДКП матрицу: RES = TMP*DCT

      | 91   3  -5  -6   2   0   1|
      |-38 -57   9  17  -2   2   2|
      |-80  58   0 -18   4   3   4|
RES = |-52 -36 -11  13  -9   3   0|
      |-86 -40  44  -7  17  -6   4|
      |-62  64 -13  -1   3  -8   0|
      |-16  14 -35  17 -11   2  -1|
      |-53  32  -9  -8  22   0   2|

Этап Квантования

На этом этапе мы посчитаем матрицу квантования, используя этот псевдо код:

for i:=0 to 8 do
 for j:=0 to 8 do
  Q[i,j] = 1+((1+i+j)*q);

где q - это коэффициент качества, от него зависит степень потери качества
сжатого изображения
для q = 2 имеем матрицу квантования:

     | 3  5  7  9 11 13 15 17|
     | 5  7  9 11 13 15 17 19|
     | 7  9 11 13 15 17 19 21|
Q =  | 9 11 13 15 17 19 21 23|
     |11 13 15 17 19 21 23 25|
     |13 15 17 19 21 23 25 27|
     |15 17 19 21 23 25 27 29|
     |17 19 21 23 25 27 29 31|

теперь нужно каждое число в матрице квантования разделить на число в
соответствущей позиции в матрице RES, в результате получим:
     | 30   0   0   0   0   0   0   0|
     | -7   8   1   1   0   0   0   0|
     |-11   6   0   1   0   0   0   0|
A =  | -5  -3   0   0   0   0   0   0|
     | -7  -3   2   0   0   0   0   0|
     | -4   4   0   0   0   0   0   0|
     | -1   0   1   0   0   0   0   0|
     | -3   1   0   0   0   0   0   0|

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

     +----+----+----+----+----+----+----+----+
     |  1 |  2 |  6 |  7 | 15 | 16 | 28 | 29 |
     +----+----+----+----+----+----+----+----+
     |  3 |  5 |  8 | 14 | 17 | 27 | 30 | 43 |
     +----+----+----+----+----+----+----+----+
     |  4 |  9 | 13 | 18 | 26 | 31 | 42 | 44 |
     +----+----+----+----+----+----+----+----+
     | 10 | 12 | 19 | 25 | 32 | 41 | 45 | 54 |
     +----+----+----+----+----+----+----+----+
     | 11 | 20 | 24 | 33 | 40 | 46 | 53 | 55 |
     +----+----+----+----+----+----+----+----+
     | 21 | 23 | 34 | 39 | 47 | 52 | 56 | 61 |
     +----+----+----+----+----+----+----+----+
     | 22 | 35 | 38 | 48 | 51 | 57 | 60 | 62 |
     +----+----+----+----+----+----+----+----+
     | 36 | 37 | 49 | 50 | 58 | 59 | 63 | 64 |
     +----+----+----+----+----+----+----+----+

итак у нас получилась последовательность:
30 0 -7 -11 8 0 0 1 6 -5 -7 -3 0 1 0 0 0 1 0 -3 -4 -1 4 2 0 0 0 0
0 0 0 0 0 0 0 -3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Этап Вторичного Сжатия

 Самым распространенным
методом вторичного сжатия является метод Хаффмана и его разновидности.

Метод Хаффмана.


Сжатие Хаффмана - статистический метод сжатия,
который уменьшает среднюю длину кодового слова для символов алфавита.
Код Хаффмана является примером кода, оптимального в случае,
когда все вероятности появления символов в сообщении - целые отри-
цательные степени двойки. Код Хаффмана может быть построен по 
следующему алгоритму:

1.Выписываем в ряд все символы алфавита в порядке возрастания
или убывания вероятности их появления в тексте;

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

3.Прослеживаем путь к каждому листу дерева помечая направление 
к каждому узлу (например, направо - 1, налево - 0). 

Поясним создание дерева с использованием иллюстраций :

A       B       C       D       E
10      5       8       13      10

B       C       A       E       D
5       8       10      10      13

A       E       BC      D
10      10      13      13

BC      D       AE
13      13      20

AE      BCD
20      26

AEBCD
46

Таким образом, построено дерево

Теперь, если в тексте встречается, например, символ "d" , то вместо того, чтобы выделять этому символу байт, после сжатия символ займет всего 2 бита (01). 

Форматы графических файлов

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

Вызывает интерес та часть процесса, где происходит преобразование данных в растровый массив. Существует несколько форматов файлов растровой графики, и каждый формат предусматривает собственный способ кодирования информации о пикселах и другой присущей компьютерным изображениям информации. Именно поэтому программа Paint, поставляемая в комплекте ОС Windows 95, совместима с BMP-файлами, но не может считывать файлы формата GIF. Создатели программы Paint наделили ее способностью декодировать графическую информацию, хранящуюся в формате BMP, но распространенный формат GIF для нее остается таким же чуждым, как язык суахили для среднего техасца.

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

Распространенные форматы файлов растровой графики

Формат Макс. число бит/пиксел Макс. число цветов Макс. размер изображения, пиксел Методы сжатия Кодирование нескольких изображений
BMP 24 16'777'216 65535 x 65535 RLE* -
GIF 8 256 65'535 x 65535 LZW +
JPEG 24 16'777'216 65535 x 65535 JPEG -
PCX 24 16'777'216 65535 x 65535 RLE -
PNG 48 281'474'976'710'656 2'147'483'647 x 2 147 483 647 Deflation (вариант LZ77) -
TIFF 24 16'777'216 всего 4'294'967'295 LZW, RLE и другие* +
* Сжатие выполняется факультативно.

Файлы BMP

Формат файла BMP (сокращенно от BitMaP) - это "родной" формат растровой графики для Windows, поскольку он наиболее близко соответствует внутреннему формату Windows, в котором эта система хранит свои растровые массивы. Для имени файла, представленного в BMP-формате, чаще всего используется расширение BMP, хотя некоторые файлы имеют расширение RLE, означающее run length encoding (кодирование длины серий). Расширение RLE имени файла обычно указывает на то, что произведено сжатие растровой информации файла одним из двух способов сжатия RLE, которые допустимы для файлов BMP-формата.

В файлах BMP информация о цвете каждого пиксела кодируется 1, 4, 8, 16 или 24 бит (бит/пиксел). Числом бит/пиксел, называемым также глубиной представления цвета, определяется максимальное число цветов в изображении. Изображение при глубине 1 бит/пиксел может иметь всего два цвета, а при глубине 24 бит/пиксел - более 16 млн. различных цветов.
 

Структура файла BMP
Заголовок файла растровой графики (14 байт)
Сигнатура файла BMP (2 байт)
Размер файла (4 байт)
Не используется (2 байт)
Не используется (2 байт)
Местонахождение данных растрового массива (4 байт)
Информационный заголовок растрового массива (40 байт)
Длина этого заголовка (4 байт)
Ширина изображения (4 байт)
Высота изображения (4 байт)
Число цветовых плоскостей (2 байт)
Бит/пиксел (2 байт)
Метод сжатия (4 байт)
Длина растрового массива (4 байт)
Горизонтальное разрешение (4 байт)
Вертикальное разрешение (4 байт)
Число цветов изображения (4 байт)
Число основных цветов (4 байт)
Таблица цветов (длина изменяется от 8 до 1024 байт)
Собственно данные растрового массива (длина переменная)

На приведенной схеме показана структура типичного BMP-файла, содержащего 256-цветное изображение (с глубиной 8 бит/пиксел). Файл разбит на четыре основные раздела: заголовок файла растровой графики, информационный заголовок растрового массива, таблица цветов и собственно данные растрового массива. Заголовок файла растровой графики содержит информацию о файле, в том числе адрес, с которого начинается область данных растрового массива. В информационном заголовоке растрового массива содержатся сведения об изображении, хранящемся в файле, например, его высоте и ширине в пикселах. В таблице цветов представлены значения основных цветов RGB (красный, зеленый, синий) для используемых в изображении цветов. Программы, считывающие и отображающие BMP-файлы, в случае использования видеоадаптеров, которые не позволяют отображать более 256 цветов, для точной цветопередачи могут программно устанавливать такие значения RGB в цветовых палитрах адаптеров.

Формат собственно данных растрового массива в файле BMP зависит от числа бит, используемых для кодирования данных о цвете каждого пиксела. При 256-цветном изображении каждый пиксел в той части файла, где содержатся собственно данные растрового массива, описывается одним байтом (8 бит). Это описание пиксела не представляет значений цветов RGB, а служит указателем для входа в таблицу цветов файла. Таким образом, если в качестве первого значения цвета RGB в таблице цветов файла BMP хранится R/G/B=255/0/0, то значению пиксела 0 в растровом массиве будет поставлен в соответствие ярко-красный цвет. Значения пикселов хранятся в порядке их расположения слева направо, начиная (как правило) с нижней строки изображения. Таким образом, в 256-цветном BMP-файле первый байт данных растрового массива представляет собой индекс для цвета пиксела, находящегося в нижнем левом углу изображения; второй байт представляет индекс для цвета соседнего справа пиксела и т. д. Если число байт в каждой строке нечетно, то к каждой строке добавляется дополнительный байт, чтобы выровнять данные растрового массива по 16-бит границам.

Не все файлы BMP имеют структуру, подобную показанной на схеме. Например, файлы BMP с глубиной 16 и 24 бит/пиксел не имеют таблиц цветов; в этих файлах значения пикселов растрового массива непосредственно характеризуют значения цветов RGB. Также могут различаться внутренние форматы хранения отдельных разделов файла. Например, информация растрового массива в некоторых 16 и 256-цветных BMP-файлах может сжиматься посредством алгоритма RLE, который заменяет последовательности идентичных пикселов изображения на лексемы, определяющие число пикселов в последовательности и их цвет. В Windows допускается работа с BMP-файлами стиля OS/2, в которых используются различные форматы информационного заголовка растрового массива и таблицы цветов.

Файлы PCX

PCX стал первым стандартным форматом графических файлов для хранения файлов растровой графики в компьютерах IBM PC. На этот формат, применявшийся в программе Paintbrush фирмы ZSoft, в начале 80-х гг. фирмой Microsoft была приобретена лицензия, и затем он распространялся вместе с изделиями Microsoft. В дальнейшем формат был преобразован в Windows Paintbrush и начал распространяться с Windows. Хотя область применения этого популярного формата сокращается, файлы формата PCX, которые легко узнать по расширению PCX, все еще широко распространены сегодня.

Файлы PCX разделены на следующие три части: заголовок PCX, данные растрового массива и факультативная таблица цветов. 128-байт заголовок PCX содержит несколько полей, в том числе поля размера изображения и числа бит для кодирования информации о цвете каждого пиксела. Информация растрового массива сжимается с использованием простого метода сжатия RLE; факультативная таблица цветов в конце файла содержит 256 значений цветов RGB, определяющих цвета изображения. Формат PCX первоначально был разработан для адаптеров CGA- и EGA-дисплеев и в дальнейшем был модифицирован для использования в адаптерах VGA и адаптерах истинных цветов. Кодирование цвета каждого пиксела в современных изображениях PCX может производиться с глубиной 1, 4, 8 или 24 бит.

Файлы TIFF

Если PCX - один из самых простых для декодирования форматов растровой графики, то TIFF (Tagged Image File Format, формат файлов изображения, снабженных тегами) - один из самых сложных. Файлы TIFF имеют расширение TIFF. Каждый файл начинается 8-байт заголовком файла изображения (IFH), важнейший элемент которого - каталог файла изображения (Image File Directory, IFD) - служит указателем к структуре данных. IFD представляет собой таблицу для идентификации одной или нескольких порций данных переменной длины, называемых тегами; теги хранят информацию об изображении. В спецификации формата файлов TIFF определено более 70 различных типов тегов. Например, тег одного типа хранит информацию о ширине изображения в пикселах, другого - информацию о его высоте. В теге третьего типа хранится таблица цветов (при необходимости), а тег четвертого типа содержит сами данные растрового массива. Изображение, закодированное в файле TIFF, полностью определяется его тегами, и этот формат файла легко расширяется, поскольку для придания файлу дополнительных свойств достаточно лишь определить дополнительные типы тегов.

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

Еще одна сложность заключается в том, что файл TIFF может содержать несколько изображений, каждому из которых сопутствуют собственный IFD и набор тегов. Данные растрового массива в файле TIFF могут сжиматься с использованием любого из нескольких методов, поэтому в надежной программе для чтения файлов TIFF должны быть средства распаковки RLE, LZW (LempelZivWelch) и несколько других. Ситуацию еще больше ухудшает то обстоятельство, что пользование программами распаковки LZW должно осуществляться в соответствии с лицензионным соглашением с фирмой Unisys Corp. на право пользования алгоритмом LZW и часто за плату. В результате даже самые лучшие программы считывания TIFF нередко "сдаются", когда сталкиваются со сжатым по методу LZW изображением.

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

Файлы GIF

Большинство ведущих специалистов-графиков, имеющих дело с алгоритмом LZW, сталкиваются с аналогичными юридическими проблемами при использовании популярного межплатформенного формата файлов растровой графики GIF (Graphics Interchange Format - формат обмена графическими данными, произносится "джиф"), разработанного компанией CompuServe. Обычно для имени файлов GIF используется расширение GIF, и тысячи таких файлов можно получить в CompuServe.

Структура файла GIF зависит от версии GIF-спецификации, которой соответствует файл. В настоящее время используются две версии, GIF87a и GIF89a. Первая из них проще. Независимо от номера версии, файл GIF начинается с 13-байт заголовка, содержащего сигнатуру, которая идентифицирует этот файл в качестве GIF-файла, номер версии GIF и другую информацию. Если файл хранит всего одно изображение, вслед за заголовком обычно располагается общая таблица цветов, определяющая цвета изображения. Если в файле хранится несколько изображений (формат GIF, аналогично TIFF, позволяет в одном файле кодировать два и больше изображений), то вместо общей таблицы цветов каждое изображение сопровождается локальной таблицей цветов.

В файле GIF87a вслед за заголовком и общей таблицей цветов размещается изображение, которое может быть первым из нескольких располагаемых подряд изображений. Каждое изображение состоит из 10-байт описателя изображения, расположенной вслед за ним локальной таблицы цветов и битов растрового массива. Для повышения эффективности использования памяти данные растрового массива сжимаются с помощью алгоритма LZW.

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

Основные достоинства GIF заключаются в широком распространении этого формата и его компактности. Но ему присущи два достаточно серьезных недостатка. Один из них состоит в том, что в изображениях, хранящихся в виде GIF-файла, не может быть использовано более 256 цветов. Второй, возможно, еще более серьезный, заключается в том, что разработчики программ, использующие в них форматы GIF, должны иметь лицензионное соглашение с CompuServe и вносить плату за каждый экземпляр программы; такая ценовая политика была принята CompuServe после того, как Unisys объявила, что начнет добиваться соблюдения своих прав собственности и потребовала от тех, кто пользуется алгоритмом сжатия LZW, вносить лицензионные платежи. Возникшее в результате этого запутанное юридическое положение тормозит внедрение программистами в свои графические программы средств для работы с файлами GIF.

Файлы PNG

Формат PNG (Portable Network Graphic - переносимый сетевой формат, произносится "пинг") был разработан для замены GIF, чтобы обойти юридические препятствия, стоящие на пути использования GIF-файлов. PNG унаследовал многие возможности GIF и, кроме того, он позволяет хранить изображения с истинными цветами. Еще более важно, что он сжимает информацию растрового массива в соответствии с вариантом пользующегося высокой репутацией алгоритма сжатия LZ77 (предшественника LZW), которым любой может пользоваться бесплатно. Из-за недостатка места я не буду обсуждать внутреннюю структуру PNG. Если вы захотите больше узнать об этом формате, обратитесь к рекомендуемой в конце статьи литературе.

Файлы JPEG

Формат файла JPEG (Joint Photographic Experts Group - Объединенная экспертная группа по фотографии, произносится "джейпег) был разработан компанией C-Cube Microsystems как эффективный метод хранения изображений с большой глубиной цвета, например, получаемых при сканировании фотографий с многочисленными едва уловимыми (а иногда и неуловимыми) оттенками цвета. Самое большое отличие формата JPEG от других рассмотренных здесь форматов состоит в том, что в JPEG используется алгоритм сжатия с потерями (а не алгоритм без потерь) информации. Алгоритм сжатия без потерь так сохраняет информацию об изображении, что распакованное изображение в точности соответствует оригиналу. При сжатии с потерями приносится в жертву часть информации об изображении, чтобы достичь большего коэффициента сжатия. Распакованное изображение JPEG редко соответствует оригиналу абсолютно точно, но очень часто эти различия столь незначительны, что их едва можно (если вообще можно) обнаружить.

Процесс сжатия изображения JPEG достаточно сложен и часто для достижения приемлемой производительности требует специальной аппаратуры. Вначале изображение разбивается на квадратные блоки со стороной размером 8 пиксел. Затем производится сжатие каждого блока отдельно за три шага. На первом шаге с помощью формулы дискретного косинусоидального преобразования фуры (DCT) производится преобразование блока 8х8 с информацией о пикселах в матрицу 8x8 амплитудных значений, отражающих различные частоты (скорости изменения цвета) в изображении. На втором шаге значения матрицы амплитуд делятся на значения матрицы квантования, которая смещена так, чтобы отфильтровать амплитуды, незначительно влияющие на общий вид изображения. На третьем и последнем шаге квантованная матрица амплитуд сжимается с использованием алгоритма сжатия без потерь.

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

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

Литература для дополнительного чтения

Компьютерным форматам графических файлов посвящено несколько книг, но, по моему мнению, наиболее полезно (и хорошо изложено) второе издание энциклопедии форматов графических файлов James D.Murray and William van Ryper, Encyclopedia of Graphics File Formats, Second Edition (O'Reilly & Associates, 1996). В этой книге приводится история создания и внутренняя структура более 100 форматов файлов от Adobe Illustrator до ZBR. Удивительно, но в ней ничего не говорится о наиболее распространенных форматах BMP, однако сведения о них можно найти во множестве других источников. Разделы Further Information (Дополнительная информация) в описании каждого формата позволяют узнать, где можно получить спецификацию и другую информацию о формате, а также приводят указатели URL для сотен полезных узлов Web.

Вторую книгу Steve Rimmer, Windows Bitmapped Graphics (Windcrest/McGraw-Hill, 1993) я считаю бесценной. Помимо очень подробного описания форматов файлов GIF, PCX, WPG, TIFF, TGA и MacPaint, а также множества часто встречающихся в таких файлах ухищрений и изменений, автор приводит исходные тексты программ на языке Си для Windows, которые предназначены для чтения и вывода на экран изображений, сохраненных в каждом из перечисленных форматов. Эта книга должна занять место на полке каждого, кого интересуют распространенные компьютерные форматы графических файлов.Здесь храниться информация по форматам файлов (ttp://www.wotis.com

Другие Алгоритмы сжатия

Методы сжатия данных имеют достаточно длинную историю развития, которая началась задолго до появления первого компьютера. В этой статье будет произведена попытка дать краткий обзор основных теорий, концепций идей и их реализаций, не претендующий, однако, на абсолютную полноту. Более подробные сведения можно найти, например, в Кричевский Р.Е. [1989], Рябко Б.Я. [1980], Witten I.H. [1987], Rissanen J. [1981], Huffman D.A.[1952], Gallager R.G. [1978], Knuth D.E. [1985], Vitter J.S. [1986] и др..

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

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

 од необратимым сжатием подразумевают такое преобразование входного потока данных, при котором выходной поток, основанный на определенном формате информации, представляет, с некоторой точки зрения, достаточно похожий по внешним характеристикам на входной поток объект, однако отличается от него объемом. Степень сходства входного и выходного потоков определяется степенью соответствия некоторых свойств объекта (т.е. сжатой и несжатой информации в соответствии с некоторым определенным форматом данных), представляемого данным потоком информации. Такие подходы и алгоритмы используются для сжатия, например данных растровых графических файлов с низкой степенью повторяемости байтов в потоке. При таком подходе используется свойство структуры формата графического файла и возможность представить графическую картинку приблизительно схожую по качеству отображения (для восприятия человеческим глазом) несколькими (а точнее n) способами. Поэтому, кроме степени или величины сжатия, в таких алгоритмах возникает понятие качества, т.к. исходное изображение в процессе сжатия изменяется, то под качеством можно понимать степень соответствия исходного и результирующего изображения, оцениваемая субъективно, исходя из формата информации. Для графических файлов такое соответствие определяется визуально, хотя имеются и соответствующие интеллектуальные алгоритмы и программы. Необратимое сжатие невозможно применять в областях, в которых необходимо иметь точное соответствие информационной структуры входного и выходного потоков. Данный подход реализован в популярных форматах представления видео и фото информации, известных как JPEG и JFIF алгоритмы и JPG и JIF форматы файлов.

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

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

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

Сжатие способом кодирования серий

 Наиболее известный простой подход и алгоритм сжатия инфор-мации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последова-тельностей на один кодирующий байт и счетчик числа их повторений. Проблема всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других - некодированных последовательностей байтов. Решение про-блемы достигается обычно простановкой меток вначале кодированных цепочек. Такими метками могут быть, например, характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии и т.п.. Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF:), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже - с малым числом повторяющихся байтов в сериях.

Сжатие без применения метода RLE

 Процесс сжатия данных без применения метода RLE можно разбить на два этапа - моделирование (modelling) и собственно кодирование (encoding). Эти процессы и их реализующие алгоритмы достаточно независимы и разноплановы. и его методы

 Под кодированием обычно понимают обработку потока символов (в н

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

 Первый заключается в просмотре входного потока и построении кодирования на основании собранной статистики (при этом требуется два прохода по файлу - один для просмотра и сбора статистической информации, второй - для кодирования, что несколько ограничивает сферу применения таких алгоритмов, т.к., таким образом, исключается возможность однопроходного кодирования "на лету", применяемого в телекоммуникационных системах, где и объем данных, под час не известен, а их повторная передача или разбор может занять неоправданно много времени). В таком случае, в выходной поток записывается статистическая схема использованного кодирования. Данный метод известен как статическое кодирование Хаффмена [Huffman].

 Второй метод - метод адаптивного кодирования (adaptive coder method). Его общий принцип состоит в том, чтобы менять схему кодирования в зависимости от характера изменений входного потока. Такой подход имеет однопроходный алгоритм и не требует сохранения информации об использованном кодировании в явном виде. Адаптивное кодирование может дать большую степень сжатия, по сравнению со статическим, поскольку более полно учитываются изменения частот входного потока. Данный метод известен как динамическое кодирование Хаффмена [Huffman], [Gallager], [Knuth], [Vitter].

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

Пример:

 Пусть входной алфавит состоит из четырех символов: a, b, c, d, частоты которых в входном потоке равны, соответственно, 1/2, 1/4, 1/8, 1/8. Кодирование Хаффмена для этого алфавита задается следующей таблицей:
 
 
Cимвол Частота Входное кодирование Выходное кодирование
a 1/2 00 0
b 1/4 01 10
c 1/8 10 110
d 1/8 11 111

Например, кодом цепочки abaaacb, представленной на входе как 00 01 00 00 00 10 01, будет 0 10 0 0 0 110 10, соответственно - 14 бит на входе дали 11 бит на выходе. Кодирование по Хаффмену обычно строится и хранится в виде двоичного дерева, в "листьях" которого находятся символы, а на "ветвях" - цифры 0 или 1. Тогда уникальным кодом символа является путь от корня дерева к этому символу, по которому все 0 и 1 "собираются" в одну уникальную последовательность.

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

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

 Однако, кодирование Хаффмена имеет минимальную избыточность при условии, что каждый символ кодируется в алфавите кода символа отдельной цепочкой из двух бит - {0, 1}. Основным же недостатком данного метода является зависимость степени сжатия от близости вероятностей символов к 2 в некоторой отрицательной степени, что связано с тем, что каждый символ кодируется целым числом бит. Так при кодировании потока с двухсимвольным алфавитом сжатие всегда отсутствует, т.к. несмотря на различные вероятности появления символов во входном потоке алгоритм фактически сводит их до 1/2.

 Данная проблема, как правило, решается путем введения в алфа-вит входного потока новых символов вида 'ab', 'abc',. . . и т.п., где a, b, c - символы первичного исходного алфавита. Такой процесс называется сегментацией или блокировкой входного потока. Однако, сегментация не позволяет полностью избавиться от потерь в сжатии (они лишь уменьшаются пропорционально размеру блока), но приводит к резкому росту размеров дерева кодирования, и, соответственно, длине кода символов вторичных алфавитов. Так, если, например, символами входного алфавита являются байты со значениями от 0 до 255, то при бло-кировании по два символа мы получаем 65536 символов (различных комбинаций) и столько же листьев дерева кодирования, а при блокировании по три - 16777216! Конечно, при таком усложнении, соответственно возрастут требования и к памяти и ко времени построения дерева, а при адаптивном кодировании - и ко времени обновления дерева, что приведет к резкому увеличению времени сжатия. Напротив, в среднем, потери составят 1/2 бита на символ при отсутствии сегментации, и 1/4 или 1/6 бита соответственно при ее наличии, для блоков длиной 2 и 3 бита.

Арифметическое кодирование

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

 Предполагаемая требуемая последовательность символов, при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала [0, 1). Результат сжатия представляется как последовательность двоичных цифр из записи этой дроби. Идея метода состоит в следующем: исходный текст рассматривается как запись этой дроби, где каждый входной символ является "цифрой" с весом, пропорциональным вероятности его появления. Этим объясняется интервал, соответствующий минимальной и макси-мальной вероятностям появления символа в потоке. Поясним работу метода на примере.

 Пусть алфавит состоит из двух символов: a и b с вероятностями соответственно 3/4 и 1/4. К ак уже говорилось выше, кодирование Хаффмена не может упаковывать слова в данном алфавите, т.к. не справляется без сегментации с двухсимвольным алфавитом.

 Рассмотрим наш интервал вероятностей [0, 1). Разобьем его на части, длина которых пропорциональна вероятностям символов. В на-шем случае это [0, 3/4) и [3/4, 1). Суть алгоритма в следующем: каждому слову во входном алфавите соответствует некоторый подинтервал из интервала [0, 1) а пустому слову соответствует весь интервал [0, 1). После получения каждого следующего символа интервал уменьшается с выбором той его части, которая соответствует новому символу. Кодом цепочки является интервал, выделенный после обработки всех ее сим-волов, точнее, двоичная запись любой точки из этого интервала, а длина полученного интервала пропорциональна вероятности появления кодируемой цепочки.

 Применим данный алгоритм для цепочки "aaba":
 
 
Шаг Просмотренная цепочка Интервал
0 нет [0, 1) = [0, 1)
1 a [0, 3/4) = [0, 0.11)
2 aa [0, 9/16) = [0, 0.1001)
3 aab [27/64, 36/64) = [0.011011, 0.100100)
3 aaba [108/256, 135/256) = [0.01101100, 0.10000111)

В качестве кода можно взять любое число из интервала, получен-ного на шаге 4, например, 0.1.

 Алгоритм декодирования работает синхронно с кодирующим: начав с интервала [0, 1), он последовательно определяет символы входной цепочки. В частности, в нашем случае он вначале разделит (пропорционально частотам символов) интервал [0, 1) на [0, 0.11) и [0.11, 1). Поскольку число 0.0111 (код цепочки "aaba") находится в первом из них, можно получить первый символ: "a". Затем делим первый подынтервал [0, 0.11) на [0, 0.1001) и [0.1001, 0.1100) (пропорционально частотам символов). Опять выбираем первый, так как 0 < 0.0111 < 0.1001. Продолжая этот процесс, мы однозначно декодируем все четыре символа. Для того, чтобы декодирующий алгоритм мог определить конец цепочки, мы можем либо передавать ее длину отдельно, либо добавить к алфавиту дополнительный уникальный символ - "конец цепочки".

 При разработке этого метода возникают две проблемы: во-первых, необходима арифметика с плавающей точкой, теоретически, неограниченной точности, и, во-вторых, - результат кодирования становится известен лишь при окончании входного потока. Однако, дальнейшие исследования показывают [Rubin], что можно практически без потерь обойтись целочисленной арифметикой небольшой точности (16-32 разряда), а также добиться инкрементальной работы алгоритма: цифры кода могут выдаваться последовательно по мере чтения входного потока при ограничении числа символов входной цепочки какам либо разумным числом.

Модели входного потока

 Кодирование представляет собой лишь часть процесса упаковки. Как было показано, арифметическое кодирование имеет минимальную избыточность при заданном распределении символов входного потока. Но какой алфавит выбрать и каким соответствующим распределением воспользоваться? Ответы на эти вопросы дает построение модели входного потока, представляющей собой (см. [Rissanen], [Witten]) некоторый способ определения возможного распределения вероятностей появления каждого очередного символа в потоке. Каждого, поскольку статические модели (в которых распределение принимается неизмен-ным), в большинстве случаев, не дают максимального качества сжатия. Гораздо больший интерес представляют так называемые адаптивные модели, учитывающие текущий контекст потока. Такие модели позволяют строить быстрые однопроходные алгоритмы сжатия, не требующие априорных знаний о входном потоке данных и строящие распределение "на лету". В отдельную группу выделяют также класс "локально адаптивных" алгоритмов, отдающих при построении распределения предпочтение некоторым особенным, например, послед-ним поступившим символам.

 Возможны различные подходы к этой проблеме: простейший из них - сбор статистики появления каждого символа независимо от других (моделирование источником Бернулли, при котором вероятность появления последующего символа не зависит от того, какие символы встретились перед ним). Возможно, также и использование марковских моделей: сбор статистики появления каждого символа в которых про-изводится с учетом некоторого количества предыдущих появлявшихся символов (в марковском источнике первого порядка вероятность по-вления символа зависит только от одного последнего символа, второго - от двух и т. д.). Марковские модели могут давать более точную картину источника, однако число состояний в них больше, соответственно большим будет объем хранимых таблиц частот. Кроме того, при использовании кодирования Хаффмена они могут даже ухудшить качество сжатия, поскольку порождаемые ими вероятности обычно хуже приближаются степенями 1/2.

Кодирование сортировкой

 Здесь нельзя не упомянуть простой и достаточно эффективный метод кодирования источника с неизвестным распределением частот, известный как сжатие при помощи "стопки книг" или как сжатие сортировкой или хешированием. Метод был впервые открыт и исследован Рябко в 1980г. (см. [Рябко]), а затем переоткрыт Бентли, Слейтером, Тарьяном и Веи в 1986г. (см. [Bentley]). Идея метода состоит в следующем: пусть алфавит источника состоит из N символов с номерами 1, 2,..., N. Кодирующий алгоритм сохраняет последовательность символов, представляющую собой некоторую перестановку символов в последовательности первичного входного алфавита. При поступлении на вход некоторого символа c, имеющего в этой переставленной последовательности номер i, кодирующий алгоритм записывает код этого символа (например, монотонный код: [Кричевский], стр. 69-73). Затем поступивший символ переставляется в начало последовательности и номера всех символов, стоящих перед c, увеличиваются на 1. Таким обра-зом, наиболее часто встречающиеся символы будут переходить в начало списка и иметь более короткие коды, что в свою очередь снизит объем выходного потока при их записи в качестве символов выходно-го потока.

Двухступенчатое кодирование. Алгоритм Лемпеля-Зива

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

 В простейшем случае для кодирования в качестве входного алфавита можно использовать именно эти символы (байты) входного потока. Именно так работает метод squashing программы PKPAK (использовано статическое кодирование Хаффмена и двухпроходный алгоритм). Степень сжатия при этом относительно невелика - для текстовых файлов порядка 50%. Гораздо большей степени сжатия можно добиться при выделении из входного потока повторяющихся цепочек - блоков, и кодирования ссылок на эти цепочки с построением хеш таблиц от первого до n-го уровня.

 Метод, о котором и пойдет речь, принадлежит Лемпелю и Зиву (см. [Lempel), и обычно называется LZ-compression. Суть его состоит в следующем: упаковщик постоянно хранит некоторое количество последних обработанных символов в буфере. По мере обработки входного потока вновь поступившие символы попадают в конец буфера, сдви-гая предшествующие символы и вытесняя самые старые. Размеры этого буфера, называемого также скользящим словарем (sliding dictionary), варьируются в разных реализациях кодирующих систем. Экспериментальным путем установлено, что программа LHarc использует 4-килобайтный буфер, LHA и PKZIP - 8-ми, а ARJ - 16-килобайтный.

 Затем, после построения хеш таблиц алгоритм выделяет (путем поиска в словаре) самую длинную начальную подстроку входного потока, совпадающую с одной из подстрок в словаре, и выдает на выход пару (length, distance), где length - длина найденной в словаре подстроки, а distance - расстояние от нее до входной подстроки (то есть фактически индекс подстроки в буфере, вычтенный из его размера). В случае, если такая подстрока не найдена, в выходной поток просто копируется очередной символ входного потока.

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

 Таким образом, алгоритм Лемпеля-Зива преобразует один поток исходных символов в два параллельных потока длин и индексов в таб-лице (length + distance). Очевидно, что эти потоки являются потоками символов с двумя новыми алфавитами, и к ним можно применить один из упоминавшихся выше методов (RLE, кодирование Хаффмена или арифметическое кодирование). Так мы приходим к схеме двухступенчатого кодирования - наиболее эффективной из практически используемых в настоящее время. При реализации этого метода необходимо добиться согласованного вывода обоих потоков в один файл. Эта проблема обычно решается путем поочередной записи кодов символов из обоих потоков.

Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW)

 Данный алгоритм отличают высокая скорость работы как при упаковке, так и при распаковке, достаточно скромные требования к памяти и простая аппаратная реализация. Недостаток - низкая степень сжатия по сравнению со схемой двухступенчатого кодирования. Пред-положим, что у нас имеется словарь, хранящий строки текста и содержащий порядка от 2-х до 8-ми тысяч пронумерованных гнезд. Запишем в первые 256 гнезд строки, состоящие из одного символа, номер которого равен номеру гнезда. Алгоритм просматривает входной поток, разбивая его на подстроки и добавляя новые гнезда в конец словаря. Прочитаем несколько символов в строку s и найдем в словаре строку t - самый длинный префикс s. Пусть он найден в гнезде с номером n. Выведем число n в выходной поток, переместим указатель входного потока на length(t) символов вперед и добавим в словарь новое гнездо, содержащее строку t+c, где с - очередной символ на входе (сразу по-сле t). Алгоритм преобразует поток символов на входе в поток индексов ячеек словаря на выходе. При размере словаря в 4096 гнезд можно передавать 12 бит на каждый индекс. Каждая распознанная цепочка добавляет в словарь одно гнездо. При переполнении словаря упаковщик может либо прекратить его заполнение, либо очистить (полностью или частично).

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

От алгоритмов сжатия к форматам файлов, программам паковщи-кам и архиваторам

 Конечно, для системы сжатия информации хороший алгоритм - первоочередной, но не единственный больной вопрос. Конечному пользователю, как правило, нет дела до принципов организации функционирования и внутренней структуры используемых им программ, лишь бы работали качественно. Под качеством систем сжатия принято понимать несколько критериев, которые определяются применением при ее реализации и конкретном использовании. Так большинство применений необратимого сжатия лежит в области технологии хранения графической информации - картинки и видео, что в свою очередь локализует алгоритм в рамках одного файла для одного стандарта и характера входного потока. Однако, на практике, из-за экономии места на накопителях, возникает необходимость сжатия любого файла (в том числе и выполнимого модуля). Эту проблему решают паковщики. И, наконец, проблему сжатия нескольких файлов и даже всех файлов каталогов и дисков решают программы - архиваторы. Заметим, что в список возможных задач архиваторов входит не только сжатие/извлечение информации файлов различных форматов, но и сохранение дерева файловой системы, атрибутов файлов, их имен, некоторой комментирую-щей информации, создание самораспаковывающихся архивов, архивация с сохранением кодов циклического контроля ошибок, для гарантии абсолютного соответствия извлеченных файлов исходным файлам, шифровку данных архива и архивация с паролем, обеспечение пользователя удобным интерфейсом и др. Поэтому, архиваторы являются од-ной из самых сложных систем программ. В настоящее время, к вышеперечисленным задачам можно пожелать наличия некоторых необязательных, но удобных свойств и возможностей. Это: конфигурируемость пакета, наличие развитого оконного интерфейса, а не интерфейса командной строки, настраиваемость на определенный тип информации, сохранение параметров в файле архива, создание многотомных и/или самоизвлекающихся архивов и др.. Все это желательно иметь при малой длине файла архиватора. Между программами паковщиками и ар-хиваторами обычно не имеется принципиальных различий, однако, па-ковщики упаковывают информацию одного файла в один файл, а архиваторы образуют один файл выходного потока, который, впрочем, может быть автоматически нарезан на файлы равной длины для записи на гибкие диски. Отдельную группу составляют программы паковщики, занимающиеся сжатием выполнимых модулей и дисков. Также, упаковку данных при помощи алгоритмов сжатия используют системы резервного копирования, сжатия устройств (логических дисков MS-DOS), факс-модемные драйверы и утилиты и др.

 В настоящий момент на рынке программных продуктов и серверах программного обеспечения можно встретить достаточно большое число архивирующих и сжимающих утилит, большинство из которых доступны для некоммерческого использования. Такая доступность, прежде всего, связана с тем, что каждая, даже коммерческая, программа нуждается в обширном рынке пользователей. А, поскольку, форматы файлов архиваторов и паковщиков, даже использующих ожин и тот же алгоритм, не одинаковы, то такие программы невольно конкурируют за рынок пользователей. С этим также связано и то, что поддержка более популярных форматов файловых архивов начинает включаться в другие утилиты и программы и используемые форматы становятся стандартными форматами архивов (zip, arj, rar, ha, pak, cab и др..). Стандартный формат подразумевает исключительную легкость при поиске программы, необходимой для извлечения файлов из сжатого состояния и поддержку их другими программами (например браузерами, командными оболочками, файловыми менеджерами и т.п.).

 Нами были проанализированы более 300 архиваторов и паковщи-ков и отобраны наиболее интересные. Тесты сжатия производились на ПК Intel Pentium 233MHz с RAM 64Mb под управлением ОС MS-Windows 95 (4.0.1111). Для тестирования использовались 7 файлов с совокупным размером 8646421 байт. В архиве содержались как тексто-вые (txt 643830), графические (bmp 2233560, psd 959170), двоичные (exe 4014592, dll 352256) и мультимедийные (avi 342420, mid 100593) файлы. Архивация производилась при работе в фоновом режиме из под обо-лочки far 1.52. Для измерения времени использовалась команда time. Файлы сжимались с жесткого диска на жесткий диск. Необходимо от-метить, что в качестве опций для сжатия использовались параметры для наилучшего сжатия каждого файла, а в случае наличия у программы специальных параметров, определяющих сжатие файлов строго оп-ределенного формата, при его тестировании они также использовались. Результаты лучших экземпляров сведены нами в таблицу. Данные в нашей таблице отсортированы в порядке ухудшения коэффициента сжатия, а ratio показывает, сколько процентов объема осталось после сжатия:
 
 
Name Ver Ratio Time
ACB 2.00 30% 510s
UHARC 0.2b 30% 189s
777 0.04 34% -1
BOA 0.58 34% 410s
IMP 0.9b 34% 23s
RAR 2.04 41% 27s
Aine 2.2 44% 18s
Limit 1.0 44% 35s

Как видно из приведенных результатов, в общем зачете - быстродействие/коэффициент сжатия победителями вышли IMP и UHARC. Абсолютными чемпионами по сжатию стали ACB и UHARC, а по скорости - AINE, однако, медленнее всех оказался ACB, затем идет BOA и UHARC. Наш привычный RAR занимает достаточно высокое место по скорости и относительно скромную позицию по сжатию, однако, это единственная из включенных нами в таблицу программ, имеющая оконно-ориентированный пользовательский интерфейс. Работа с остальными программами осуществляется посредством задания парамет-ров в командной с троке или файле.

 Здесь приводится выдержка из тестов, проведенных группой A.C.T. (www.arc-test.ru). Тест сжатия производился на ПК 486DX4 75MHz с RAM 16Mb под управлением ОС MS-DOS 6.22. Для тестирования использовались файлы из архива Calgary Corpus, содержащего 21 файл с совокупным размером 3255838 байт. В архиве содержались как текстовые, графические, так и двоичные файлы. Кэширующие программы не были загружены. Для измерения времени использовалась утилита Ultra Precision Command Timer v1.6 by Erik de Neve. Файлы сжимались с жесткого диска на 2'х-мегабайтный RAM-диск. Данные в таблице отсортированы нами в порядке улучшения сжатия, а "коэф-т" показывает на сколько процентов произведено сжатие (следовательно соотношение между ratio и "коэф-т" следующее: ratio+"коэф-т"=100%)

 При сравнительном анализе полученных результатов наблюдаются значительные расхождения в оценках. Так победитель наших тестов в области сжатия - ACB уступает BOA, а LHARC и вовсе остался в хвосте. Не совпадает и оценка скоростных параметров. Впрочем читатель может сам проанализировать сравнительные таблицы и сделать соответствующие выводы. Возможно, такие расхождения определяются различиями аппаратных платформ (486-я машина 75MHz и Pentium 233MHz, а также накопитель на жестких дисках, объем RAM и др) и программной среды (реальный режим MS-DOS без систем кэширования и защищенный режим Windows 95 с кэшированием и 32-х раз-рядным доступом к диску).

 Более ранние и привычные нам программы, а также наиболее распространенные архиваторы - pkzip, arj, ha, lha и другие остались далеко позади отобранных систем как по скорости, так и по качеству сжатия и поэтому в сравнительную таблицу включены небыли.

Как выбрать программу архиватор

 Несмотря на то, что в наше время цена мегабайта дискового пространства уменьшается с каждым годом, а качество носителей информации растет, потребность в архивации и резервном копировании остается, а проблема все также актуальна, как и десять лет назад. Это определяется тем, что архивация и сжатие данных необходимы не только для экономии места на локальном дисковом носителе, но и для переноса информации, резервирования, резервного копирования и т.п.. Поэтому, выбирая архиватор, необходимо руководствоваться его универсальностью и надежностью, но не забывать конечно и о главных параметрах - качество и скорость сжатия. Среди имеющихся в настоящий момент архиваторов многие являются специфичными к определенным форматам файлов, что несомненно следует использовать, но по назначению. Общий оценочный анализ показывает, что среди архиваторов с ratio < 40% большинство имеет значительно более длительное время паковки, которое может быть настолько велико (отличаться в сотни раз) по сравнению с выигрышем в сжатии (на 7-10%), что целесообразность использования данных программ сомнительна даже на очень мощных персональных компьютерах, таких как Pentium II 330MHz. Угнетает и тот факт, что большинство систем сжатия по прежнему компонуются как выполнимые модули реального режима для ОС MS-DOS и все возможности защищенного режима не используются. Этот же относится и к интерфейсу программ, который в общем оставляет желать лучшего, т.к. командная строка, хоть и является достаточно универсальным средством взаимодействия пользователя с программами, однако, весьма плохо приспособлена для быстрого просмотра списков имен, множественного выбора из списков (например файлов в архиве), множественного помещения в список и т.п., т.е. для операций, наиболее часто встречающихся в процессе работы с архивами. Возражающим посоветую произвести такую операцию, замерив затраченное на нее время. Возьмите архив из ~500 файлов с различными расширениями и извлеките из него 20-30 файлов, причем имена которых определите во время просмотра сoдержимого архива. Выполните эту задачу при помощи командной строки и при помощи какого нибудь оконного интерфейса. Такие и подобные операции пользователями интерфейсов командной строки обычно выполняются путем извлечения всех файлов из архива и удаления ненужных или переписывания необходимых в отдельный каталог, их архивация и удаление. Нет нужды говорить, что такая операция с применением оконного интерфейса и списков с возможностью множественного выбора элементов по маске производится гораздо быстрее и без затрат дополнительных дисковых ресурсов.

 Из стандартных и наиболее полезных на текущий момент свойств программ архиваторов следует также отметить следующие:
 
 

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

 Из попавших в рамки наших тестов, таким рекомендациям соответствует лишь RAR и WinRAR, а среди остальных - PKZIP, WinZIP, ARJ, LHA и GZIP. Эти программы и стандарты поддерживаются большинством файловых менеджеров, для них написано множество оболочек и управляющих командных файлов.

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