Задача 7.2.2

Яку мінімальну кількість кодових комбінацій необхідно вилучити із множини кодових комбінацій 00, 01, 10, 1110, 1111, 0, 101, 1000, 1001, 110, щоб ті, які залишаться, утворювали префіксний код? Що це за комбінації?

Розв’язання.Задачу можна розв’язати методом перебору. Починаючи з більш коротких кодових комбінацій, з’ясовуємо, чи не збігається вона з початковою частиною кожної більш довгої. Якщо збіг має місце, коротку кодову комбінацію вилучаємо.

Рис. 7.3. Кодове дерево до задачі 7.2.2

Інший метод полягає в побудові кодового дерева, в якому є вузли, що відповідають усім кодовим комбінаціям, наведеним в умовах задачі, та вилученні тих кодових комбінацій, які відповідають некінцевим вузлам. Таке дерево зображено на рис.7.3. Некінцевим вузлам дерева відповідають кодові комбінації 0 та 10 (вони закреслені). Тобто, якщо із переліку кодових комбінацій, наведених в умовах задачі, вилучити всього дві комбінації, а саме: 0 та 10, то комбінації, що залишаться, будуть утворювати префіксний код.