RFC1951 - DEFLATE Compressed Data Format Specification version 1.3

Network Working Group                                         P. Deutsch
Request for Comments: 1951                           Aladdin Enterprises
Category: Informational                                         May 1996


       DEFLATE Compressed Data Format Specification version 1.3

Status of This Memo

  Данная записка предоставляет информацию для сообщества Internet.
  Данная записка не определяет стандарт Internet ни в каком виде.
  На распространение данного документра не накладывается ни каких
  ограниченний.

IESG Note:

  The IESG takes no position on the validity of any Intellectual
  Property Rights statements contained in this document.

Notices

  Copyright (c) 1996 L. Peter Deutsch

  Permission is granted to copy and distribute this document for any
  purpose and without charge, including translations into other
  languages and incorporation into compilations, provided that the
  copyright notice and this notice are preserved, and that any
  substantive changes or deletions from the original are clearly
  marked.

  A pointer to the latest version of this and related documentation in
  HTML format can be found at the URL
  <ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html>.

Abstract

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

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

Table of Contents

  1. Introduction ................................................... 2
     1.1. Purpose ................................................... 2
     1.2. Intended audience ......................................... 3
     1.3. Scope ..................................................... 3
     1.4. Compliance ................................................ 3
     1.5.  Definitions of terms and conventions used ................ 3
     1.6. Changes from previous versions ............................ 4
  2. Compressed representation overview ............................. 4
  3. Detailed specification ......................................... 5
     3.1. Overall conventions ....................................... 5
         3.1.1. Packing into bytes .................................. 5
     3.2. Compressed block format ................................... 6
         3.2.1. Synopsis of prefix and Huffman coding ............... 6
         3.2.2. Use of Huffman coding in the "deflate" format ....... 7
         3.2.3. Details of block format ............................. 9
         3.2.4. Non-compressed blocks (BTYPE=00) ................... 11
         3.2.5. Compressed blocks (length and distance codes) ...... 11
         3.2.6. Compression with fixed Huffman codes (BTYPE=01) .... 12
         3.2.7. Compression with dynamic Huffman codes (BTYPE=10) .. 13
     3.3. Compliance ............................................... 14
  4. Compression algorithm details ................................. 14
  5. References .................................................... 16
  6. Security Considerations ....................................... 16
  7. Source code ................................................... 16
  8. Acknowledgements .............................................. 16
  9. Author's Address .............................................. 17

1. Введение

  1.1. Цель

         Цель данной спецификации состоит в том, чтобы определить
         формат сжатых без потерь данных, который:

         * Является независимым от типа центрального процессора,
       операционной системы, файловой системы и кодировки символов,
       и следовательно может использоваться для обмена данными;

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

         * Сжимает данные с эффективностью, сопоставимой c лучшими в
       настоящее время методами сжатия общего назначения, и в особенности
       значительно лучше чем программа "compress";

         * Может быть может быть реализован способом, не подпадающим под
       действие cуществующих патентов, и следовательно свободно;
       
         * Является совместимым с форматом файла, использованным
       утилитой gzip, в том смысле, что декомпрессор способен читать
       данные, сгенерированные существующим компрессором gzip.

         Формат данных, определенный этой спецификацией не делает попытку:

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

     Можно привести простые аргументы, которые показывают что отсутствует
     сжимающий без потери алгоритм, который способен сжать любые входные
     данные. Для формата определенного здесь, увеличение размера данных в
     наихудшем случае составляет 5 байт на 32K-байтный  блок, то есть,
     размер возрастает на 0.015%.

     Английский текст обычно сжимается с коэффициентом от 2.5 до 3;
     исполняемые файлы обычно сжимаются несколько меньше; графические
     данные типа растровых изображений  могут сжиматься гораздо сильнее.

  1.2. Intended audience

     Данная cпецификация предназначена для разработчиков программного
     обеспечения сжатия данных в "deflate" формат и/или декомпрессии
     данных из "deflate" формата.

     Текст спецификации подразумевает основные знания в программировании
     на уровне битов и других примитивных представлений данных.
     Знакомство с технологией кодирования Huffman полезны, но не
     требуются.

  1.3. Scope

     Спецификация определяет метод представления последовательности
     байтов как последовательность битов (обычно короче), и метод
     упаковки последней последовательности бит в байты.

  1.4. Compliance

     Если не оговорено другое, совместимый декомпрессор должен быть
     способен воспринимать и декомпрессировать любой набор данных,
     соответствующий всем спецификациям, приведенным здесь; совместимый
     (compliant) компрессор должен генерировать набор данных, который
     соответствуют всем спецификациям, представленным здесь.

 
  1.5.  Определения терминов и используемые соглашения

     Байт: 8 бит, хранимых и передаваемых как единица (то же что и октет).
     Для данной спецификации, байт составляет ровно 8 бит, даже если на
     машинах на которых осуществляется хранение символа количество бит
     отличается от восьми. Нумерация бит внутри байта приведена ниже.

     Строка: последовательность произвольных байт.

  1.6. Changes from previous versions (отличия от предыдущих версий)

     Начиная с версии 1.1 данной спецификации не было никаких технических
     изменений в формате "deflate".  В версии 1.2,  была изменена некоторая
     терминология. Версия 1.3 приводит данную спецификации к стилю оформления
     RFC.

