Зачем нам нужен unsigned char для кода дерева Хаффмана

Я пытаюсь создать дерево Хаффмана, вопрос, который я прочитал, для меня очень странный, он выглядит следующим образом:

Учитывая следующую структуру данных:

struct huffman
{
    unsigned char sym;              /* symbol */
    struct huffman *left, *right;   /* left and right subtrees */
};

напишите программу, которая принимает имя двоичного файла в качестве единственного аргумента, строит дерево Хаффмана этого файла, предполагая, что атомы (элементарные символы) являются 8-битными беззнаковыми символами, и печатает дерево, а также словарь. должно выполняться только с помощью malloc(), а сортировка может выполняться с помощью qsort().

Здесь меня смущает то, что для написания программы для создания дерева Хаффмана нам просто нужно сделать следующие вещи:

  1. Нам нужно взять массив частот (это может быть Farray[]={.......})
  2. Отсортируйте его и добавьте два самых маленьких узла, чтобы сформировать дерево, пока не останется 1 последний узел (который является головным).

Теперь возникает вопрос: зачем и где нам нужны эти беззнаковые данные char? (какой тип беззнаковых данных char нужен для этого вопроса, я думаю, что для отображения дерева Хаффмана достаточно только частоты)?


c tree huffman-code
person user3085082    schedule 09.01.2014    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Если вы просто хотите отобразить форму дерева, тогда да, вам просто нужно его построить. Однако для того, чтобы это было хоть как-то полезно, вам нужно знать, какой исходный символ представляет каждый узел.

Представьте, что ваши входные символы — [ABCD]. Воображаемое дерево/словарь Хаффмана может выглядеть так:

         ( )
        /   \              A = 1
      ( )   (A)            B = 00
     /   \                 C = 010
   (B)   ( )               D = 011
        /   \
      (C)   (D)

Если вы не храните sym, это выглядит так:

         ( )
        /   \              A = ?
      ( )   ( )            B = ?
     /   \                 C = ?
   ( )   ( )               D = ?
        /   \
      ( )   ( )

Не очень полезно, да?

Изменить 2: отсутствующий шаг в плане - это шаг 0: построить массив частот из файла (каким-то образом я пропустил, что вам также не нужно кодировать файл). Это не часть фактического самого алгоритма Хаффмана, и я не смог найти достойный пример для ссылки, поэтому вот грубая идея:

FILE *input = fopen("inputfile", "rb");
int freq[256] = {0};
int c;
while ((c = fgetc(input)) != EOF)
    freq[c]++;
fclose(input);

/* do Huffman algorithm  */
...

Теперь это все еще нуждается в улучшении, так как он не использует malloc() и не принимает имя файла в качестве аргумента, но это не моя домашняя работа ;)

