Метод Хаффмана

I. Общие сведения о сжатии данных

В информатике и теории информации сжатие данных или исходное кодирование представляет собой процесс кодирования информации с использованием меньшего количества битов (или других единиц, несущих информацию), чем некодированное представление будет использоваться с использованием конкретных схем кодирования. Например, этот текст может быть закодирована с меньшим количеством бит, если кто-то должен принять соглашение о том, что слово «сжатие» будет закодировано как «comp». Одним популярным экземпляром сжатия, с которым знакомы многие пользователи компьютеров, является формат ZIP-файла, который, а также обеспечение сжатия, действует как архиватор, сохраняя много файлов в одном выходном файле.
Как и в случае любой формы связи, сжатая передача данных работает только тогда, когда и отправитель, и получатель информации понимают схему кодирования. Например, этот текст имеет смысл только в том случае, если приемник понимает, что он предназначен для интерпретации как символов, представляющих английский язык^[1]. Аналогично, сжатые данные могут быть поняты только в том случае, если метод декодирования известен приемнику. Некоторые алгоритмы сжатия используют это свойство для шифрования данных во время процесса сжатия, так что декомпрессия может быть достигнута только уполномоченной стороной (например, с использованием пароля).
Сжатие полезно, поскольку оно помогает снизить потребление дорогостоящих ресурсов, таких как дисковое пространство или пропускная способность передачи. С другой стороны, сжатые данные должны быть несжаты для просмотра (или прослушивания), и эта дополнительная обработка может нанести ущерб некоторым приложениям. Например, для схемы сжатия видео может потребоваться дорогостоящее аппаратное обеспечение для того, чтобы видео было декомпрессировано достаточно быстро, чтобы его можно было разглядеть по мере его распаковки (у вас всегда есть возможность полностью распаковать видео до его просмотра, но это неудобно и требует место для хранения несжатого видео). Таким образом, конструкция схем сжатия данных предполагает компромисс между различными факторами, включая степень сжатия, количество введенных искажений (при использовании схемы сжатия с потерями) и вычислительные ресурсы, необходимые для сжатия и распаковки данных.
Существуют две основные категории алгоритмов сжатия: с потерями и без потерь. Алгоритмы сжатия с потерями включают в себя уменьшение размера файла, обычно путем удаления мелких деталей, требующих большого объема данных для хранения при полной точности.
При сжатии с потерями невозможно восстановить исходный файл из-за удаления важных данных. Сжатие с потерями наиболее часто используется для хранения изображений и аудиоданных, и, хотя оно позволяет достичь очень высоких коэффициентов сжатия путем удаления данных.