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

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