Первая попытка: нисходящий метод

На интуитивном уровне мы стремимся построить размеченное бинарное дерево, листья которого должны располагаться как можно ближе к корню. Именно такое строение обеспечит наименьшую среднюю глубину листа.

Естественный подход к решению этой задачи будет основан на построении дерева сверху вниз с как можно более плотной «упаковкой» листьев. Допустим, мы пытаемся разбить алфавит S на два множества и S2 так, чтобы сумма частот

букв в каждом наборе была равна в точности i. Если такое идеальное разбиение

невозможно, то мы можем опробовать следующую разбивку, ближайшую к сбалан- сированности. Затем для S1 и S2 рекурсивно строятся префиксные коды, которые образуют два поддерева от корневого узла. (В контексте цепочек битов это означа- ет, что кодировки для Sl будут начинаться с 0, а кодировки для S2 — с 1.)

Пока не совсем ясно, как конкретно определить это «почти сбалансированное» разбиение алфавита, однако более точная формулировка возможна. Такие схе- мы кодирования называются кодами Шеннона-Фано по именам Клода Шеннона и Роберта Фано — двух крупных ученых, работавших в области теории передачи информации (дисциплины, изучающей способы представления и кодирования цифровых данных). Такие префиксные коды неплохо работают на практике, но для наших текущих целей они создают своего рода «тупик»: никакая разновид- ность такой стратегии нисходящего разбиения не будет гарантированно создавать оптимальный префиксный код. Вернемся к примеру с алфавитом из пяти букв S ={a, b, c, d, e} и частотами

Существует всего один способ разбиения этого алфавита на два множества с равными частотами: {a, d} и {b, c, e}. В подмножестве {a, d} каждая буква может кодироваться одним дополнительным битом. Для {b, c, e} кодирование должно продолжаться рекурсивно, и снова существует уникальный способ разбиения множества на два подмножества с равной суммой частот. Полученный код соот- ветствует кодировке γ1, представленной размеченным деревом на рис. 4.16, b; как вы уже знаете, кодировка γ1 менее эффективна, чем префиксная кодировка γ2, со- ответствующая дереву на рис. 4.16, c.

Шеннон и Фано знали, что их метод не всегда порождает оптимальный пре- фиксный код, но не знали, как вычислить оптимальный код без поиска методом «грубой силы». Эту задачу через несколько лет решил аспирант Дэвид Хаффман — он узнал о задаче на учебном курсе, который вел Фано.

Рассмотрим некоторые идеи, которые привели Хаффмана к обнаружению жад- ного алгоритма построения оптимальных префиксных кодов.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Первая попытка: нисходящий метод:

  1. Попытка портрета
  2. Попытка заглушить чувства алкоголем
  3. Глава 10. Как противостоять попыткам манипуляции.
  4. Отстраненность - попытка говорить отвлеченно.
  5. Обращение к наркотикам —попытка не ощущать то, что мы чувствуем.
  6. ПОНЯТИЕ О МЕТОДАХ ОБУЧЕНИЯ. МЕТОД И ПРИЕМ. ОСНОВНЫЕ ПОДХОДЫ К КЛАССИФИКАЦИИ МЕТОДОВ ОБУЧЕНИЯ
  7. Ключ мог родиться только в России. Ключ к себе — ключ к системам. (это не метод среди методов, а Ключ к собственному методу)
  8. 2. Сравнительно-правовой метод – частнонаучный метод юридической науки
  9. Восходящий узел в девятом доме, Нисходящий - в третьем.
  10. Восходящий узел в пятом доме, Нисходящий - в одиннадцатом.
  11. Восходящий узел в третьем доме, Нисходящий - в девятом.
  12. Восходящий узел в двенадцатом доме, Нисходящий - в шестом.
  13. Восходящий узел в десятом доме, Нисходящий - в четвертом.
  14. § 38 Изменение старых понятий о переходе вотчинного права. – Формы приобретения по нынешнему закону. – Ввод во владение по новому нотариальному уставу. – Невыгоды от неизвестности о правах. – Попытка к регистрации поземельной собственности в России. – Вотчинная записка в прибалтийских губерниях