person Notlikethat    schedule 09.01.2014
comment
Вы имеете в виду, что если мне просто нужно напечатать дерево, мне просто нужны частоты (например, FArray[]={....}, а затем отсортировать их и добавить минимальное количество узлов) и напечатать это, но если мне нужно закодировать это, чтобы найти степень сжатия, длина каждого частотного элемента и т. д., тогда мне нужен бит без знака char (который этот вопрос просит меня взять в качестве единственного аргумента), я прав? - person user3085082; 10.01.2014
comment
так что вы имеете в виду, что в качестве единственного аргумента должен быть файл с именем file.txt, в котором я должен иметь что-то вроде этого a = 23 b = 45 c = 82 и т. д. Я прав? - person user3085082; 10.01.2014
comment
@user3085082 user3085082 Нет, файл будет содержать aaabccbbabbaccababacab ... Вы должны подсчитать частоту каждого символа как часть чтения ввода. - person Notlikethat; 10.01.2014
comment
Тогда, если у меня есть этот тип ввода в файле, то как я буду подсчитывать частоту символов aaabccbbabbaccababacab...? Частоты должны быть заданы нами для создания дерева Хаффмана. Это немного сбивает с толку. - person user3085082; 10.01.2014
comment
@user3085082 user3085082 Выделите массив целых чисел размером с ваш алфавит (256). Установите их все на ноль. Для каждого символа, который вы читаете из файла, увеличивайте счетчик этого символа на единицу. Когда вы прочтете последний символ из файла, это ваш массив частот. - person Notlikethat; 10.01.2014
comment
На самом деле я прочитал по этой ссылке programminglogic.com/implementing-huffman-coding-in -c и после этого я в замешательстве, вот они берут входной файл с именем Input.txt в котором у них есть a=00011 b= 000101 c=00011 и т.д. и у них декалированные частоты в коде вот такие int englishLetterFrequencies [27] = {81, 15..} , это создает путаницу в моем сознании. И вы говорите о чем-то aabbccabc и т. Д. В файле Input.txt. Пожалуйста, помогите мне устранить эту путаницу. - person user3085082; 10.01.2014
comment
@ user3085082 Нет, a=0011 b=011011 вниз по странице — это словарь для этого дерева, то есть symbol = Huffman code. Input.txt для этого дерева — это тысячи англоязычных текстов, которые были проанализированы для подсчета частоты появления букв. Поскольку они известны, они могут использовать сохраненную версию. В вашем случае данные не являются английским текстом, поэтому вы не знаете частоты заранее, поэтому вам нужно их посчитать самостоятельно - затем вам нужно прочитать файл во второй раз, чтобы фактически закодировать его. . - person Notlikethat; 10.01.2014
comment
@Notlikethis, так что в качестве заключения вы говорите мне, что внутри InputFile.txt у меня должно быть что-то вроде этого abcde, и в моем коде я должен взять ArrayFreq[5]={0}; а затем прочитайте символы, используя переменную count (count++ для каждого следующего алфавита и для каждого встречающегося алфавита будет иметь частоту, равную соответствующему значению этой полученной переменной count). Например, для abcde соответствующая частота будет 1,2,3 ,4,5 (потому что счетчик начинается с =1 и отсчитывает++ для следующего символа до последнего символа). Я прав ? Большое спасибо за руку помощи - person user3085082; 10.01.2014
comment
@Notlikethis Или вы хотите сказать, что мы должны учитывать, сколько раз каждый символ повторяется в последовательности символов aaabccbbbabb, чтобы число повторений символа было его частотой, здесь, например, частота a равна 4. Или предыдущая комментарий правильный ?? (где мы просто делаем count++ до конца, а значение count - это частота для этого алфавита), какой из них вы хотели сказать, правильный? - person user3085082; 10.01.2014
comment
Правильно, вы считаете, сколько раз появляется каждый символ. Я добавил пример, потому что я не могу объяснить это лучше. - person Notlikethat; 10.01.2014
comment
Я говорю, что это лучшее решение, спасибо за эту большую помощь. Вопрос был запутанным, но вы хорошо объяснили, теперь все в порядке. - person user3085082; 10.01.2014

arrow_upward
0
arrow_downward

Это было давно, но я думаю, что сгенерированный «словарь» необходим для кодирования данных, а «дерево» используется для их декодирования. Конечно, всегда можно построить одно из другого.

Во время декодирования вы перемещаетесь по дереву (влево/вправо, в соответствии с последовательными входными битами), и когда вы попадаете в конечный узел (нулевой указатель), тогда «sym» в узле является выходным значением.

person Roddy    schedule 09.01.2014
comment
Предположим, если мне не нужно печатать словарь, то нужен ли мне этот 8-битный беззнаковый символ? что именно означает эта строка вопроса, напишите программу, которая принимает имя двоичного файла в качестве единственного аргумента, строит дерево Хаффмана этого файла, предполагая, что атомы (элементарные символы) являются 8-битными беззнаковыми символами. ЭТО я не могу понять , Это сбивает с толку, пожалуйста, помогите мне объяснить - person user3085082; 10.01.2014
comment
@user3085082 user3085082 беззнаковые символы - это ваши входные данные: это то, что вы считаете частотой от. - person Notlikethat; 10.01.2014
comment
@Notlikethat, так что вы имеете в виду, что в качестве единственного аргумента должен быть файл с именем file.txt, в котором у меня должно быть что-то вроде этого a = 23 b = 45 c = 82 и т. д. Я прав? - person user3085082; 10.01.2014

arrow_upward
0
arrow_downward

Обычно сжатие данных делится на 2 больших шага; задан поток данных:

  • оценить вероятность того, что данный символ появится в потоке, другими словами, вы оцениваете, насколько часто символ появляется в наборе данных
  • после того, как вы изучили случаи и создали свою таблицу с символами, связанными с вероятностью, вам нужно закодировать символы в соответствии с их вероятностью, для достижения этой магии вы создаете словарь, в котором исходный символ часто просто заменяется другим символом, который намного меньше по размеру, особенно для символов, которые часто используются в наборе данных, словарь отслеживает эти замены как на этапе кодирования, так и на этапе декодирования. Хоффман дает вам алгоритм, позволяющий автоматизировать этот процесс и получить достаточно хороший результат.

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

Полное руководство здесь.

person user2485710    schedule 09.01.2014