Изменения

Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> — соответствующий ему набор весов. Тогда алгоритм выброра выбора набора бинарных кодов <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex>, такой, что:

0. ''Введем следующие понятия''. Две вершины называются совместимой парой, если они соседнии соседние или если между ними нет вершин алфавита. Две вершины называются минимальной парой, когда их суммарный вес наименьший из всех, из всех таких выбираеться выбирается пара с самой левой вершиной, из всех таких та у которой правый узел расположен левее. Минимальной совместимой парой называется наименьшая пара из всех совместимых.

1. ''Комбинирование''. По данной последовательности из n вершин строим последовательность из <tex>n-1</tex> вершины, комбинируя минимальную совместимую пару и заменяя ее левую вершину вершиной с весом <tex> w = w_{l} + w_{r} </tex> и удаляя правую. Эта процедура повторяется до дех тех пор пока не останеться останется одна вершина.

Заметим, что перестройку легко можно организовать с помощью сдеующего секового следующего стекового алгоритма.

Опредилим Определим уровни для каждого листа <tex>L= \{</tex> ''3,3,5,5,4,3,3,3,3,4,4'' <tex>\} </tex>.

Осталось только назначить код для каждого символа, это делаеться делается аналогично коду Хаффмана, левым ребрам назначается 0, а правым 1.