Изменения
Перейти к навигации
Перейти к поиску
Строка 27:
Строка 27: − +
→Кодирование Хаффмана
Этот процесс можно представить как построение [[Дерево (теория графов)|дерева]], корень которого — символ с суммой вероятностей объединенных символов, получившийся при объединении символов из последнего шага, его n<sub>0</sub> потомков — символы из предыдущего шага и т. д.
Этот процесс можно представить как построение [[Дерево (теория графов)|дерева]], корень которого — символ с суммой вероятностей объединенных символов, получившийся при объединении символов из последнего шага, его n<sub>0</sub> потомков — символы из предыдущего шага и т. д.
Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от листа дерева, соответствующего текущему символу, до его корня, накапливая биты при перемещении по ветвям дерева (первая ветвь в пути соответствует младшему биту). Полученная таким образом последовательность битов является кодом данного символа, записанным в обратном порядке.
Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от корня до листа дерева, соответствующего текущему символу, накапливая биты при перемещении по ветвям дерева (первая ветвь в пути соответствует младшему биту). Полученная таким образом последовательность битов является кодом данного символа, записанным в обратном порядке.
Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом.
Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом.