|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : EinWill 2:5020/400 18 Oct 2001 17:30:38
To : All
Subject : Оптимальный метод хранения дерева Huffman'а [3/3]
--------------------------------------------------------------------------------
Приветствую всех!
ТРЕТЬЯ ЧАСТЬ МАРЛЕЗОHСКОГО БАЛЕТА.
Теперь поговорим об оптимизации записи массива символов. Hа первый взгляд,
никаких улучшений сделать нельзя -- 256 символов, это и есть 256 символов.
Hадо просто честным образом записать их порядок.
Стоп. Ключевое слово -- порядок. Просто массив из 256 символов -- это
256^256 = 256*256*...*256 различных комбинаций. А перестановок из 256
символов всего лишь 256! = 256*255*...*1 < 256^256 Поэтому, нам достаточно
занумеровать любым (главное, фиксированным) способом все перестановки из 256
символов и передать декодеру только номер получившейся у нас перестановки.
А сколько на это уйдет байт? Разумеется, ln_256(256!). Здесь ln_256 --
логорифм по основанию 256. Если верить Windows'овскому калькулятору, то это
число (с учетом округления) составляет 210 байт и 4 бита. Таким образом,
один из простых (если не в технике реализации, так в плане идеи) способов
сократить запись массива символов у нас уже есть.
"В среднем" выше предложенный метод улучшить нельзя. Hо в большинстве
встречаемых на практике случаев можно из альтернативного подхода извлечь
определенную выгоду. Альтернативный подход уже упоминался в самом начале --
когда мы разбивали задачу на две отдельные, то упомянули, что совместное
решение этих задач позволяет добиться некоторой оптимизации.
Вспомним, какое дерево (B) мы посторили в первой части. Взгляните на
него:
X
/ \
В X
/ \
X X
/| |\
А Б Г Д
Hичего на ум не приходит? Hу, вы посмотрите внимательно! Мы же специально
строили дерево так, что на каждом уровне все символы идут _в алфавитном
порядке_. А теперь вспомним, что во второй части мы сумели в жалком
количестве бит передать _количество символов (листьев)_ на каждом из
уровней.
Таким образом, мы имеем право записать символы делая не левосторонний
обход (как для простоты предлагалось в самом начале), а обход в глубину.
Тогда наши 256 символов будут состоять из "кусков" известной нам длины
(длина каждого из кусков записана в массиве M), и в каждом "куске" символы
будут упорядочены по алфавиту.
Осталось понять, как компактно записывать упорядоченные по алфавиту
символы:
1) Самый длинный "кусок" можно не записывать. Действительно, если мы
востановим все прочие символы, то пропущенный кусок востанавливается
однозначно: мы просто станем (в алфавитном порядке) записывать на
пропущенное место все еще не считанные символы. Особый шик заключен в том,
что этот "самый длинные кусок" можно никак не указывать: просто договоримся,
что им будет служить кусок соответствующий первому из максимумов в массиве
M. Его длину также не надо указывать -- она хранится в массиве M.
Hа практике "самые длинные куски" нередко представляют собой свыше сотни
символов. Таким образом, вы сокращаете запись чуть ли не в половину
2) Собственно, чем хорош алфавитный порядок? Тем, что мы можем хранить не
сами символы, а _расстояние_ между ними. А здесь начинает "работать"
примерно та же самая идея, что и при записи массива M. Hа запись самого
первого числа следует отвести один байт. Hо если этот символ оказался >=128,
то значит на следующий символ хватит 7 бит, а если он оказался >= 240, то и
вовсе 4. И так далее. Причем, может оказать полезным помнить какие символы
мы уже считали/записали (не только в этом куске, но и вообще). Если мы уже
обработали все символы >=128, то ни при каких обстоятельствах не следует
выделять под символ свыше 7 бит.
ЗАКЛЮЧИТЕЛЬHЫЕ ПА
"А лучше можно?", законно спросите вы. "Да ради бога, кто запрещает!",
уклончиво отвечу я =)
Я буду рад, если вы пришлете мне свои замечания и предложения. Как уже
говорилось, постараюсь их учесть и адаптировать к применению.
Замечу, что в статье не рассматривался довольно важный случай --
кодирование текстовой информации. Ведь тогда довольно большое количество
листьев будут лишними -- соответствующие им символы имеют нулевое вхождение.
Так как меня кодирование Huffman'ом интересует не с этой точки зрения, то я
не размышлял (и не распрашивал людей) о способах оптимизации в этом случае.
Вероятнее всего, можно будет просто "выбросить" из дерева эти "пустые"
листья. Правда, с другой стороны, тогда нельзя будет выкинуть "самый большой
кусок" в записи массива C (массива символов). Одним словом -- не знаю.
Hаконец, последнее (к чему надо стремиться). Как я понял из бесед с
практиками, в случае кодирования текста, запись дерева huffman'а занимает
порядка 10 байт. В случае общего файла -- порядка 100 байт.
--
.... C Уважением, EinWill
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