2. Compressed representation overview

    Сжатые данные состоят из последовательности блоков, соответствующих
    блокам входных данных. Размер блока данных произвольный, за исключением
    того, что несжатые блоки ограничины размером в 65,535 байт.

    Каждый блок сжимается используя комбинацию алгоритма LZ77 и Huffman
    кодирования. Деревья Huffman для каждого блока не зависят от деревьев
    предыдущих или последующих блоков; алгоритм LZ77 может использовать
    ссылку на повторяющиеся строки в предыдущих блоках, до 32K входных
    байт ранее.

    Каждый блок состоит из двух частей: пара Huffman деревьев, которые
    описывают представление сжатых данных, и сжатые данные. (Сами деревья
    Huffman сжимаются используя Huffman кодирование.) Сжатые данные состоят
    из последовательности элементов двух типов: дословные байты
    (literal bytes) (или строки, которые не были обнаружены в предыдущих
    32K входных байтах), и указатели на повторяющиеся строки, где указатель
    представляет собой пару <длина,обратная дистанция> (<length, backward
    distance>). Формат "deflate" ограничивает смещение 32K байтами а длину
    258 байтами, но не ограничивает размер блока, за исключением не сжатых
    блоков, ограничение на длину которых приведено выше.

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

3. Детальная спецификация

  3.1. В ниже приведенных диаграммах, прямоугольник:



+---+ | | <-- вертикальные черточки могут быть опущены +---+



     представляет собой один байт; а прямоугольник типа :



+==============+ | | +==============+



     представляет собой переменное число байт.

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



+--------+ |76543210| +--------+



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



0 1 +--------+--------+ |00001000|00000010| +--------+--------+ ^ ^ | | | + more significant byte = 2 x 256 + less significant byte = 8



     3.1.1. Packing into bytes (Упаковка в байты)

     Данный документ не касается вопроса в каком порядке биты байта
     передаются в среду хранения битов, так как конечный описываемый здесь
     формат является байтовым а не бит ориентированным.

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

        * элементы данных упакованы в байты в порядке увеличения номера
      бита в пределах байта, то есть начиная с наименее значимого
      бита байта.

        * элементы данных, отличные от кодов Huffman-а упакованы,
      начиная с наименее значимого бита элемента данных.
 
        * Huffman коды упакованы, начиная с наиболее значимого бита кода.

     Другими словами, если распечатать сжатые данные как последовательность
     байтов, начиная с первого байта с *правой* границы и продвигаясь к
     *левой*, с наиболее-значимым битом каждого байта, расположенным слева
     как обычно, можно было бы разобрать результат с права на лево на
     элементы фиксированной-ширины в правильном порядке MSB-TO-LSB  бит
     и на коды Huffman с реверсивным порядком бит (то есть, первый бит
     кода в LSB позиции).



   
  3.2. Формат сжатого блока

     3.2.1. Synopsis of prefix and Huffman coding

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

     Мы определям префиксный код в терминах бинарного дерева в котором
     два ребра исходящие из не листового узла помечаются как 0 и как 1,
     а листовые узлы однозначно соответствуют символам алфавита; при этом
     код для символа представляет собой последовательность 0-ей и 1-ек,
     которыми помечены ребра, ведущие от корня к листу дерева, помеченному
     символом алфавита.  Например:


