Изменения
Новая страница: «== Алгоритм == Для построения <tex>n</tex>-ичного кода Хаффмана надо использовать операцию сжат...»
== Алгоритм ==
Для построения <tex>n</tex>-ичного кода Хаффмана надо использовать операцию сжатия алфавита, при которой каждый раз сливаются не две, а <tex>n</tex> букв исходного алфавита, имеющих наименьшие вероятности.Сжатие алфавита, при котором <tex>n</tex> букв заменяются на одну, приводит к уменьшению числа букв на <tex>n-1</tex>; так как для построения <tex>n</tex>-ичного кода, очевидно, требуется, чтобы последовательность сжатий в конце концов привела нас к алфавиту из <tex>n</tex> букв (сопоставляемых <tex>n</tex> сигналам кода), то необходимо, чтобы число <tex>m</tex> букв первоначального алфавита было представимо в виде <tex>n = m + k(m - 1</tex> ),<tex>k \in \mathbb{Z}</tex>. Этого, однако, всегда можно добиться, добавив, если нужно, к первоначальному алфавиту еще несколько фиктивных букв, вероятности которых считаются равными нулю. После этого построение <tex>n</tex>-ичного кода Хаффмана и доказательство его оптимальности (среди всех <tex>n</tex>-ичных кодов) проводятся уже точно так же, как и случае двоичного кода.
Для построения <tex>n</tex>-ичного кода Хаффмана надо использовать операцию сжатия алфавита, при которой каждый раз сливаются не две, а <tex>n</tex> букв исходного алфавита, имеющих наименьшие вероятности.Сжатие алфавита, при котором <tex>n</tex> букв заменяются на одну, приводит к уменьшению числа букв на <tex>n-1</tex>; так как для построения <tex>n</tex>-ичного кода, очевидно, требуется, чтобы последовательность сжатий в конце концов привела нас к алфавиту из <tex>n</tex> букв (сопоставляемых <tex>n</tex> сигналам кода), то необходимо, чтобы число <tex>m</tex> букв первоначального алфавита было представимо в виде <tex>n = m + k(m - 1</tex> ),<tex>k \in \mathbb{Z}</tex>. Этого, однако, всегда можно добиться, добавив, если нужно, к первоначальному алфавиту еще несколько фиктивных букв, вероятности которых считаются равными нулю. После этого построение <tex>n</tex>-ичного кода Хаффмана и доказательство его оптимальности (среди всех <tex>n</tex>-ичных кодов) проводятся уже точно так же, как и случае двоичного кода.
