2

Подскажите по реализации сжатия статическим методом Хаффмана. Каким образом оптимально хранить в файле дерево Хаффмана?

5
  • Затем нужно считать все сохраненные символы и по ним построить дерево Хаффмана?
    – DarkGenius
    26 дек 2013 в 9:48
  • Что Вы имеете ввиду, когда пишите "оптимально"? Вам нужен наименьший размер файла или скорость обработки этого файла при загрузке и последующего построения дерева?
    – eterey
    26 дек 2013 в 14:47
  • Наименьший размер файла.
    – DarkGenius
    26 дек 2013 в 14:53
  • 1
    Пока мне представляется оптимальным такое решение. Храним в файле информацию о структуре дерева. Для узла записываем левое поддерево, правое поддерево и бит "0", для листа записываем сам символ и бит "1". Начинаем сохранение, очевидно, с записи корня. Такая сериализация дерева позволит восстановить его однозначно.
    – DarkGenius
    26 дек 2013 в 14:57
  • Делать проход по дереву нужно. Налево идем - ноль ставим, направо - единицу. Так каждый символ код получит свой. Связав же символы да их коды построить Хоффмана таблицу уж не проблема. Хранить оную нужно вместе со строкой закодированной. Когда декодировку делать нужно будет, то обратно дерево построить выйдет только сворачивая в соответствующую для бита сторону.
    – eterey
    26 дек 2013 в 15:10

3 ответа 3

5

Не обязательно сохранять дерево. Можно просто хранить счетчики для каждого символа в начале файла, а дерево восстанавливать перед декодингом. 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 = [Node(WEIGHT[c], c) for c in ALPHABET].sort(reverse=True)
while nodes.size() != 1:
  l, r = nodes[0:2]
  nodes = nodes[2:]
  new_node = create_node_with_children(l, r)
  insert_index = 0
  if nodes.size() > 1: # на 2-x последних шагах уже не важен порядок
    while insert_index < nodes.size() and nodes[insert_index].weight > new_node.weight:
      insert_index += 1
  nodes[insert_index:insert_index] = [new_node]

Если внимательно посмотреть на код, то можно понять, что для восстановления топологии дерева нам достатоточно знать начальную расстановку символов в nodes и insert_index на каждом из шагов. Посчитаем сколько на это надо памяти.

Для хранения изначальной перестановки понадобится 255 байт (первый/последний символ можно не хранить, а получить методом исключения).

Далее замечаем, что число итераций в алгоритме фиксировано (255) и на i-ой итерации (считая с нуля) insert_index лежит в диапазоне [0, 255 - i), поэтому мы можем на поздних итерациях выделять меньше бит на хранения insert_index. А конкретно:

  i        | число бит на индекс
[0, 127)   | 8
[127, 191) | 7
[191, 223) | 6
[223, 239) | 5
[239, 247) | 4
[247, 251) | 3
[251, 253) | 2
[254, 256) | 0 // тут не надо ничего сохранять

Т.е. для хранeния индексов вставки нужно 127 * 8 + 64 * 7 + 32 * 6 + 16 * 5 + 8 * 4 + 4 * 3 + 2 * 2 = 1784 бит = 223 байт.

Итого получаем 255 + 223 = 478 байт, причем это число не зависит от размера входных данных, в отличии от способа описанного выше.

9
  • За что минус?
    – dzhioev
    26 дек 2013 в 14:17
  • @dzhioev, за экстремально неэкономное решение (особенно 8 байт) 26 дек 2013 в 14:30
  • Вот прямо-таки экстремально? 4 байта может спокойно не хватить. Вас ведь не смущает, что в x86-64 адреса по 8 байт?
    – dzhioev
    26 дек 2013 в 14:40
  • Очень расточительное хранение) А если исходный файл всего 1КB, то сжатый будет больше 2КB)
    – DarkGenius
    26 дек 2013 в 14:42
  • @Михаил М, @DarkGenius, обновил ответ.
    – dzhioev
    26 дек 2013 в 15:13
1

@DarkGenius, Вы уже написали хороший вариант в комментарии -

Храним в файле информацию о структуре дерева. Для узла записываем левое поддерево, правое поддерево и бит "0", для листа записываем сам символ и бит "1". Начинаем сохранение, очевидно, с записи корня.

Действительно, получается достаточно эффективно, тем более, что у вершины дерева может только либо не быть потомков, либо быть два. 2 бита * (количество символов - 1) + сами символы (скорее всего, по 8 бит).

