@ Михайло М, що не дуже зрозумів, як "перекошувати" дерево, якщо воно має більш складну структуру, ніж у вашому прикладі. І не дуже зрозуміло, що значить "початкову глибину і" росте-не росте "" і як з цієї інформації відновити дерево. Я тут ще трохи подумав, і придумав як зберегти всю інформацію в 478 байт незалежно від розміру вхідних даних, пізніше напишу в свою відповідь. - dzhioev 27 дек '13 о 9:03
> 478 байт незалежно від розміру вхідних даних, пізніше напишу> в свою відповідь Обов'язково напишіть. Будемо переробляти всі архіватори. - uzumaxy 27 дек '13 о 13:12
Початкова глибина - глибина самого лівого листа. Перша зміна - різниця між глибиною другого зліва листа і самого лівого. Дерево відновлюється однозначно. Дивимося на початкову глибину - йдемо настільки вліво. Додаємо лист відповідно до першого записаним символом. Якщо далі "росте" - на його "брата" йдемо настільки вглиб, якщо немає - додаємо лист на тому ж рівні. І т.д. 478. Ви, напевно, придумали якийсь фокус з бітової маскою на все 256 символів. Напевно, можна на розлогих деревах так зіграти. Але тим не менше 478> 2 біт * 255 + 256 байт - Михайло Ч 27 дек '13 о 13:12
Не обов'язково зберігати дерево. Можна просто зберігати лічильники для кожного символу на початку файлу, а дерево відновлювати перед декодинг. Eсли зберігати лічильники по 8 байт, то буде потрібно 8B * 256 = 2KiB, що зовсім не багато.
UPD. якщо шкода 2KiB, то можна зберігати лічильники більш компактно. Наприклад, ввести наступний формат для лічильника: префікс + лічильник. Префікс являє собою трехбітовое ціле число, рівне розміру лічильника в байтах. приклади:
- Лічильник дорівнює 0. Зберігається в 000 (3 біта).
- Счеткік дорівнює 222. Зберігається в 00111011110 (11 біт).
- Лічильник дорівнює 1024. cохраняющим в +0100000010000000000 (19 біт).
Тобто розмір збережених даних для лічильника n дорівнюватиме ceil (ceil (log_2 (n)) / 8) * 8 + 3 біт.
UPD2. придумав ще один спосіб, який, як мені здається, кращий за попередній. Для початку опишу яку реалізацію алгоритму побудови дерева я збираюся використовувати:
Якщо уважно подивитися на код, то можна зрозуміти, що для відновлення топології дерева нам достатоточно знати початкову розстановку символів в nodes і insert_index на кожному з кроків. Порахуємо скільки на це треба пам'яті.
Для зберігання початкової перестановки знадобиться 255 байт (перший / останній символ можна не зберігати, а отримати методом виключення).
Далі помічаємо, що число ітерацій в алгоритмі фіксоване (255) і на i-ой ітерації (вважаючи з нуля) insert_index лежить в діапазоні [0, 255 - i), тому ми можемо на пізніх ітераціях виділяти менше біт на зберігання insert_index. А конкретно:
Тобто для хранeнія індексів вставки потрібно 127 * 8 + 64 * 7 + 32 * 6 + 16 * 5 + 8 * 4 + 4 * 3 + 2 * 2 = 1784 біт = 223 байт.
Разом отримуємо 255 + 223 = 478 байт, причому це число не залежить від розміру вхідних даних, на відміну від способу описаного вище.