Зачем сочетать Хаффмана и lz77?
Я занимаюсь реверс-инжинирингом в игре Gameboy Advance, и я заметил, что разработчики оригиналов написали код, который имеет два системных вызова для распаковки уровня, используя Huffman и lz77 (в этом порядке).
Но зачем использовать Huffman + lzZ7? В чем преимущество этого подхода?
0 ответов
Использование доступных библиотек
Возможно, что разработчики используют DEFLATE (или какой-либо аналогичный алгоритм) просто для того, чтобы иметь возможность повторно использовать протестированное и отлаженное программное обеспечение, а не писать что-то новое с нуля (и тратить много времени на тестирование и исправление всех проблем. причудливые крайние случаи).
Почему и Хаффман, и LZ77?
Но почему DEFLATE, Zstandard, LZHAM, LZHUF, LZH и т. Д. Используют и Huffman, и LZ77?
Потому что эти 2 алгоритма обнаруживают и удаляют 2 разных вида избыточности, общих для многих файлов данных (уровни видеоигр, английский и другой текст на естественном языке и т. Д.), И их можно комбинировать, чтобы получить лучшее чистое сжатие, чем любой из них по отдельности. (К сожалению, большинство алгоритмов сжатия данных нельзя комбинировать таким образом).
Детали
В английском языке две наиболее распространенные буквы - это (обычно) "е", а затем "т". Итак, какая пара самая распространенная? Вы могли бы угадать "ээ", "эт" или "те" - нет, это "й".
LZ77 хорош в обнаружении и сжатии таких общих слов и слогов, которые встречаются гораздо чаще, чем можно предположить, исходя только из частотности букв.
Буквенно-ориентированный Хаффман хорошо обнаруживает и сжимает файлы, используя только частоту букв, но не может обнаружить корреляции между последовательными буквами (обычными словами и слогами).
LZ77 сжимает исходный файл в промежуточную последовательность буквальных букв и "копий". Затем Хаффман сжимает эту промежуточную последовательность. Часто эти "элементы копирования" уже намного короче, чем была бы исходная подстрока, если бы мы пропустили шаг LZ77 и просто Хаффман сжал исходный файл. И Хаффман сжимает буквальные буквы в промежуточной последовательности так же хорошо, как и те же самые буквы в исходном файле.
Таким образом, уже этот двухэтапный процесс создает файлы меньшего размера, чем любой алгоритм по отдельности. В качестве бонуса обычно элементы копирования также сжимаются по методу Хаффмана для большей экономии места для хранения.
Как правило, большинство программ сжатия данных состоит из этих двух частей. Сначала они запускают исходные данные через " преобразование" или несколько преобразований, также называемых "декорреляторами", обычно сильно настроенными на конкретный вид избыточности в конкретном виде сжимаемых данных (преобразование DCT JPEG, компенсация движения MPEG и т. Д.).) или настроены на ограничения человеческого восприятия (слуховая маскировка MP3 и т. д.). Затем они пропускают промежуточные данные через один " энтропийный кодер" (арифметическое кодирование или кодирование Хаффмана или кодирование с асимметричной системой счисления), который практически одинаков для всех типов данных.