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