DEFLATE: обратная ссылка действительно лучше?

Question

Я делаю свой собственный компрессор DEFLATE, который почти каждый раз превосходит библиотеку ZLIB.

В формате DEFLATE (LZ77) поток данных содержит байтовый литерал или обратную ссылку, говорящую, чтомы должны скопировать последовательность байтов из предыдущих декодированных байтов.Компрессоры обычно выполняют LZ77 (находят обратные ссылки - как можно больше), а затем создают дерево Хаффмана и сжимают этот поток байтов / ссылок.

Возможен крайний случай: ссылка на 3 одинаковых байта,длина кодируется 15 битами, расстояние - 15 + 13 битами, а закодированный байт составляет всего 1 бит в нашем дереве Хаффмана.Разница составляет 43 против 3 бит.Использование ссылки увеличило вывод в 14 раз по сравнению с байтами кодирования напрямую.

Моя проблема заключается в следующем: у меня есть текстовый файл размером 10 097 918 B.ZLIB покрывает 9,089,334 B ссылками в своем LZ77, в то время как мой компрессор покрывает 9,305,056 B. Таким образом, я могу сказать, что мой LZ77 лучше.

Но ZLIB дает 1,329,309 B файла, в то время как моя программа дает 1,381,153 Bфайл (оба строят оптимальное дерево Хаффмана).Таким образом, лучший LZ77 приводит к худшему кодированию Хаффмана.Есть какие-нибудь исследования о LZ77, дружественном Хаффману?

Answer 1

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

Это один изчто делает Zopfli, чтобы получить лучшие коэффициенты сжатия при сохранении формата DEFLATE, в дополнение к использованию подхода с кратчайшим путем вместо жадных решений.