/\ Symbol Code 0 1 ------ ---- / \ A 00 /\ B B 1 0 1 C 011 / \ D 010 A /\ 0 1 / \ D C



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

     При заданном алфавите с известной частотой символов, алгоритм
     Huffman-а позволяет конструировать оптимальные префикстные коды.
     (представляя строки как частоты символов и используя наименьшее
     количество бит из всех префиксных кодов для данного алфавита).  
     Такой код называется кодом Huffman-а. (см. ссылку [1]  в главе 5,
     для дополнительной информации относительно кодов Huffman-а.)

     Отметим что для формата "deflate", коды Huffman-а для различных
     алгоритмов не должны превышать определенную максимальную длину.
     Данное ограниченние затрудняет алгоритм вычисления длины кодов
     из частоты появления. Детальное описание приведено в разделе 5.

     3.2.2. Use of Huffman coding in the "deflate" format

     В формате "deflate" коды Huffman-а, используемые для каждого алфавита
     имеют два дополнительных правила:

     * Все коды заданной битовой длины имеют лексикографически
       последовательные значения, в том же самом порядке, как и символы
       которые они представляют;

     * Более короткие коды лексиграфичеси предшествуют более длинным
   кодам.

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



Symbol Code ------ ---- A 10 B 0 C 110 D 111



     Т.е., 0 предшествует 10, которое предшествует 11x, а 110 и 111
     лексиграфически следуют друг за другом.

     Следуя данному правилу, мы можем определить коды Huffman-а для
     алфавита задавая только длины кодов для каждого символа алфавита;
     этого достаточно для определения фактических кодов. В нашем примере,
     коды полностью определены последовательностью длин кодов (2, 1, 3, 3).
     Ниже приведен алгоритм, который генерирует коды. Длины кодов
     первоначально расположены в tree[I].Len; генерируемые коды
     располагаются в tree[I].Code.

        1)  Подсчитываем колво кодов для каждой битовой длины кода.
        bl_count [N] - число кодов длины N, N >= 1.

        2)  Ищется числовое значения наименьшего кода для каждой кодовой
            длины:



code = 0; bl_count[0] = 0; for (bits = 1; bits <= MAX_BITS; bits++) { code = (code + bl_count[bits-1]) << 1; next_code[bits] = code; }



        3)  Назначаются числовые значения для всех кодов, используя
            последовательные значения для всех кодов одной и тойже длины,
            с базовыми значениями, определенными на шаге 2. Кодам, которые н
            никогда не используются (которые имеют битовую длину равную ноль)
            значение не назначается.


for (n = 0; n <= max_code; n++) { len = tree[n].Len; if (len != 0) { tree[n].Code = next_code[len]; next_code[len]++; } }



     Пример:

     Рассмотрим алфавит ABCDEFGH, с битовыми длинами (3, 3, 3, 3,
     3, 2, 4, 4).  После шага 1, мы имеем:



N bl_count[N] - ----------- 2 1 3 5 4 2



     Шаг номер 2. расчитанные значения для next_code дают:



N next_code[N] - ------------ 1 0 2 0 3 2 4 14




     Шаг номер 3. генерирует следующие значения для кодов:



Symbol Length Code ------ ------ ---- A 3 010 B 3 011 C 3 100 D 3 101 E 3 110 F 2 00 G 4 1110 H 4 1111



     3.2.3. Детали формата блока

     Каждый блок сжатых данных начинается с 3 битового заголовка, содержащего
     следующие данные:



первый бит BFINAL следующие 2 бита BTYPE



     Отметим что биты заголовка не обязательно начинаются на границе байта,
     так как блок не обязательно занимает целое число байтов.

BFINAL установливается только для последнего блока данных.

BTYPE определяет, как данные сжаты, следующим образом:

00 - нет компрессии
01 - сжат используя фиксированные коды Huffman-а
10 - сжат используя динамические коды Huffman-a
11 - зарезервировано (ошибка)

Единственная разница между двумя случаями компрессии состоит в том как определяются коды Huffman-а алфавита символ/длина и алфавита расстояние.

Во всех случаях, алгоритм декодирования данных следующий:


