Блог

Я пишу алгоритм кодирования / декодирования Хаффмана и сталкиваюсь с проблемой, заключающейся в том, что хранение дерева Хаффмана занимает слишком много места. В настоящее время я преобразую дерево в хэш-карту как таковую -> HashMap<Символы, код Хаффмана>, а затем сохраняю эту хэш-карту. Проблема в том, что, хотя строка отлично сжимается, добавление данных дерева Хаффмана, хранящихся в хэш-карте, добавляет столько накладных расходов, что фактически получается больше, чем оригинал. В настоящее время я просто наивно записываю пары [данные, значение] в файл, но я полагаю, что должен быть какой-то более сложный способ сделать это. Есть идеи?

Вам не нужно дерево для кодирования. Все, что вам нужно, это длины битов для каждого символа и способ упорядочения символов. Смотрите Канонический код Хаффмана.

На самом деле, все, что вам нужно, это символы, которые кодируются в порядке битовой длины, и в пределах битовой длины сортируются по символу, а затем по количеству кодов каждой длины. Только с этими двумя вещами вы можете кодировать.