Дисперсия - длина
Cтраница 2
 |
Дерево кодирования Хаффмана для шестизначного множества. [16] |
Код Хаффмана генерируется как часть процесса образования дерева. Процесс начинается с перечисления входных символов алфавита наряду с их вероятностями ( или относительными частотами) в порядке убывания частоты появления. Эти позиции таблицы соответствуют концам ветвей дерева, как изображено на рис. 13.34. Каждой ветви присваивается ее весовой коэффициент, равный вероятности этой ветви. Теперь процесс образует дерево, поддерживающее эти ветви. Два входа с самой низкой относительной частотой объединяются ( на вершине ветви), чтобы образовать новую ветвь с их смешанной вероятностью. После каждого объединения новая ветвь и оставшиеся ветви переупорядочиваются ( если необходимо), чтобы убедиться, что сокращенная таблица сохраняет убывающую вероятность появления. Во время переупорядочения после каждого объединения поднимается ( всплывает) новая ветвь в таблице до тех пор, пока она не сможет больше увеличиваться. Таким образом, если образуется ветвь с весовым коэффициентом 0 2 и во время процесса находятся две другие ветви уже с весовым коэффициентом 0 2, новая ветвь поднимается до вершины группы с весовым коэффициентом 0 2, а не просто присоединяется к ней. Процесс всплытия пузырьков к вершине группы дает код с уменьшенной дисперсией длины кода, в противном случае - код с такой же средней длиной, как та, которая получена посредством простого присоединения к группе. Эта сниженная дисперсия длины кода уменьшает шанс переполнения буфера. [17]
 |
Дерево кодирования Хаффмана для шестизначного множества. [18] |
Код Хаффмана генерируется как часть процесса образования дерева. Процесс начинается с перечисления входных символов алфавита наряду с их вероятностями ( или относительными частотами) в порядке убывания частоты появления. Эти позиции таблицы соответствуют концам ветвей дерева, как изображено на рис. 13.34. Каждой ветви присваивается ее весовой коэффициент, равный вероятности этой ветви. Теперь процесс образует дерево, поддерживающее эти ветви. Два входа с самой низкой относительной частотой объединяются ( на вершине ветви), чтобы образовать новую ветвь с их смешанной вероятностью. После каждого объединения новая ветвь и оставшиеся ветви переупорядочиваются ( если необходимо), чтобы убедиться, что сокращенная таблица сохраняет убывающую вероятность появления. Во время переупорядочения после каждого объединения поднимается ( всплывает) новая ветвь в таблице до тех пор, пока она не сможет больше увеличиваться. Таким образом, если образуется ветвь с весовым коэффициентом 0 2 и во время процесса находятся две другие ветви уже с весовым коэффициентом 0 2, новая ветвь поднимается до вершины группы с весовым коэффициентом 0 2, а не просто присоединяется к ней. Процесс всплытия пузырьков к вершине группы дает код с уменьшенной дисперсией длины кода, в противном случае - код с такой же средней длиной, как та, которая получена посредством простого присоединения к группе. Эта сниженная дисперсия длины кода уменьшает шанс переполнения буфера. [19]
Страницы: 1 2