DEFLATE: обратная ссылка действительно лучше?
Я делаю свой собственный компрессор 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, дружественном Хаффману?
1 ответ
Это сложная проблема, поскольку вы знаете только битовые затраты, связанные с этими решениями, после принятия всех решений, брать ли литерал или обратную ссылку. Но вы могли бы повторять и использовать затраты из предыдущего прогона, чтобы принимать эти решения при перекодировании несколько раз, пока вы не будете довольны результатом.
Это одна из вещей, которые Zopfli делает, чтобы получить лучшие коэффициенты сжатия при сохранении формата DEFLATE, в дополнение к использованию подхода с кратчайшим путем вместо жадных решений.