Алгоритмы cжатия изображений
Определение 5 Коды, определяемые схемой S
lср= l*, называются кодами с минимальной избыточностью, или кодами Хаффмана.
Коды с минимальной избыточностью дают в среднем минимальное увеличение длин слов при соответствующем кодировании.
В нашем случае, алфавит Y ={a1,..., ar} задает символы входного потока, а алфавит W ={0,1}, т.е. состоит всего из нуля и единицы.
Алгоритм построения схемы S можно представить следующим образом:
Шаг 1. Упорядочиваем все буквы входного алфавита в порядке убывания вероятности. Считаем все соответствующие слова Bi из алфавита W ={0,1} пустыми.
Шаг 2. Объединяем два символа air-1 и air с наименьшими вероятностями pi r-1 и pi r в псевдосимвол a'{air-1 air} c вероятностью pir-1+pir. Дописываем 0 в начало слова Bir-1 (Bir-1=0Bir-1), и 1 в начало слова Bir (Bir=1Bir).
Шаг 3. Удаляем из списка упорядоченных символов air-1 и air, заносим туда псевдосимвол a'{air-1air}. Проводим шаг 2, добавляя при необходимости 1 или ноль для всех слов Bi, соответствующих псевдосимволам, до тех пор, пока в списке не останется 1 псевдосимвол.
