Шаг 1. Символы исходного алфавита упорядочиваются по невозрастанию вероятностей. В результате получаем последовательность (ai1,...,aiN). В этой последовательности для всех j = 1, 2,:, N - 1 выполняется соотношение aij ≥ aij+1 Шаг 2. Переменной-счётчику t присваивается значение 1: t := 1. Шаг 3. Рассматриваемую последовательность разбиваем на M групп, не меняя порядка следования символов, так чтобы суммарные вероятности символов в каждой группе были примерно одинаковы и максимально близки к 1/M. Получаем совокупность подпоследовательностей G1, G2,..., GM: G1 = (ai1, ai2, : ,ai k1), G2 = (ai k1+1, ai k1+2, ... ,ai k2), Шаг 4. Формируем t-й символ кодовых слов. Всем символам из подпоследовательности GS приписываем символ bS, s = 1, 2,.., M. Шаг 5. Переменная-счётчик увеличивается на 1: t := t + 1. Шаг 6. Просматриваем все группы-подпоследовательности. Если некоторая группа GS состоит из одного символа aj то для этого aj процесс построения кодового слова считается законченным. Для каждой из этих групп, содержащих по 2 и более символов, выполняем действия, соответствующие Шагу 3 и Шагу 4. В результате чего получаем очередные t-е символы кодовых слов. После просмотра всех групп, осуществляется переход к Шагу 5. Процесс работы алгоритма заканчивается, когда все группы будут содержать ровно по одному символу исходного алфавита. Обратим внимание на ряд особенностей, которые нужно иметь в виду при практическом применении этого метода. Первое. При разбиении на группы не разрешается переставлять элементы с целью выравнивания сумм вероятностей. Порядок, полученный на Шаге 1, сохраняется в течение всего времени работы алгоритма. Второе. Разбиение на группы не всегда выполняется однозначным образом. Это связано с тем, что иногда некоторый "пограничный" символ ai может быть присоединён к любой из двух подгрупп GS или GS+1 равноценным образом. Если ai присоединяется последним символом в GS, то в ней суммарная вероятность станет на p(ai) больше, чем в группе GS+1. Если же ai включить первым символом в GS+1, то большая сумма вероятностей будет в GS+1. Подобная ситуация может возникнуть не один раз, следовательно, результат кодирования однозначно не определяется. Можно получить несколько равноценных между собой кодов для одного и того же алфавита. Иногда с целью получения однозначности вводят дополнительные условия. Например, можно потребовать, чтобы большее значение суммы "%'.ob-.ab%) было в группе с меньшим номером. Однако такое требование не является обязательным. Третье. Следует на всех шагах придерживаться одинаковой последовательности приписывания символов кодового алфавита группам символов исходного алфавита. Эту последовательность приписывания следует зафиксировать до начала работы алгоритма. Возможны различные способы, но обычно придерживаются следующего правила: символам из группы с номером S приписывают S-й символ кодового алфавита. Это правило присутствует и в приведённом выше алгоритме.  8  Комментарии к статье  8 8  Обсудить в чате