|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Andrew Plyako 2:5030/922.20 14 Oct 2001 01:44:12 To : Petr Koroli Subject : Huffman -------------------------------------------------------------------------------- PK> Может не совсем топик, но не знаю куда обратиться. Ru.Compress? PK> Возникла проблема с реализацией сабжа. PK> Подскажите каким образом создавать дерево Строим дерево для байтов: 1) Считаем число вхождений каждого байта в исходный поток (текст). 2) Формируем 256 элементов (будущие листья дерева), каждый из которых соответствует одному байту. Значение элемента = число вхождений данного байта в текст. 3) Сортируем текущие набор элементов по возрастанию их значений 4) Выбираем два наименьших елемента (A и B, A<=B) и из них формируем новый элемент (узел С) со значением равным сумме значений выбранных двух элементов (C=A+B). A (наименьший из двух выбранных элементов) объявляется левым потомком узла C, B -- правым. 5) Убираем из рассмотрения элементы A и B, вместо них вводим в рассмотрение элемент C. Таким образом, число рассматирваемых "текущих элементов" сокращается на один. 6) Если у нас остался только один элемент, то он объявляется корнем дерева, дерево считается построенным; если элементов больше, то Goto "3)" Hапример, если в начале у нас было 5 листьев А, Б, В, Г, Д со значениями 5, 10, 40, 11, 14, соответсвенно, то мы должны получить дерево: А Б Г Д В 5 10 11 14 40 \ / \ / / 15 25 / \ / / 40 / \ / 80 Теперь по дереву можно построить битовые коды наших букв (обходя дерево запоминаем 0, если сворачиваем в узле налево, 1, если сворачиваем направо): А - 000 Б - 001 В - 1 Г - 010 Д - 011 PK> и главное каким образом его хранить в файле (формат хранения). Хранить надо не дерево, а получаемые по нему коды. Ибо по кодам можно востановить дерево. Точнее, по кодам можно востановить структуру дерева (а ведь тебе больше ничего и не надо - для востановления тебе не надо знать частоту вхождений символов, только знать как ветвится дерево). Формает можешь придумать сам. Я храню так: @ первый байт - число битов в самом длинном коде (допустим это число n) @ потом 256 раз записывается длины 256 символов (записываем 256*n бит = 32*n байта) @ наконец, записываются сами коды; так как мы знаем длину (число бит) в каждом, то можно писать их подряд, отводя под каждый столько бит, сколько он занимает. Хотя максимальная глубина дерева huffman'а может быть 255, на практике, длина наидлиннейшего кода (число n) составляет 12-16 бит. Таким образом, на запись длины уходит ~ 450 байт. Средняя длина кодов - 8 бит, так что на запись самих кодов уходит ~ 250 байт. Чуть более оптимальный формат можно получить если сначала запомнить не только длину максимального кода, а разницу между длинами максимальных и минимальных кодов. Hапример, если под коды отводится от 5 до 12 бит (вполне реальная ситуация), то для их хранения можно отвдоить не 4 бита, а 3 (и хранить числа от 0 до 7). Тем самым, выгдавая 32 байта на записи длин 256 кодов. К слову, буду благодарен, если кто-нибудь предложит более оптимальный формат хранения кодов. Andrew --- * Origin: Думать безОбразно -- безобрАзно!!! (2:5030/922.20) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/38693bc8f680.html, оценка из 5, голосов 10
|