Введение в цифровую графику
Алгоритм Хаффмана
Алгоритм Хаффмана
основан на определенном анализе документа и вычислении частоты встречаемости
цветовых значений (или значений других видов информации), а затем этим значениям
в соответствии с рангом присваиваются коды сначала с минимальным количеством
битов, а затем по мере снижения частоты (уменьшения ранга) используется все
большее количество двоичных разрядов. Такой способ кодирования иногда называют
алфавитным кодированием.
Пример
Заменим также для простоты значения цвета буквами. Например, в следующей последовательности букв ААСАААВАВАВВАВСАСВСАСААССС заметно, что чаще всего встречается символ А (12 раз), затем символ С (9 раз) и, наконец, символ В (5 раз). Следовательно, символ А можно заменять кодом 0, символ С — кодом 1, а символ В — кодом 00. И так далее, если элементов для кодирования больше. В результате, если считать, что каждый символ в нашем примере кодируется 1 битом, то для передачи строки
потребуется 208 битов, а в сжатом виде объем информации составит только 31 бит.
