Подход Хаффмана

Попытки создать оптимальный неравномерный код начинается с азбуки Морзе (код неравномерный, если объем кодировки для разных знаков различный).

Основная идея неравномерного кода – если буква встречается чаще, то код её должен быть короче. Такими оптимизированными неравномерными кодами занимались так же Шеннон и Фано.

Хаффман предложил строить коды по типу бинарного дерева. Он исходил из того, что кодировать придется в двоичном коде через 0 и 1, поэтому он предложил разместить буквы какого-то текста в порядке убывания его частоты или вероятности (частота – количество букв в тексте; вероятность – отношение количества данной буквы к общему количеству букв).

Подход Хаффмана хорош тем, что получаем неравномерный код в соответствии с частотами каждой буквы.

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

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

Алгоритм Хаффмана легко реализуется в ЭВМ и воспроизводится. Образуется в результате кодирования дерево, выражается в качестве табличного соответствия и прилагается к сжатому документу. Это самый быстрый алгоритм.

Если заданы произвольные бытовые данные, то размер буквы можно устанавливать самому. Наибольшую эффективность на практике оказывают буквы размером 18-20 бит.

Слишком короткие буквы (по битам) встречаются очень часто, но степень сжатия будет невысока, слишком длинные буквы (более 3 байт) фактически приближается к алгоритму KWE, так как буквы встречаются все меньше и меньше. Значит, есть некий оптимальный выбор длины буквы.

Как можно убедиться алгоритмы RLE и KWE они дополняют друг друга, поэтому их комбинируют.

Дата добавления: 2015-07-11