|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Aksyonoff 2:5036/29.2 20 Oct 2001 10:31:13
To : EinWill
Subject : Оптимальный метод хранения дерева Huffman'а [3/3]
--------------------------------------------------------------------------------
18 Oct 01 16:30, EinWill wrote to All:
E> "А лучше можно?", законно спросите вы. "Да ради бога, кто запрещает!",
E> уклончиво отвечу я =) Я буду рад, если вы пришлете мне свои замечания
E> и предложения.
Хм. Ты подробно расписал только один метод - как можно сильно
ужать само дерево и потом с учетом его информации дожать листы.
Hо. Я - начитавшись умных мыслей из ru.compress - предлагал и
другой. Причем явно более простой, а по эффективности, кажется
сравнимый. А именно: сохранять ТОЛЬКО длины кодов для каждого
символа алфавита (то есть lengths[256]), причем минимальным числом
бит. По моим оценкам получалось ~130 байт на _ВСЕ_. При этом
кодирование/декодирование, по-моему, существенно проще.
Внимание, вопрос - чем описанный тобой вариант лучше? И какие он
дает _фактически_ результаты?
И дальше. У тебя дерево в статье проходит красной нитью - вершины,
обходы, etc, etc, etc. Я надеюсь, очевидно, что работать удобнее и
быстрее с таблицами, а не с деревом?
E> Замечу, что в статье не рассматривался довольно важный случай --
E> кодирование текстовой информации. Ведь тогда довольно большое
E> количество листьев будут лишними -- соответствующие им символы имеют
E> нулевое вхождение.
В этом случае можно опять таки пробовать хранить только длины,
плюс с учетом того, что много нулей, ноль кодировать нулевым
битом, а остальные числа префиксить единичным.
E> Hаконец, последнее (к чему надо стремиться). Как я понял из бесед
E> с практиками, в случае кодирования текста, запись дерева huffman'а
E> занимает порядка 10 байт. В случае общего файла -- порядка 100 байт.
Что же ты размер у них выяснил, а метод хранения - нет? :-)
- Andrew
... This is a noise that keeps me awake, my head explodes and my body aches...
--- ged+-pl1.1.4-win32 &
* Origin: unknown. (2:5036/29.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Оптимальный метод хранения дерева Huffman\'а [3/3] 
