Мы — долго запрягаем, быстро ездим, и сильно тормозим.

RFC
  RFC1180 (TCP/IP)
  RFC791 (IP)
  RFC792 (ICMP)
  RFC793 (TCP)
  RFC768 (UDP)
  RFC1459 (IRC)
  RFC1521 (MIME)
  RFC1951 (DEFLATE)
  RFC2839 (IKS)
Программирование
FreeBSD
man
EXIM


www.lissyara.su —> документация —> RFC —> RFC1951 (DEFLATE)

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>.





Хостинг HOST-FOOD

2014-07-27, lissyara
gmirror

Удалённое создание софтверного зеркала средствами gmirror, на диске разбитом с использованием gpart. Использование меток дисков для монтирования разделов.
2013-08-20, zentarim
Scan+Print server FreeBSD 9

Настройка сервера печати и сервера сканирования под управлением операционной системы FreebSD 9 для МФУ Canon PIXMA MP540
2011-11-20, BlackCat
Разъём на WiFi-карту

Делаем съёмной несъёмную антену на WiFi-карте путём установки ВЧ-разъёма
2011-09-14, manefesto
Настройка git+gitosis

Настройка системы контроля версия исходного кода в связке git+gitosis+ssh
2011-08-14, zentarim
Wi-FI роутер + DHCP + DNS

Настройка Wi-Fi роутера на Freebsd 8 + DNS сервер + DHCP сервер: чтобы Wi-Fi клиенты были в одной подсети с проводными, проводные и беспроводные клиенты получали адреса автоматически по DHCP, кэширующ
2011-06-15, -ZG-
Охранная система на FreeBSD+LPT

В этой статье описана попытка реализации простой охранной системы на базе FreeBSD с подключением к ней охранных устройтсв на LPT порт и видеорегистрацией.
2011-03-13, terminus
ng_nat

Описание работы ng_nat, практическое использование, достоинства и недостатки в сравнении с ipfw nat
2011-02-20, Капитан
Nagios+Digitemp

Статья описывает создание системы оповещения о превышении температуры в специальных помещениях на основе Nagios с использованием программы Digitemp.
2011-02-17, Le1
Zyxel Configuration

Скрипт для массового изменения конфига свичей Zyxel. Берет из файла iplist список ip-шек, заходит последовательно на каждый и выполняет комманды из файла commands, записывая происходящее в лог файл.
2011-02-16, fox
hast carp zfs ucarp cluster

HAST (Highly Available Storage), CARP, UCARP, ZFS, Cluster настройка и одаптация плюс личные размышления…
2011-02-04, BlackCat
Восстановление ZFS

История о том, как был восстановлен развалившийся RAIDZ ZFS-пул (перешедший в FAULTED) с помощью скотча и подручных средств. Или о том, какие приключения ожидают тех, кто не делает резервных копий.
2011-02-03, Капитан
1-Wire

Статья описывает самостоятельное изготовление контроллера DS9097 для съёма показаний с датчиков температуры DS1820 с помощью программы Digitemp.
2011-01-28, Капитан
Температура в серверной

Статья описывает построение системы наблюдения за температурой в помещении серверной с использованием программы Digitemp и выводом графиков в MRTG
2011-01-21, m4rkell
Syslog server

Как то буквально на днях, у нас завалилось, что то в еве) или не в еве не суть. Суть в том, что когда захотели снять логи с хостов esx обнаружили, что хранят эти негодяи логии только за последнии сутк
2011-01-07, lissyara
Canon/gphotofs

Монтирование цифровых фотоаппаратов Canon (PTP) как файловой системы, автоматизация этого процесса через события devd и внешние скрипты.
2010-12-13, Al
IPSec

Описание принципов работы IPSEC и способов аутентификации.
2010-12-07, manefesto
FreeBSD on flash

Было принято решении переехать на USB Flash и установить минимальный джентельменский набор для работы своего роутера. Делаем =)
2010-12-05, Fomalhaut
root ZFS, GPT

Инструкция по установке FreeBSD с использованием в качестве таблицы разделов GPT и в качестве основной файловой системы - ZFS
2010-09-05, Cancer
Настройка аудиоплеера на ximp3