do считать заголовок блока из входного потока. если сохранен без применения компрессии пропустить биты остатка в текущем, частично обработанном байте считать LEN и NLEN (смотри следующую секцию) скопировать LEN байт данных в выходной поток в противном случае если сжато используя динамические коды Huffman-а считать представление деревьев (смотри ниже) loop (до распознания кода конца блока) декодировать значение (value) символа/длины из входного потока если значение < 256 скопировать значение (литерального байта) в выходной поток в противном случае если значение совпадает с концом блока (256) выйти из цикла в противном случае (значение = 257..285) декодировать расстояние (байт) в входном потоке сдвинуться назад на декодированное количество в выходном потоке, и копировать length байт из данной позиции в выходной поток end loop while не последний блок



   Отметим, что ссылка на дубликат строки может обращатся к предыдущему блоку,
     то есть, обратное расстояние может пересекать одну или более границ блока.
     Однако расстояние не может обращаться к данным расположенным перед началом
     выходного потока.
     (Приложения использующие предустановленный словарь могут отбрасывать
     часть выходного потока; расстояние может указывать на такие части выходного
     потока в любом случае) Отметим также что строка ссылка может перекрывать
     текущую позицию; например, если последние 2 байта декодрованы как X и Y,
     а строка ссылка как <длина = 5, расстояние = 2> то данная ссылка
     дает в выходной поток X,Y,X,Y,X.

               Теперь определим каждый метод сжатия.

     3.2.4. Не-сжатые блоки (BTYPE=00)

     Любые биты ввода до следующей границы байта игнорируются.
     Остальная часть блока содержит следующую информацию:



0 1 2 3 4... +---+---+---+---+==================================+ | LEN | NLEN |... LEN байт литеральных данных...| +---+---+---+---+==================================+



     LEN количество байт данных в блоке. NLEN дополнение LEN до единиц.

     3.2.5. Сжатые блоки (коды для длины и расстояния)

     Как отмечалось выше, кодируемые блоки данных формате "deflate"
     состоят из последовательностей символов, из трех концептуально
     различных алфавитов: либо литеральные байты из алфавита значений
     байта (0.. 255), либо пара <длина, обратное расстояние>, где длина
     находится в диапазоне до 258 а расстояние от 1 до 32,768. Фактически,
     литеральный алфавит и алфавиты длины слиты в единый алфавит (0.. 285),
     где значения 0.. 255 представляют литеральные байты, значение 256
     указывает конец-блока, а значения 257.. 285 представляют коды длины
     (возможно вместе с дополнительными битами после кода символа)
     следующим образом:


Extra Extra Extra Code Bits Length(s) Code Bits Lengths Code Bits Length(s) ---- ---- ------ ---- ---- ------- ---- ---- ------- 257 0 3 267 1 15,16 277 4 67-82 258 0 4 268 1 17,18 278 4 83-98 259 0 5 269 2 19-22 279 4 99-114 260 0 6 270 2 23-26 280 4 115-130 261 0 7 271 2 27-30 281 5 131-162 262 0 8 272 2 31-34 282 5 163-194 263 0 9 273 3 35-42 283 5 195-226 264 0 10 274 3 43-50 284 5 227-257 265 1 11,12 275 3 51-58 285 0 258 266 1 13,14 276 3 59-66



     Дополнительные биты (extra bits) должны интерпретироваться как машинные
     целые, хранимые с наиболее значимым битом первым, т.е., биты 1110
     представляют значение 14.



Extra Extra Extra Code Bits Dist Code Bits Dist Code Bits Distance ---- ---- ---- ---- ---- ------ ---- ---- -------- 0 0 1 10 4 33-48 20 9 1025-1536 1 0 2 11 4 49-64 21 9 1537-2048 2 0 3 12 5 65-96 22 10 2049-3072 3 0 4 13 5 97-128 23 10 3073-4096 4 1 5,6 14 6 129-192 24 11 4097-6144 5 1 7,8 15 6 193-256 25 11 6145-8192 6 2 9-12 16 7 257-384 26 12 8193-12288 7 2 13-16 17 7 385-512 27 12 12289-16384 8 3 17-24 18 8 513-768 28 13 16385-24576 9 3 25-32 19 8 769-1024 29 13 24577-32768



     3.2.6. Компрессия с фиксированными кодами Huffman (BTYPE=01)

     Коды Huffman для этих двух алфавитов предустановлены, и не
     представлены явно в данных. Длины кода Huffman для алфавита
     литерала/длины:




