2. Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагается равной сумме вероятностей составляющих его символов. В конце концов, мы построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него;
3. Прослеживаем путь к каждому листу дерева помечая направление к каждому узлу (например, направо - 1, налево - 0).
Поясним создание дерева с использованием иллюстраций :
A B C D E
10 5 8 13 10
B C A E D
5 8 10 10 13
A E BC D
10 10 13 13
BC D AE
13 13 20
AE BCD
20 26
AEBCD
46
Таким образом, построено дерево
Бинарное дерево
Теперь, если в тексте встречается, например, символ "d", то вместо того, чтобы выделять этому символу байт, после сжатия символ займет всего 2 бита (01).
ПРИМЕЧАНИЕ:
JPEG/JFIF файловый формат использует формат Motorola для целых (двухбайтовых) значений, НЕ формат Intel, то есть: сначала старший байт, затем
Русская версия