Цели: Простенький аудиоплеер, для того что бы тетя продавец в магазине утром пришла нажала на кнопку Power и заиграла в зале музыка, так же был доступ по сети, общая шара куда можно заливать музыку, к
2010-08-31, Cancer
Установка и настройка OpenVPN

На днях появилась задача - объединить головной офис и 3 филиала в одну сеть через интернет посредством OpenVPN, чтобы люди могли подключаться через RDP к базам 1С на серверах.
2010-08-25, manefesto
freebsd lvm

Использование linux_lvm для работы с LVM разделами из-под FreeBSD. Проблемы которые возники при монтирование lvm раздела
2010-04-30, gonzo111
proftpd file auth&quota

Proftpd - квоты и авторизация из файлов, без использования базы данных и/или системных пользователей
2010-04-22, lissyara
tw_cli

Пошаговая инструкция по восстановлению RAID на контроллере 3ware, из которого выпал один диск. Настройка мониторинга состояния рейда и отчётов о его состоянии на email.
2010-04-14, fox
MySQL Master+Master

MySQL (Master Master) and (Master Slave) Как настроить репликацию…
2010-03-09, terminus
DNS zones

Краткий ликбез про управление DNS зонами. Примеры проведения делегирования прямых и обратных DNS зон.
2010-03-09, aspera
Squid+AD (group access)

Настройка прокси сервера SQUID с автроризацией пользователей в AD. Разделение пользователей на группы
2010-03-02, BlackCat
Шлюз: Часть 4

Настройка дополнительных сервисов: синхронизация времени (OpenNTPD), клиент DynDNS.org.
2010-03-01, BlackCat
Шлюз: Часть 3

Настройка DHCP и DNS серверов для работы внутри частной сети, c поддержкой внутренних (частных зон) DNS, а так же интеграция DHCP и DNS сервисов.
2010-03-01, BlackCat
Шлюз: Часть 2

Конфигурация МСЭ pf для проброса портов с изменением порта назначения и без, а так же поддержки активного режима FTP и ограничения максимального размера сегмента
2010-03-01, BlackCat
Шлюз: Часть 1

Быстрая настройка шлюза/маршрутизатора с установлением PPPoE-соединения, поддержкой NAT и DNS-forwarding.
2010-02-23, Morty
darkstat

Простая считалка траффика, со встроенным веб-сервером. Очень маленькая, может делать отчеты трафика по хостам, портам, протоколам, а также строить графики
2010-01-23, gonzo111
squid+sams+sqstat

Пилим squid и sams - примеры конфигов с объяснениями. Установка SqStat.
2009-12-19, schizoid
mpd5 + radius + ng_car + Abills

Настройка pppoe-сервера с биллинговой системой Abills и шейпером ng_car
2009-11-16, lissyara
UFS->ZFS

Удалённая миграция с UFS на ZFS. Загрузка с раздела zfs. Настройка для работы с малым количеством памяти под архитектурой i386.
2009-11-13, gx_ua
fusefs-ntfs

Установка, настройка и использование fusefs-ntfs, драйвер NTFS, предназанченного для монтирования NTFS разделов под FreeBSD
2009-11-12, Morty
LiveCD

Создание собственного LiveCD с необходимыми вам изменениями, автоматизирование данного процесса, а так же вариант скоростной сборки СД.
2009-09-27, lissyara
Samba как PDC

Контроллер домена - аналог M$ NT4 домена под самбой, без использования LDAP и прочей хиромантии. Просто и быстро =)
2009-08-30, terminus
ipfw nat

Подробное руководство по ipfw nat, сложные случаи конфигурации.
2009-08-24, levantuev
HotSpot

Установка Hotspot системы в общественное заведение.
2009-08-18, lissyara
diskless

Создание бездисковых терминалов под управлением FreeBSD - с загрузкой по сети. Используются для старта rdesktop и подключения к виндовому серверу терминалов.
2009-07-29, BAV_Lug
Видеонаблюдение

