36. Алгоритмы сжатия информации

Имеется файл с данными. Данные представляют собой последовательность символов .Нужно закодировать символы таким образом, чтобы

1) размер файла уменьшился;

2) исходный файл можно было бы восстановить из сжатого

Каждый символ кодируется последовательностью битов (например, ASCII-кодом, в котором каждый символ кодируется 8 битами)

Идея: кодировать символы таким образом, чтобы выполнялось следующее:

чем чаще встречается символ, тем короче его код .

Алгоритм Хаффмана

Пусть имеется файл с размером 100 байт,

состоящий из символов A,B,C,D,E,F.

1)Посчитаем число вхождений каждого символа

2) Отсортируем символы по частоте их вхождений

Нужно еще хранить и дерево кодирования!

В дереве 11 вершин, каждая должна содержать указатели на своего правого и левого сына. Каждый указатель – например 4 байта.

Итого получаем 4*11 = 44 байта