Lit Value Bits Codes --------- ---- ----- 0 - 143 8 от 00110000 до 10111111 144 - 255 9 от 110010000 до 111111111 256 - 279 7 от 0000000 до 0010111 280 - 287 8 от 11000000 до 11000111



     Как было описано выше, длины кода достаточно для генерации
     фактических кодов; коды приведены в таблице для дополнительной ясности.
     Значения 286-287 литерального символа/длины фактически не никогда не
     появятся в сжатых данных.

     Коды расстояния 0-31, представляются (фиксированной-длиной) 5 битами,
     с возможными дополнительными битами как показано в таблице, в
     параграфе 3.2.5, выше. Обратите внимание, что расстояния кодированные
     значениями 30-31, никогда не будут встречаться в сжатых данных.

         3.2.7. Сжатие с динамическими кодами Huffman (BTYPE=10)

     Коды Huffman-а для этих двух алфавитов появляются в блоке
     непосредственно после битов заголовка и перед сжатыми данными,
     причем сначала идет код литерала/длины а затем код расстояния.
     Каждый код определен последовательностью длин кода, как описано
     выше в параграфе 3.2.2. Для большей компактности, коды длины сжаты,
     используя код Huffman. Алфавит для длин следующий:




0 - 15: Представляют длины 0 - 15 16: Копировать предыдущую длину кода 3 - 6 раз. Следующие 2 бита указывают длину повторения (От 0 до 3..., от 3 до 6) Пример: 8, 16 (+2 бита 11), 16 (+2 бита 10) кодируют 12 8-ми битовых длин (1+6+5) 17: Повторить длину кода 0 для 3 - 10 раз. (3 бита длины) 18: Повторить длину кода 0 для 11 - 138 раз. (7 битов длины)



     Длина кода 0 указывает, что соответствующий символ в алфавите
     литерала/длина или в алфавите расстояния не встречается в блоке, и
     не должен участвовать в алгоритме построения кода Huffman-а,
     приведенном выше. Если используется только один код расстояния,
     это кодируется используя один бит, (не нулевыми битами); в данном
     случае единственная длина единица, c одним неиспользованным кодом.

     Теперь мы можем определить формат блока:

          5 битов: HLIT, # кодов литерала/длины - 257 (257 - 286)
          5 битов: HDIST,# кодов расстояния - 1 (1 - 32)
          4 бита : HCLEN,# кодов длины - 4 (4 - 19)
          (HCLEN + 4) x 3 бита: длины кода для алфавита длины, данного
             только что выше, в порядке: 16, 17, 18, 0, 8, 7, 9,
             6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15


          Данные длины кодов интерпретируются как 3 битовые (0-7)
      целые числа; длина 0 обозначает что соответствующий символ
      (литеральный символ/длина или расстояния) не используется.


          HLIT + 257 кодовых длин для алфавита литерала/длины,
          закодированных используя код Huffman для длин

          HDIST + 1 кодовых длин для алфавита расстояния,
          закодированного с использованием кода Huffman-а для длины

          Фактические сжатые данные блока, кодированные с использованием
          кодов Huffman для литеральных символов/длины и расстояния

          Символ 256 из алфавита литеральных символов/длины (конец данных),
          закодированный с использованием кода Huffman-а для литерального
          символа/длины

     The code length repeat codes can cross from HLIT + 257 to the
     HDIST + 1 code lengths.  In other words, all code lengths form
     a single sequence of HLIT + HDIST + 258 values.

  3.3. Compliance

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

     Совместимый декомпрессор должен воспринимать полные диапазоны значений,
     определенных в предыдущем разделе, а также должен воспринимать блоки
     произвольного размера.