Но я расспросил коллегу, который делал более хитро. У него получилось примерно 1 бит на символ +, естественно, сами символы. Идея следующая: перестраиваем дерево так, чтобы оно было перекошено строго в одну сторону. Теперь перебираем все листы слева направо и записываем глубину, на которой они находятся. Для

 / \
a  /\
  d  /\
    c  b

получается

a d c b
1 2 3 3

Теперь остаётся записать символы в получившемся порядке, начальную глубину и "растёт-не растёт". Правда, вырасти может и на два и на три... На этот случай надо делать какое-нибудь адаптивное арифметическое кодирование. Но в основном должны быть 0 и 1, которые как раз закодируются одним битиком. Вобщем, по заключению коллеги, битик экономится, но очень трудоёмко в реализации.

Upd: или не арифметическим, а кодировать группы чисел Хаффманом с фиксированным деревом. Или хранить позиции чисел, отличных от 0, 1.

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

   /    \ 
  /\   / \
 /\ c d  /\
a  b    e  f

надо преобразовать путём перестановки поддеревьев в

   /      \ 
  /\    /   \
 с  d  /\   /\
      a  b e  f
4
  • @Михаил М, не очень понял, как "перекашивать" дерево, если оно имеет более сложную структуру, чем в вашем примере. И не очень понятно, что значит "начальную глубину и "растёт-не растёт"" и как по этой информации восстановить дерево. Я тут еще немного подумал, и придумал как сохранить всю информацию в 478 байт вне зависимости от размера входных данных, попозже напишу в свой ответ.
    – dzhioev
    27 дек 2013 в 9:03
  • > 478 байт вне зависимости от размера входных данных, попозже напишу > в свой ответ Обязательно напишите. Будем переделывать все архиваторы.
    – eterey
    27 дек 2013 в 13:12
  • Начальная глубина - глубина самого левого листа. Первое изменение - разница между глубиной второго слева листа и самого левого. Дерево восстанавливается однозначно. Смотрим на начальную глубину - уходим настолько влево. Добавляем лист в соответствии с первым записанным символом. Если дальше "растёт" - на его "брате" уходим настолько вглубь, если нет - добавляем лист на том же уровне. И т.д. 478. Вы, наверное, придумали какой-то фокус с битовой маской на все 256 символов. Наверное, можно на развесистых деревьях так сыграть. Но тем не менее 478 > 2 бит * 255 + 256 байт 27 дек 2013 в 13:12
  • @uzumaxy, написал.
    – dzhioev
    27 дек 2013 в 13:27
1

Я ничего не утверждаю, но кгда делал сам, то просто хранил символы в порядке уменьшения частоты и нечего больше.

Т.к. Хафмен оптимальный префиксный код, то по порядку символа в последовательности можно определить однозначно код.

6
  • Да ладно!... :) Там же два самых низкочастотных символа объединяются и их частота суммируется. Если она превысит частоту изначально 4-го с конца символа, то следующими будут объединены 3-й и 4-й, а если не превысит - новая вершина и 3-й. Т.е. Вы запишете dcba, а будет ли в дереве ba/\dc или d-c-ba - не понятно. Разве нет? 26 дек 2013 в 13:42
  • Действительно, такая неоднозначность возникает. Как же тогда ее обойти?
    – DarkGenius
    26 дек 2013 в 14:41
  • Блин, я вообще комментарий собирался писать, а получилось... Короче как я это дело понимаю: Есть символы есть частоты, пусть так: a-15, b-10, c-3, d-1, e-1 То я всегда могу поменять частоты без изменения порядка: a-5, b-4, c-3, d-2, e-1 Поскольку код оптимальный, то такое перевешивание не должно влиять на сжатие, т.к. код всегда должен быть уникален, количество символов мы не меняли и на частотах отразиться не должно. Поэтому сохраняя: a, b, c, d, e Я фактически храню таблицу с весами. Или я не прав? 26 дек 2013 в 16:28
  • Как раз нельзя менять. Если букв a, b, c, d соответственно 100, 99, 2 и 1 в исходном файле, то это не то же самое, что 100, 3, 2 и 1. Во втором случае, явно выгодней сделать для а однобитовый код 26 дек 2013 в 17:52
  • Да, я понял - неправ. Спасибо что показали. 26 дек 2013 в 18:49

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.