Даний документ визначає безвтратний формат стиснення даних, який стискає дані використовуючи комбінацію алгоритму LZ77 і кодування Хоффмана (Hoffman). Дані можуть бути відтвореними або стисненими, навіть для довільно довгого ввідного потоку даних, використовуючи тільки обмежений простір даних. Формат може бути легко реалізованим способом, який не закритий патентами.
1. Вступ.
1.1 Призначення.
Призначення даної специфікації полягає у визначенні безвтратного способу стиснення даних, які:
- являються незалежними від типу центрального процесора, операційної системи, файлової системи, набору символів, а отже може бути використаним для обміну;
- може бути створеним або отриманим, навіть для доволі довгої послідовності потоку введення даних, використовуючи тільки невелику кількість місця збереження, і отже може бути використаним у комунікаціях або подібних структурах;
- стискати дані ефективно у порівнянні з найкращими з зараз доступних методів стиснення загального призначення, і кращою, ніж програма "стиснення";
- може бути реалізованою легко способом, який не закритий патентами, і отже може вільно розповсюджуватися.
- сумісний з форматом файлів, який створюється широко-розповсюдженою програмою gzip, що дозволить декомпресорам зчитувати дані, які створюються існуючим компресором gzip.
Формат даних, визначений цією специфікацією, не призначений для:
- довільного доступу до стиснених даних;
- стискати спеціалізовані дані (на подобі растрової графіки), так само як поточні найкращі спеціалізовані алгоритми.
Статистика показує, що безвтратні алгоритми стиснення не можуть ефективно стискати абсолютно усі можливі набори ввідних даних. Для формату описаного в даному документі, найгірший випадок розширення складає 5 байтів на 32 кілобітний блок, тобто, збільшення розміру на 0.015% для великих наборів даних. Текст на англійському зазвичай стискається від 2.5 до 3 разів; виконувані файли зазвичай стискаються дещо менше; графічні дані на подобі растрових зображень можуть стискатися набагато більше.
1.2 Призначення аудиторії
Дана специфікація призначена розробникам програмного забезпечення, які створюють програму для стиснення даних у формат "deflate" і/або розпакування даних з формату "deflate".
Текст специфікації припускає базові знання у програмуванні на рівні бітів і інших примітивних представлень даних. Обізнаність з технікою кодування Хоффмана (Hoffman) являється бажаним, але не обов'язковим.
1.3 Сфера
Дана специфікація визначає метод для представлення послідовності байтів у вигляді (зазвичай коротшому) послідовності бітів і метод для упаковування даних бітів у байти.
1.4 Сумісність
Якщо у тексті специфікації не вказане інше, сумісний декомпресор повинен вміти прийняти і розпакувати будь-який набір даних, який відповідає усім специфікаціям вказаним в даному документі; сумісний компресор повинен продукувати набір даних, який відповідає усім специфікаціям вказаним в поточному документі.
1.5 Визначення використовуваних термінів
Байт - 8 бітів, які зберігають або передаються у вигляді базової одиниці (те ж саме, що і октет). Для даної специфікації, байт містить саме 8 бітів, навіть на машинах, які зберігають символи у кількості бітів відмінних від восьми. Нижче у документі вказано, як номеруються біти у байті.
Рядок - послідовність довільних байтів.
1.6 Зміни від попередніх версій
Технічних змін не було у форматі deflate від версії 1.1 даної специфікації. У версії 1.2 була змінена деяка термінологія. Версія 1.3 є переформатованою у стиль RFC документів.
2. Огляд стисненого представлення.
Стиснені дані складаються з серії блоків, які відповідають наступним блокам введених даних. Блоки даних є довільними, окрім того, що не стиснені блоки обмежуються до кількості 65535 байтів.
Кожен блок стискається використовуючи комбінацію алгоритму LZ77 і кодування Хоффмана. Дерева Хоффмана для кожного блоку являються незалежними від наступних або попередніх блоків; алгоритм LZ77 може використовувати посилання на дублі рядків, які розміщені у попередньому блоку, аж до 32 кілобайтів попередніх даних.
Кожен блок складається з двох частин: пари коду дерева Хоффмана, який описує предаставлення частини стиснених даних, і стиснених даних. (Дерева Хоффмана самі по собі являються стисненими, за допомогою використання кодування Хоффмана). Стиснені дані складаються з серій елементів двох типів: літеральних байтів (рядків, які не були продубльовані в попередніх 32 кілобайтах даних), і вказівників на продубльовані рядки, де вказівники представляються у вигляді пари <довжина, зворотнє зміщення>. Представлення використане у форматі deflate обмежує відстань у 32 кілобайти і довжину у 258 байтів, але не обмежує розмір блоку, окрім для блоків, які не можуть бути стисненими, які є обмеженими, як вказано раніше.
Кожен тип значення (літерали, зміщення і довжини) у стиснених даних представляються у вигляді коду Хоффмана, використовуючи одне дерево коду, для літералів і довжин і окреме дерево для зміщень. Дерева коду для кожного блоку з'являються у компактній формі перед стисненими даними для цього блоку.
3. Детальна специфікація
3.1 Загальні позначення.
У діаграмах розміщених нижче, прямокутник на подобі наступного:
+---+
| | <-- вертикальні лінії можуть бути пропущеними
+---+
представляють один байт; прямокутник на подобі даного:
+==============+
| |
+==============+
представляє будь-яку кількість байтів.
Байти зберігаються у комп'ютері не мають "порядок бітів", оскільки вони завжди трактуються як базові одиниці. Однак, байт вважається цілим числом між значенням 0 і 255, має найбільш і найменш значущий біти, і оскільки ми пишемо числа з найбільш значущим бітом зліва, ми також пишемо байти з найбільш значущими бітами зліва. У наступній діаграмі, ми призначили порядкові числа бітам байту, отож біт 0 являється найменш значущим бітом, тобто біти пронумеровані:
+--------+
|76543210|
+--------+
У комп'ютері, число може займати декілька байтів. Усі багатобайтні числа у описаному тут форматі, зберігаються у найменш значущому байті першому (при меншій адресі пам'яті). Наприклад, десяткове число 520 зберігається на подобі:
0 1
+--------+--------+
|00001000|00000010|
+--------+--------+
^ ^
| |
| + більш значущий байт = 2 x 256
+ менш значущий байт = 8
3.1.1 Упаковування у байти
Даний документ не торкається теми порядку розміщення бітів байту, який передається через потокове медіа, оскільки кінцевий формат даних, який описується даним документом являється скоріш байтово- ніж бітово-орієнтованим. Однак ми описуємо формат стиснених блоків нижче, у вигляді послідовності елементів даних деяких бітових довжин, а не послідовність байтів. Ми повинні однак вказати, як упаковувати ці елементи даних у байти для формування кінцевої послідовності байтів:
- Елементи даних упаковуються у байти в порядку, який збільшує його номер в байті, тобто починаючи з найменш значущого біту байта.
- Елементи даних які не являються кодами Хоффмана упаковуються починаючи з найменш значущого біту елементу даних.
- Коди Хоффмана упаковуються починаючи з найбільш значущого біту коду.
Іншими словами, якщо одна сторона буде передавати стиснені дані у якості послідовності байтів, починаючи з першого байту правої сторони і продовжуватиме до лівої сторони, з найбільш значущими бітами кожного байту зліва як зазвичай, інша сторона буде в змозі розпізнавати результат з права наліво, з елементами фіксованої довжини у правильному порядку НЗБ-до-МЗБ (найбільш значущий біт до менш значущого біту - MSB-to-LSB) і коди Хоффмана у оберненому порядку (тобто перший біт коду у відносній позиції менш значущого біту).
3.2. Формат стисненого блоку.
3.2.1. Опис префіксу і кодування Хоффмана
Префіксні кодування представляються символи з абетки за бітовими послідовностями (кодами), один код для кожного символу, у манері, в якій різні символи можуть бути представлені за допомогою бітових послідовностей різних довжин, але парсер може завжди однозначно розпізнавати закодовані рядки символ-за-символом.
Ми визначаємо префіксний код у термінах бінарного дерева, у якому дві грані відрізняються від не листового вузла за допомогою мітки 0 і 1 і у якому листовий вузол відповідає один-до-одного з символом абетки; тоді код для символу являється послідовністю нулів і одиниць на гранях від кореня до листового вузла з цим символом. Наприклад:
/\ Символ Код
0 1 ------ ----
/ \ A 00
/\ B B 1
0 1 C 011
/ \ D 010
A /\
0 1
/ \
D C
Парсер може розкодовувати наступний символ з закодованого потоку введення, йдучи вниз по дереву з кореня, на кожному кроці вибираючи грань у відповідності до наступного біту.
Отримана абетка з відомою чистотою символів, і алгоритм Хоффмана дозволяє конструкцію з необов'язковим префіксним кодом (який відображає рядок з цими частотами символів, використовуючи декілька бітів будь-якої можливих префіксних кодів цієї абетки). Такі коди називаються кодами Хоффмана [1].
Зверніть увагу, що у форматі "deflate" коди Хоффмана для декількох абеток повинні не перевищувати певну максимальну довжину коду. Це обмеження ускладнює алгоритм для обчислення довжин кодів з частот символів.
3.2.2 Використання кодів Хоффмана у форматі "deflate".
Коди Хоффмана, які використовуються для кожної абетки у форматі deflate мають два додаткових правила:
- Усі коди даної довжини бітів мають лексикографічні послідовні значення, у тому самому порядку символів, які вони представляють.
- Короткі коди лексикографічно передують довшим.
Ми можемо перекодувати приклад наведений вище для того, щоб слідувати даним правилам, припускаючи, що порядок абетки являється ABCD:
Символ Код
------ ----
A 10
B 0
C 110
D 111
Тобто 0 передує 10 який передує 11х, і 110 і 111 являються лексикографічно послідовними.
Застосовуючи це правило, ми можемо визначити коди Хоффмана для абетки просто надаючи бітні довжини кодів для кожного символу абетки у порядку; це достатньо для визначення самих кодів. У нашому прикладі коди являються повністю визначеними за допомогою послідовності бітових довжин (2, 1, 3, 3). Наступний алгоритм генерує коди у якості цілих чисел, які призначені для зчитування з найбільш значущого до найменш значущого біту. Довжини кодів зберігаються у tree[I].Len; коди зберігаються у tree[I].Code.
- Обчислити номери кодів для кожної довжини коду. Нехай bl_count[N] буде кількістю кодів довжини N, N>=1.
- Знайти числове значення найменшого коду для кожної довжини:
code = 0 ;
bl_count[0] = 0 ;
for (bits = 1; bits <= MAX_BITS; bits++)
{
code = (code + bl_count[bits-1]) << 1 ;
next_code [bits] = code ;
}
- числові значення до усіх кодів, використовуючи послідовні значення для усіх кодів однакової довжини з базовими значеннями, визначеними у кроці 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 продукує наступні значення кодів:
Символ Довжина Код
------ ------- ----
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. Деталі форматів блоку
Кожен блок стиснених даних розпочинається з трьох заголовкових бітів, які мітять наступні дані
- перший біт BFINAL
- наступні 2 біти BTYPE
Зверніть увагу, що заголовкові біти не обов'язково розпочинаються з байтової межі, оскільки блок не обов'язково окуповує ціле число байтів.
BFINAL встановлюється тільки якщо це є останній блок набору даних.
BTYPE вказує як стискаються дані, наступним чином:
- 00 - без стиснення;
- 01 - стиснені з фіксованими кодами Хоффмана;
- 10 - стиснені з динамічними кодами Хоффмана;
- 11 - зарезервовано (помилка).
Єдина різниця між двома способами стиснення полягає у тому, як визначаються коди Хоффмана для літералів/довжин і зміщень.
У усіх випадках, алгоритм декодування для безпосередніх даних полягає у наступному:
циклічно виконувати
зчитати заголовок блоку з потокового вводу.
якщо збережено без компресії
пропустити будь-які біти у поточному байті
зчитати LEN і NLEN (перегляньте наступну секцію)
в іншому випадку
якщо стиснення відбувалось з динамічними кодами Хоффмана
зчитати представлення дерев кодів (перегляньте підсекцію нижче)
цикл (поки не розпізнається останній блок кодів)
розкодувати значення літералу/довжини з потоку вводу
якщо значення < 256
скопіювати значення (літеральний байт) до потокового виводу
в іншому випадку
розкодувати відстань від потокового вводу
переміститись назад на зміщення у потоці виводу, і скопіювати
довжину байтів з цієї позиції до потоку виводу.
кінець циклу
поки не отримали останній блок
Зверніть увагу, що продубльовані вказівники на рядки можуть відноситись до рядків з попереднього блоку; тобто зміщення назад може перетинати один або декілька меж блоків. Однак зміщення не може відноситись за початок вихідного потоку. (Програми, які використовують заздалегідь визначені словники можуть відхилити частину виводу; зміщення може все-одно вказувати на цю частину потоку). Зверніть увагу на те, що рядок, на який посилаються, може перекривати поточну позицію. Наприклад, якщо ми маємо два значення X i Y, і зміщення з значенням <довжина = 5, відстань = 2> додає X,Y,X,Y,X до потоку виводу.
Тепер ми опишемо кожен метод компресії по черзі.
3.2.4. Не стиснені блоки (BYTE=00)
Будь-які біти потоку вводу аж до наступної межі байту ігноруються. Остання інформація блоку містить наступні частини:
0 1 2 3 4...
+---+---+---+---+====================================+
| LEN | NLEN |... LEN байтів літеральних даних ...|
+---+---+---+---+====================================+
LEN являється кількістю байтових блоків даних блоку. NLEN являється доповненням LEN.
3.2.5. Стиснені блоки (коди довжин і зміщень).
Так як сказано вище, стиснені блоки даних формату "deflate" складаються з послідовності символів, які беруться з трьох концептуально різних абеток: літеральні байти, з абетки байтових значень (0...255), або пар <довжина, зміщення назад>, де довжини мають значення від (3...258) і зміщення має значення з (1...32768). Насправді, абетки літералів і довжин об'єднуються в одну абетку (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
Додаткові біти повинні бути інтерпретованими як машинне ціле число, яке зберігається з найбільш значущим бітом на початку, тобто, біти 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. Стиснення за допомогою фіксованих кодів Хоффмана (BTYPE=01).
Коди Хоффмана для двох абеток являються фіксованими і не представляються безпосередньо в даних. Абетка довжин кодів Хоффмана для літералів/довжин наступна:
Lit Value Біти Коди
--------- ---- -----
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. Стиснення за допомогою динамічних кодів Хоффмана (BYTE=10).
Коди Хоффмана для двох абеток з'являються у блоку одразу ж після заголовкових бітів і перед самими стисненими даними, першим являється літеральний/довжинний код після якого йде код зміщення. Кожен код визначається послідовністю кодів довжини, як обговорено у параграфі 3.2.2. Навіть для більшої компактності, послідовності кодів довжини стискаються за допомогою кодів Хоффмана. Абетка для кодів довжини являється наступною:
- 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: повторити довжинні коди нуля 3...10 разів. (3 біти довжини).
- 18: Повторити довжинний код нуль від 11 до 138 разів. (7 біт довжини).
Довжинний код 0 означає, що відповідний символ у абетці літералів/довжин і зміщень не з'являться у блоці, і не повинні брати участь у алгоритмі конструкції кодів Хоффмана наданим раніше. Якщо використовується тільки один код зміщення, він кодується використовуючи тільки один біт, а не нулем біт, в даному випадку присутній тільки один код одиничної довжини, з одним невикористаним кодом. Один код зміщення з нульовими бітами означає, що коди відстаней не використовуються взагалі (дані складаються з літералів).
Тепер ми можемо визначити формат блоку:
- 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. Ці довжинні коди інтерпретуються як трьох-бітові цілі числа (0...7); як сказано вище довжинний код 0 означає відповідний символ не використовується (літерал/довжинний або код зміщення).
- HLIT+257 довжинних кодів для абетки літералів/довжин, кодується використовуючи довжинний код коду Хоффмана.
- HDLIST+1 довжинних кодів для абетки зміщень кодується використовуючи довжинний код коду Хоффмана.
- Безпосередні дані стиснені дані блоку, закодовані використовуючи літеральні/довжинні або коди зміщення коду Хоффмана
- Літеральний/довжинний символ з значенням 256 (кінець даних - end-of-data) закодовується використовуючи літеральні/довжинні коди Хоффмана.
Повторні довжинні коди можуть мати значення з HLIT+257 до HDIST+1 довжинних кодів. Іншими словами, усі довжинні коди з однієї послідовності значень HLIT+HDIST+258.
3.3. Сумісність
Компресор може ще більше посилити вищенаведені обмеження і все-одно залишатись сумісним з стандартом. Наприклад, він може обмежити розмах зміщень до деякого значення менше ніж 32 кілобайти. Подібно, компресор може обмежити розмір блоків, отож стиснений блок буде вміщуватися у пам'яті.
Сумісний декомпресор повинен приймати повний розмах можливих значень, визначених у попередній секції, і повинен приймати блоки звичайного розміру.
4. Деталі алгоритму стиснення.
Ціль даного документу полягає у тому, щоб визначити формат стиснених даних "deflate", не торкаючись певного алгоритму, формат відноситься до стиснених даних за допомогою алгоритму LZ77 (Лампель-Зів 1977 [2]). Оскільки багато варіацій алгоритму LZ77 являються запатентованими, рекомендується, що розробники компресора будуть користуватись загальним алгоритмом, представленим у даному документі, який відомо, що не запатентований. Матеріал у цій секції не являється частиною визначення, і компресор не повинен слідувати ньому щоб бути сумісним.
Компресор перериває блок коли він визначає, що створення нового блоку і оновлення дерева буде корисним, або коли розмір блоку заповнює буфер блоку компресора.
Компресор використовує ланцюгову хеш-таблицю для знаходження дублікатів рядків, використовуючи хеш функції, які оперують на 3-х байтових послідовностях. В будь-якій точці процесу компресії, нехай XYZ будуть наступними трьома ввідними байтами, які необхідно протестувати (звичайно, усі вони не обов'язково мають однакове значення). Спочатку, компресор перевіряє хеш-ланцюг для XYZ. Якщо послідовність пуста, компресор просто записує X у якості літерального байту і розширює один байт у ввід. Якщо хеш-послідовність не пуста, що показує присутність послідовності в попередніх байтах (або, якщо нам не повезло, і деякі інші 3 байти мають такий ж хеш), компресор порівнює усі рядки з хешом для значення XYZ з фактичними ввідними даними починаючи з даної точки, і обирає найдовший збіг.
Компресор шукає хеш-послідовність починаючи з недавніми рядками, до малих відстаней і це надає перевагу кодуванням Хоффмана. Хеш-послідовності однонаправлені. Не існує видалення з хеш-послідовності; алгоритм просто відкидає співпадання з хешами, які є надто старими. Для запобігання найгіршої ситуації, дуже довгі хеш-таблиці довільно обрізаються за певної критичної довжини, які визначаються під час виконання програми.
Для покращення компресії в цілому, компресор необов'язково може відкласти секцію збігів ("ліниве співставлення" - "lazy matching"): після збігу довжиною N елементів, компресор шукає довший збіг розпочинаючи з довшого збігу починаючи з наступних ввідних байтів. Якщо він знаходить довший збіг, він обрізає попередній збіг до одиничної довжини (тобто генеруючи один літеральний байт) і після цього вивільняє довший збіг. В іншому випадку, він вивільняє оригінальний збіг, і, як описано вище, і просувається на N байтів перед тим як продовжити.
Параметри програми, яка виконується, також контролюють процедуру "лінивого співставлення". Якщо ступінь стиснення являється дуже важливим, компресор намагається завершити другий пошук не зважаючи на довжину першого пошуку. За нормальних обставин, якщо поточний збіг являється "достатньо довгим", компресор зменшує пошук для довгих збігів, це пришвидшує процес. Якщо швидкість, являється більш важливою, компресор вставляє новий рядок у хешову таблицю тільки коли жодного збігу не знайдено, або збіг не являється занадто довгим. Це зменшує ступінь компресії, але зберігає час, оскільки зменшується кількість вставлень і пошуків.
5. Виноски
[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. Міркування про безпеку
Будь-який метод стиснення даних спричиняє зменшення надмірності у даних. Відповідно, будь-які пошкодження даних ймовірно спричинять декілька ефектів і будуть важкими для відновлення. Нестиснений текст, з іншої сторони, скоріш за все залишиться читабельним, незважаючи на присутність деяких пошкоджених байтів.
Рекомендується, що системи які використовують цей формат даних забезпечують деякі механізми для перевірки цілісності стиснених даних. Перегляньте джерело [3], наприклад.
7. Вихідний код.
Вихідний код реалізації сумісного компресора і декомпресора формату "deflate" для мови програмування C доступний разом з пакунком zlib за адресою ftp://ftp.uu.net/pub/archiving/zip/zlib/.
8. Подяки
Бренди і торгові марки, які містяться в даному документі являються власністю їх відповідних власників.
Формат розробив "deflate" Філ Катз (Phil Katz). Джен-Лоуп Ґайлі (Jean-Loup Gailly) і Марк Адлер (Mark
Adler) написали відповідні програми, які користуються даною специфікацією. Ґлен Рандерс-Пірсон (Glenn Randers-Pehrson) перетворив даний документ до формату RFC i HTML.
9. Адреса автора
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>
Оригінал документу
http://www.ietf.org/rfc/rfc1951.txt