4. Compression algorithm details

     В то время как намерением данного документа явлеется определение
     формат "deflate" сжатых данных не ссылаясь на какой то конкретный
     алгоритма сжатия, данных формат похож на форматы, используемые
     LZ77 (Lempel-Ziv с 1977, смотри ссылку [2]); так как много
     реализаций LZ77 запатентованы, настоятельно рекомендуется, чтобы
     реализатор компрессора придерживался общего алгоритма, описанного
     здесь, о котором известно, что он не будет запатентован сам по себе.

     Материал приведенный в данном разделе - не часть определения
     спецификации, и компрессор не должен следовать ниже описанному,
     чтобы быть совместимым.

     Компрессор заканчивает блок, когда он определяет, что старт нового
     блока с новыми деревьями был бы полезен, или когда размер блока
     выходит за пределы  буфера компрессора.

     Для обнаружения продублированных строк компрессор использует цепочечную
     hash таблицу,  используя hash функцию,  которая работает c 3-байтовых
     последовательностями. В любой точке во время компрессии, проверяются
     следующие 3 бйта XYZ   (не обязательно все различные, конечно). Сначала,
     компрессор исследует hash цепочку на наличие XYZ. Если цепочка пуста,
     компрессор просто записывает X как литеральный байт и продвигается
     на один байт во входном потоке. Если hash цепочка - не пуста, то это
     указывает что последовательность XYZ (или, если при неудаче, некоторые
     другие 3 байта с тем же самым значением hash функции) недавно
     встречалились, компрессор сравнивает все строки в XYZ hash цепочке с
     фактической входной последовательностью данных, и выбирает самое
     длинное соответствие.


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


     Чтобы улучшать общее сжатие, компрессор опционально задерживает выбор
     совпадения ("ленивое совпадение" или "lazy match"): после того, как
     найдено совпадение длиной N , компрессор ищет более длинное совпадение,
     начиная со следующего входного байта.
   
     Если это находится более длинное совпадение, то записывается один
     литеральный байт, а затем записывается ссылка на более длинное
     совпадение.

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

5. References

  [1] Huffman, D. A., "A Method for the Construction of Minimum
      Redundancy Codes", Proceedings of the Institute of Radio
      Engineers, September 1952, Volume 40, Number 9, pp. 1098-1101.

  [2] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data
      Compression", IEEE Transactions on Information Theory, Vol. 23,
      No. 3, pp. 337-343.

  [3] Gailly, J.-L., and Adler, M., ZLIB documentation and sources,
      available in ftp://ftp.uu.net/pub/archiving/zip/doc/

  [4] Gailly, J.-L., and Adler, M., GZIP documentation and sources,
      available as gzip-*.tar in ftp://prep.ai.mit.edu/pub/gnu/

  [5] Schwartz, E. S., and Kallick, B. "Generating a canonical prefix
      encoding." Comm. ACM, 7,3 (Mar. 1964), pp. 166-169.

  [6] Hirschberg and Lelewer, "Efficient decoding of prefix codes,"
      Comm. ACM, 33,4, April 1990, pp. 449-459.

6. Security Considerations

  Any data compression method involves the reduction of redundancy in
  the data.  Consequently, any corruption of the data is likely to have
  severe effects and be difficult to correct.  Uncompressed text, on
  the other hand, will probably still be readable despite the presence
  of some corrupted bytes.

  It is recommended that systems using this data format provide some
  means of validating the integrity of the compressed data.  See
  reference [3], for example.

7. Source code

  Source code for a C language implementation of a "deflate" compliant
  compressor and decompressor is available within the zlib package at
  ftp://ftp.uu.net/pub/archiving/zip/zlib/.

8. Acknowledgements

  Trademarks cited in this document are the property of their
  respective owners.

  Phil Katz designed the deflate format.  Jean-Loup Gailly and Mark
  Adler wrote the related software described in this specification.
  Glenn Randers-Pehrson converted this document to RFC and HTML format.

9. Author's Address

  L. Peter Deutsch
  Aladdin Enterprises
  203 Santa Margarita Ave.
  Menlo Park, CA 94025

  Phone: (415) 322-0103 (AM only)
  FAX:   (415) 322-1734
  EMail: <ghost@aladdin.com>

  Questions about the technical content of this specification can be
  sent by email to:

  Jean-Loup Gailly <gzip@prep.ai.mit.edu> and
  Mark Adler <madler@alumni.caltech.edu>

  Editorial comments on this specification can be sent by email to:

  L. Peter Deutsch <ghost@aladdin.com> and
  Glenn Randers-Pehrson <randeg@alumni.rpi.edu>


2004. Translated to Russian by Dmitriy Cherkashin <dch@ucrouter.ru>.


  Этот информационный блок появился по той простой причине, что многие считают нормальным, брать чужую информацию не уведомляя автора (что не так страшно), и не оставляя линк на оригинал и автора — что более существенно. Я не против распространения информации — только за. Только условие простое — извольте подписывать автора, и оставлять линк на оригинальную страницу в виде прямой, активной, нескриптовой, незакрытой от индексирования, и не запрещенной для следования роботов ссылки.
  Если соизволите поставить автора в известность — то вообще почёт вам и уважение.

© lissyara 2006-10-24 08:47 MSK