Таблица частот байтов для кодирования Хаффмана - PullRequest
1 голос
/ 18 августа 2010

Я пишу компрессор Хаффмана и декомпрессор (на С ++), который должен работать с произвольными двоичными файлами. Мне нужно немного советов по структуре данных. Прямо сейчас мой процесс сжатия выглядит следующим образом:

  • Считать байты файла в двоичном виде в буфер char
  • Используйте std :: map для подсчета частот каждого байтового шаблона в файле. (Здесь я думаю, что напрашиваюсь на неприятности.)
  • Построить двоичное дерево на основе частотной гистограммы. У каждого внутреннего узла есть сумма частот его дочерних узлов, и у каждого конечного узла есть символ * для представления действительного байта.

Вот где я сейчас нахожусь.

Мой вопрос в том, что именно я измеряю, если я просто использую карту от char * до int. Если я прав, это на самом деле не то, что мне нужно. То, что я действительно делаю, это отслеживание фактических 4-байтовых значений указателя с помощью char *.

Итак, я планирую использовать карту для гистограммы и символ для данных, хранящихся в конечных узлах. Моя логика здесь звучит? Мои рассуждения говорят мне «да», но поскольку я впервые имею дело с двоичными данными, я бы хотел быть осторожным с ловушками, которые проявляются только странным образом.

Спасибо.

1 Ответ

3 голосов
/ 18 августа 2010

Вам не нужна карта;Есть только 256 возможных значений.Просто наберите int freq[256] = {0} и добавьте к нему freq[data[idx]]++ для каждого байта на входе.

Если вы действительно хотите карту, используйте map<unsigned char, int>;ваше подозрение на использование карты от char* верно.

...