Может ли DEFLATE сжимать повторяющиеся строки размером до 32 КБ? - PullRequest
Новая
       143

Может ли DEFLATE сжимать повторяющиеся строки размером до 32 КБ?

0 голосов
/ 10 июля 2020

Согласно СПЕЦИФИКАЦИЯ c:

Обзор сжатого представления

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

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

Каждый блок состоит из двух частей: пары деревьев кодов Хаффмана, которые описывают представление сжатого часть данных и часть сжатых данных. (Сами деревья Хаффмана сжимаются с использованием кодирования Хаффмана.) Сжатые данные состоят из серии элементов двух типов: буквальных байтов (строк, которые не были обнаружены как дублированные в предыдущих 32 КБ входных байтов), и указателей на повторяющиеся строки. , где указатель представлен в виде пары . Представление, используемое в формате «deflate», ограничивает расстояния до 32 Кбайт и длину до 258 байтов, но не ограничивает размер блока, за исключением несжимаемых блоков, которые ограничены, как указано выше.

Итак, указателей на повторяющиеся строки только go назад 32 КиБ, но, поскольку размер блока не ограничен, может ли дерево кода Хаффмана хранить две повторяющиеся строки более чем на 32 КиБ в качестве одного и того же кода? Тогда ограничивающим фактором является размер блока?

Ответы [ 2 ]

1 голос
/ 11 июля 2020

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

1 голос
/ 10 июля 2020

Дерево Хаффмана для расстояний содержит коды от 0 до 29 (таблица ниже); код 29, за которым следует 8191 в «простых» битах, означает «расстояние 32768». Это жесткое ограничение в определении Deflate. Размер блока не ограничен. Собственно размер блока нигде не хранится: блок - это бесконечный поток. Если вы хотите остановить блокировку, вы отправляете для этого код конца блока. 

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