Да, в deflate таблица сжата. Схема такая.
1. Если для каждого символа известна длина кода, не сам код, а его длина, то по длинам можно восстановить и коды. Есть правило, записано в протоколе, как по длинам восстанавливать коды, так что разночтений быть не может.
2. Для исходных данных максимальная длина кодов 15 бит. Значит каждому символу нужно сопоставить длину, число от 0 до 15 (нулевая длина — символ не используется).
3. Таблица (список длин по всему алфавиту) сначала подлежит RLE-сжатию, — серии одинаковых длин и нулевые серии кодируются особыми символами. Всего этих символов 19:
0-15 -длины кодов;
16-18 -серии.
4. Таблица после RLE кодируется другими кодами Хаффмана, этих кодов не более 19-ти, а максимальная длина 7 бит.
5. Таблица для этих «других» кодов Хаффмана, вернее длины этих кодов, даются напрямую без всякого сжатия, длины эти трёхбитные, и занимают максимум
3*19=57 бит. Еще 17 бит занимает заголовок заголовка блока. Итого блок содержит следующее (сплошным битовым потоком, без выравнивания на границы байтов):
1. Заголовок заголовка — 17 бит.
2. Таблица «других» кодов Хаффмана (их длины) — до 57 бит.
3. Таблица настоящих кодов Хаффмана (их длины) — сколько получится.
4. Собственно сжатые исходные данные.
Да, вот такая двухуровневая «хаффманизация», там всё продумано.
Примечание.
deflate не только Хаффманом сжимает, но еще и ссылками на подстроки. Наример, если подстрока «Таблица» ранее встречалась, то даст ссылку «длина-смещение» вместо самой подстроки.
Да, в deflate таблица сжата. Схема такая.
1. Если для каждого символа известна длина кода, не сам код, а его длина, то по длинам можно восстановить и коды. Есть правило, записано в протоколе, как по длинам восстанавливать коды, так что разночтений быть не может.
2. Для исходных данных максимальная длина кодов 15 бит. Значит каждому символу нужно сопоставить длину, число от 0 до 15 (нулевая длина — символ не используется).
3. Таблица (список длин по всему алфавиту) сначала подлежит RLE-сжатию, — серии одинаковых длин и нулевые серии кодируются особыми символами. Всего этих символов 19:
0-15 -длины кодов;
16-18 -серии.
4. Таблица после RLE кодируется другими кодами Хаффмана, этих кодов не более 19-ти, а максимальная длина 7 бит.
5. Таблица для этих «других» кодов Хаффмана, вернее длины этих кодов, даются напрямую без всякого сжатия, длины эти трёхбитные, и занимают максимум
3*19=57 бит. Еще 17 бит занимает заголовок заголовка блока. Итого блок содержит следующее (сплошным битовым потоком, без выравнивания на границы байтов):
1. Заголовок заголовка — 17 бит.
2. Таблица «других» кодов Хаффмана (их длины) — до 57 бит.
3. Таблица настоящих кодов Хаффмана (их длины) — сколько получится.
4. Собственно сжатые исходные данные.
Да, вот такая двухуровневая «хаффманизация», там всё продумано.
Примечание.
deflate не только Хаффманом сжимает, но еще и ссылками на подстроки. Наример, если подстрока «Таблица» ранее встречалась, то даст ссылку «длина-смещение» вместо самой подстроки.
dxdy.ru/post1324268.html#p1324268