Алгоритм Хаффмана. 
Кодирование информации

Это алгоритм архивации без потери качества. Представим себе самый общий случай, когда в файле представлена большая часть таблицы ASCII и почти нет однородных последовательностей. В таком случае выгоду можно получить только если разные байты (символы) встречаются в данном файле с различной частотой. Тогда наиболее часто встречающиеся символы могут быть закодированы меньшим числом бит, а те, что встречаются довольно редко наоборот большим числом бит. В итоге результирующий файл с большой вероятностью будет меньшего объема, чем исходный.

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

Можно представить, что все файлы — это тексты, написанные в алфавите, состоящем из 256 букв (так оно на самом деле и есть). Рассмотрим все множество файлов, размер которых не превышает n byte (где n произвольное число). И допустим, что существует некий алгоритм кодирования, который любой из этих файлов сжимает с «положительной» эффективностью. Тогда множество всех их архивов содержится во множестве всех файлов, размер которых меньше n byte. Согласно нашему предположению существует взаимно-однозначное соответствие между двумя конечными множествами, число элементов в которых не совпадает. Чего быть не может. Отсюда можно сделать довольно значимые выводы: 1) не существует архиватора, который бы одинаково хорошо паковал любые файлы, 2) для любого архиватора найдутся файлы, в результате сжатия которых будут получаться архивы в лучшем случае не меньшего размера, чем исходные файлы.