J tech 120. indd

Разработка алгоритма декодирования 
на основе неравенства Крафта
На вход программы декодирования подается код (по-
следовательность кодовых слов) полученный при коди-
ровании полученного на ход сообщения.
1. Осуществляем проверку, не пуст ли массив данных? 
Если не пуст, то переходим к следующему шагу. Если 
пуст, то сравниваем найденные кодовые слова с за-
помненными, находим соответствующие символы и 
выводим дешифрованное сообщение.
2. Проходим по введенной последовательности 0 и 1 по 
ветвям имеющегося дерева от его корня к листьям 
(концевым точкам) на каждом шаге сравнивая ко-
ординаты узла с известными координатами концевых 
точек. Проверяем, совпадают ли координаты узла с 
координатами одной из концевых точек (l
i
, k)? Если 
нет, то повторяем этот шаг снова. Если да, то запо-
минаем найденное кодовое слово и возвращаемся к 
шагу 2.
Блок-схема алгоритма декодирования представлена 
на рисунке 2.
Разработка алгоритма эффективной 
упаковки
В предыдущем абзаце нами уже было закодировано 
сообщение «колобок полотенце уволок» и построено 
кодовое дерево. Но в сравнении с методом Хаффмана 
средняя длина кодового слова больше, чем у Хаффмана. 
Некоторые кодовые слова по разработанному методу 
получаются длиннее, чем у Хаффмана.
Суть алгоритма уплотнения в том, чтобы сократить 
по нашему методу и соответственно увеличить эффек-
тивность кодирования. Это возможно за счёт наличия 
«свободных» точек на кодовом дереве, в которые можно 
перенести кодовые слова с более высоких уровней, тем 
самым избавляясь от избыточности и сокращая длину 
некоторых кодовых слов.

---

Информатика и кибернетика
3
Опишем алгоритм эффективной упаковки.
Проходим от корня дерева по всем уровням и ищем 
«свободные» точки.
Свободными точками для всех уровней дерева кроме 
предпоследнего будем считать узлы, которые не явля-
ются кодовым словом (концевой точкой), и из которых 
не выходит ни одно кодовое слово. Для предпоследнего 
уровня «свободной» точкой считается та, которая не 
является концевой и из которой не выходит 2 кодовых 
слова, то есть либо ноль, либо одно.
1) Итак, начиная с первого уровня первым делом прове-
ряем, не является ли этот уровень последним? Если 
он последний, то алгоритм упаковки не имеет смысла 
и закодированное сообщение остаётся неизменным. 
Если уровень не является последним, то переходим к 
следующему шагу.
2) На каждом уровне осуществляем проход по всем 
точкам по порядку, 1≤k≤2
l
и проверяем, не является 
ли данная точка кодовым словом (концевой), так как 
это необходимое условие для «свободной» точки.
3) Если на предыдущем шаге проверяемая точка оказа-
лась «концевой», то переходим к шагу 4, а если нет, 
то переходим к шагу 5.
4) Проверяем, не является ли данная точка последней 
на уровне. Если является, то переходим на следу-
ющий уровень и повторяем шаги 1–4, если не явля-
ется, то переходим на следующую по порядку точку и 
повторяем шаги 2–4.
Рис. 1. Блок-схема алгоритма кодирования на основе неравенства Крафта

---