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 таблицу мусора только, когда никакое соответствие не было найдено, или когда совпадение — не "слишком длинное ". Это приводит к деградации коэфициента сжатия, но приводит к экономии времени, так как обходится меньшим количествам процедур вставки и меньшим количествам процедур поиска.