Настройка бюджетного варианта видеонаблюдения на удаленном объекте
2009-07-22, Cancer
OpenLDAP адресная книга

Настройка и создание адресной книги на базе OpenLDAP + phpLDAPadmin
2009-06-30, SergeySL
AimSniff

Руководство по созданию системы мониторинга ICQ-переписки на базе AimSniff, использующей базу данных MySQL для хранения и Web-интерфейс WAS (Web Aim Sniff) для просмотра перехваченных сообщений
2009-06-25, atrium
Управление правами доступа

Полномочия пользователей и файлов, принадлежащих им, формирует концепцию ОС UNIX.
2009-06-16, DNK
Exim+PgSQL

Установка почтовой системы exim+pgsql на FreeBSD 7.1
2009-05-30, mvalery
HDD(mbr) -> HDD(gpt)

Как разбить диск размером более 2TB на разделы, сделать загрузочным, а затем перенести на него информацию с рабочей системы — донора.
2009-05-22, Cancer
SendXMPP

Отправка сообщений на Джаббер сервер по средствам SendXMPP
2009-05-11, Raven2000
Network UPS Tools

Network UPS Tools представляет собой набор программ, которые обеспечивают общий интерфейс для мониторинга и администрирование UPS оборудования.
2009-04-29, m0ps
IPSEC over GRE with RIP

Пример IPSEC over GRE и динамическим роутингом (RIP), с ADSL в качестве последней мили на оборудовании Cisco.
2009-04-24, WhiteBear777
qemu network

Появилась необходимость поставить на БСД эмулятор(qemu) и настроить в качестве гостевой ОС Windows XP, предоставив ей выход в локалку и в сеть internet...
2009-04-22, vp
freebsd + huawei 162 gsm modem

В статье описывается простой способ подключения модема huawei 162 к freebsd + первичная настройка smstools
2009-04-12, mvalery
Мониторинг RAID

Мониторинг из командной строки RAID компаний AMCC 3ware, HighPoint, Dell (Perc 5/i и PERC 6/i) и LSI (MegaRAID SAS 8408E и SAS1078)
2009-04-09, texnotronic
RAID1 via LAN

Функциональности DRBD во FreeBSD можно добиться примонтировав блочное устройство по сети при помощи GEOM Gate (ggate) и добавив его в зеркало с локальным диском средствами gmirror.
2009-04-03, Raven2000
Оптимизация хоста для CMS

В последнее время на старый и не очень быстрый ПК (Celeron 800 RAM 256) мною было навешано с десяток сайтов и некоторые были из серии тяжелых CMS. И так нам дано FreeBSD 7.1 и ~10 сайтов/CMS.
2009-04-01, atrium
VSFTPD + AD && MySQL

Настройка самого безопасного сервера FTP - vsftpd.
2009-03-31, Dron
Peoplenet + C-motech (3G)

Описание подключения к сети Peoplenet посредством 3G модема С-motech CCu-650U на FreeBSD
2009-03-25, lissyara
mod_auth_external

mod_auth_external - авторизация пользователей в apache c помощью внешней программы - например, системных пользователей.
2009-03-24, gx_ua
Lightsquid

Частично lightsquid может заменить sams: быстрая и простая инсталляция, быстрый парсер, cgi скрипт для динамической генерации отчета, нет привязки к БД, различные графические отчеты, мультиязычный инт
2009-03-18, LHC
Установка Zabbix-1.6

Установка и первоначальная настройка системы мониторинга Zabbix (версия 1.6)
2009-03-16, Cancer
Принт-Сервер Samba+LPD & AD

Простейшая настройка Принт-Сервера на FreeBSD используя Samba+LPD & AD
подписка

    вверх      
Статистика сайта
Сейчас на сайте находится: 9 чел.
За последние 30 мин было: 33 человек
За сегодня было
2804 показов,
531 уникальных IP
 

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

© lissyara 2006-10-24 08:47 MSK

Компания промышленный монтаж окажет широкий спектр услуг

Время генерации страницы 0.041 секунд
Из них PHP: 37%; SQL: 63%; Число SQL-запросов: 46 шт.
Исходный размер: 146034; Сжатая: 30665