Главная страница


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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 Huffman   Petr Koroli   13 Oct 2001 19:32:10 
 Huffman   Michael Bolotnicov   14 Oct 2001 01:47:00 
 Huffman   Andrew Plyako   14 Oct 2001 01:44:12 
 Huffman   Andrew Aksyonoff   14 Oct 2001 04:40:59 
 Huffman   Serge Voskoboynikov   15 Oct 2001 14:00:55 
 Re: Huffman   EinWill   16 Oct 2001 14:24:43 
 Huffman   Andrew Aksyonoff   17 Oct 2001 20:27:38 
 Re: Huffman   Dmitriy Guzenko   17 Oct 2001 02:32:22 
 Re: Huffman   EinWill   17 Oct 2001 10:39:47 
 Huffman   Andrew Aksyonoff   17 Oct 2001 20:41:09 
 Re: Huffman   EinWill   17 Oct 2001 14:26:19 
 Huffman   Alex Astafiev   18 Oct 2001 00:26:56 
 Re: Huffman   EinWill   18 Oct 2001 16:38:40 
 Huffman   Alex Astafiev   18 Oct 2001 23:53:09 
 Huffman   Andrew Aksyonoff   17 Oct 2001 20:43:35 
 Huffman   Andrew Aksyonoff   17 Oct 2001 20:37:27 
 Huffman   Jaroslaw Skobelew   14 Oct 2001 20:10:29 
 Huffman   Artyom Vasilenko   15 Oct 2001 16:36:00 
Архивное /ru.algorithms/38693bc8f680.html, оценка 2 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional