J tech 120. indd

4
Те
хника.
 Те
хнологии.
 Инж
енерия 
№ 
2 (12) 
2019
5) Поскольку понятия «свободной» точки на предпо-
следнем уровне дерева и на всех остальных отлича-
ются, то необходимо проверить условие, не является 
ли уровень, на котором мы находимся предпо-
следним. Если не является, то переходим к шагу 
6. Если уровень является предпоследним, то пере-
ходим к шагу 7.
6) Проверяем условие, проходят ли через текущую 
точку одно или более кодовых слова. Если да, то по-
вторяем шаги начиная с 4. Если нет, то переходим к 
шагу 8.
7) Если на 5 шаге выяснилось, что уровень, на ко-
тором находимся, является предпоследним, то прове-
ряем условие, проходят ли через эту точку 2 кодовых 
слова, так как если уровень предпоследний, то выйти 
из точки могут максимум 2 кодовых слова. Если через 
точку проходят 2 кодовых слова, то свободной точка 
не считается и повторяем шаги начиная с 4. Если 
через текущую точку на предпоследнем уровне про-
ходит одно кодовое слово, либо не проходят вовсе, то 
переходим к шагу 8.
8) Текущая точка является свободной, мы запоминаем 
ее координаты и начинаем поиск «концевых» точек 
на вышележащих уровнях.
9) На этом шаге проверяем, нашлись ли на вышеле-
жащем уровне концевые точки. Если да, то пере-
носим в «свободную» точку найденную «концевую» 
точку с наибольшей вероятностью на своём уровне 
и повторяем шаги 2–9. Если концевых точек нет на 
вышележащем уровне, то переходим к следующему 
шагу.
10. переходим на следующий уровень и повторяем шаги 
10–11.
11. Проходим по алгоритму до тех пор, пока дерево не 
будет полностью упакованным. Дерево считается 
плотно упакованным, если на нём не осталось сво-
бодных точек.
Блок-схема алгоритма эффективной упаковки пред-
ставлена на рисунке 3.
Рассмотрим наглядно алгоритм эффективной упа-
ковки на кодовом дереве [рис. 4].
Итак, после применения алгоритма эффективной 
упаковки длины кодовых слов сокращаются, и средняя 
длина кодового слова становится такой же, что и у Хаф-
фмана, а значит, разработанный алгоритм оптимален.
Выводы
Разработанный алгоритм и алгоритм Хаффмана 
были протестированы на девяти различных вариантах 
входных данных и во всех случаях показали одинаковый 
результат. Сравнение проводилось по средней длине ко-
дового слова. Критерий оценки — минимальная средняя 
длина кодового слова при условии, что кодовые слова 
удовлетворяют неравенству Крафта.
Таким образом, результаты экспериментальных ис-
следований подтвердили, что разработанный алго-
ритм кодирования является оптимальным. А значит, его 
можно успешно применять на практике в архиваторах, 
основанных на статистических методах кодирования.
Рис. 2. Блок-схема алгоритма декодирования на основе неравенства Крафта

---

Информатика и кибернетика
5
Рис. 3. Блок-схема алгоритма эффективной упаковки
Рис. 4. Алгоритм эффективной упаковки

---