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