Первая попытка: нисходящий метод
Естественный подход к решению этой задачи будет основан на построении дерева сверху вниз с как можно более плотной «упаковкой» листьев. Допустим, мы пытаемся разбить алфавит 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.
Шеннон и Фано знали, что их метод не всегда порождает оптимальный пре- фиксный код, но не знали, как вычислить оптимальный код без поиска методом «грубой силы». Эту задачу через несколько лет решил аспирант Дэвид Хаффман — он узнал о задаче на учебном курсе, который вел Фано.
Рассмотрим некоторые идеи, которые привели Хаффмана к обнаружению жад- ного алгоритма построения оптимальных префиксных кодов.
Еще по теме Первая попытка: нисходящий метод:
- Попытка портрета
- Попытка заглушить чувства алкоголем
- Глава 10. Как противостоять попыткам манипуляции.
- Отстраненность - попытка говорить отвлеченно.
- Обращение к наркотикам —попытка не ощущать то, что мы чувствуем.
- ПОНЯТИЕ О МЕТОДАХ ОБУЧЕНИЯ. МЕТОД И ПРИЕМ. ОСНОВНЫЕ ПОДХОДЫ К КЛАССИФИКАЦИИ МЕТОДОВ ОБУЧЕНИЯ
- Ключ мог родиться только в России. Ключ к себе — ключ к системам. (это не метод среди методов, а Ключ к собственному методу)
- 2. Сравнительно-правовой метод – частнонаучный метод юридической науки
- Восходящий узел в девятом доме, Нисходящий - в третьем.
- Восходящий узел в пятом доме, Нисходящий - в одиннадцатом.
- Восходящий узел в третьем доме, Нисходящий - в девятом.
- Восходящий узел в двенадцатом доме, Нисходящий - в шестом.
- Восходящий узел в десятом доме, Нисходящий - в четвертом.
- § 38 Изменение старых понятий о переходе вотчинного права. – Формы приобретения по нынешнему закону. – Ввод во владение по новому нотариальному уставу. – Невыгоды от неизвестности о правах. – Попытка к регистрации поземельной собственности в России. – Вотчинная записка в прибалтийских губерниях