Як зберігати дерево Хаффмана?

Сортувати за

DarkGenius. Ви вже написали хороший варіант в —

Зберігаємо в файлі інформацію про структуру дерева. Для вузла записуємо ліве піддерево, праве піддерево і біт "0", Для листа записуємо сам символ і біт "1". Починаємо збереження, очевидно, з записи кореня.

Дійсно, виходить досить ефективно, тим більше, що у вершини дерева може тільки або не бути нащадків, або бути два. 2 біта * (кількість символів — 1) + самі символи (швидше за все, по 8 біт).

Але я розпитав колегу, який робив більш хитро. У нього вийшло приблизно 1 біт на символ +, природно, самі символи. Ідея наступна: розбудовуємо дерево так, щоб воно було перекошене строго в одну сторону. Тепер перебираємо всі листи зліва направо і записуємо глибину, на якій вони знаходяться. Для

виходить

Тепер залишається записати символи в отриманому порядку, початкову глибину і "росте-не росте". Правда, вирости може і на два і на три. На цей випадок треба робити яке адаптивне арифметичне кодування. Але в основному повинні бути 0 і 1, які якраз Закодуйте одним Битик. Вобщем, за висновком колеги, Битик економиться, але дуже трудомістко в реалізації.

Upd. або не арифметична, а кодувати групи чисел Хаффманом з фіксованим деревом. Або зберігати позиції чисел, відмінних від 0, 1.

Під перекошування я мав на увазі щось на зразок сортування. Наприклад,


треба перетворити шляхом перестановки піддерев в

Оригiнал читайте here.

Також читайте

Share →