Как мне представить двоичные числа в C ++ (используется для кодировщика Хаффмана)?
Я пишу свой Кодировщик Хаффмана, и до сих пор я создал дерево Хаффмана с помощью minHeap, чтобы вытолкнуть два узла с самой низкой частотой и сделать узел, который связывается с ними, а затем оттолкнуть новый узел назад на один (вспенить, промыть, повторить, пока только один узел).
Итак, теперь я создал дерево, но мне нужно использовать это дерево для назначения кодов каждому символу. Моя проблема в том, что я не знаю, как хранить двоичное представление числа в C ++. Я помню, что читал, что беззнаковый символ является стандартом для байта, но я не уверен.
Я знаю, что должен рекурсивно пройти по дереву, и всякий раз, когда я сталкиваюсь с листовым узлом, я должен назначать соответствующий символ, какой бы ни был текущий код, представляющий путь.
Вот что у меня так далеко:
void traverseFullTree(huffmanNode* root, unsigned char curCode, unsigned char &codeBook){
if(root->leftChild == 0 && root->rightChild == 0){ //you are at a leaf node, assign curCode to root's character
codeBook[(int)root->character] = curCode;
}else{ //root has children, recurse into them with the currentCodes updated for right and left branch
traverseFullTree(root->leftChild, **CURRENT CODE SHIFTED WITH A 0**, codeBook );
traverseFullTree(root->rightChild, **CURRENT CODE SHIFTED WITH A 1**, codeBook);
}
return 0;
}
CodeBook — это мой массив, в котором есть места для кодов длиной до 256 символов (для каждого возможного символа в ASCII), но я собираюсь фактически назначить коды значениям, которые появляются в дереве.
Я не уверен, что это правильный путь для обхода моего дерева Хаффмана, но это то, что сразу же работает (хотя я не проверял это). Кроме того, как я могу вызвать функцию обхода корня всего дерева без нулей ИЛИ (самой вершины дерева)?
Должен ли я вместо этого использовать строку и добавлять к ней ноль или 1?
Решение
Поскольку компьютеры являются двоичными … ВСЕ числа в C / C ++ уже в двоичном формате.
int a = 10;
Переменная a это двоичное число
То, что вы хотите посмотреть, это битовые манипуляции, такие операторы, как & | << >>,
В кодировке Хаффмана вы упаковываете данные в массив байтов.
Прошло много времени с тех пор, как я написал C, так что это псевдокод «не в манере» …
Совершенно не проверено — но должно дать вам правильную идею.
char buffer[1000]; // This is the buffer we are writing to -- calc the size out ahead of time or build it dynamically as go with malloc/ remalloc.
void set_bit(bit_position) {
int byte = bit_position / 8;
int bit = bit_position % 8;
// From http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c
byte |= 1 << bit;
}
void clear_bit(bit_position) {
int byte = bit_position / 8;
int bit = bit_position % 8;
// From http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c
bite &= ~(1 << bit);
}// and in your loop, you'd just call these functions to set the bit number.
set_bit(0);
clear_bit(1);
Другие решения
Поскольку curCode имеет только ноль и единицу в качестве значения, BitSet может удовлетворить ваши потребности. Это удобно и экономит память. Ссылка это: http://www.sgi.com/tech/stl/bitset.html
Только небольшое изменение в вашем коде:
void traverseFullTree(huffmanNode* root, unsigned char curCode, BitSet<N> &codeBook){
if(root->leftChild == 0 && root->rightChild == 0){ //you are at a leaf node, assign curCode to root's character
codeBook[(int)root->character] = curCode;
}else{ //root has children, recurse into them with the currentCodes updated for right and left branch
traverseFullTree(root->leftChild, **CURRENT CODE SHIFTED WITH A 0**, codeBook );
traverseFullTree(root->rightChild, **CURRENT CODE SHIFTED WITH A 1**, codeBook);
}
return 0;
}
как хранить двоичное представление числа в C ++
Вы можете просто использовать bitsets
#include <iostream>
#include <bitset>
int main() {
int a = 42;
std::bitset<(sizeof(int) * 8)> bs(a);
std::cout << bs.to_string() << "\n";
std::cout << bs.to_ulong() << "\n";
return (0);
}
как вы можете видеть, они также предоставляют методы для преобразования в другие типы, и удобный [] оператор.
Пожалуйста, не используйте строку.
Вы можете представить кодовую книгу в виде двух массивов целых чисел, один с битовой длиной кодов, другой с самими кодами. С этим связана одна проблема: что если код длиннее целого числа? Решение состоит в том, чтобы просто не допустить этого. Максимально короткая длина кода (скажем, 15) — это хитрость, используемая в большинстве практических применений кодирования Хаффмана по разным причинам.
Я рекомендую использовать канонические коды Хаффмана, и это немного упрощает обход дерева: вам нужны только длины, поэтому вам не нужно отслеживать текущий код. С помощью канонических кодов Хаффмана вы можете легко генерировать коды по длинам.
Если вы используете канонические коды, вы можете позволить кодам быть шире, чем целые числа, потому что старшие биты будут в любом случае равны нулю. Тем не менее, это все еще хорошая идея, чтобы ограничить длину. Имея короткую максимальную длину (хорошо не тоже Короче говоря, это будет ограничивать сжатие, но, скажем, около 16) позволяет использовать самые простые табличное декодирование метод, простая одноуровневая таблица.
Ограничение длины кода до 25 или менее также немного упрощает кодирование, оно позволяет использовать 32-битное целое число в качестве «буфера» и очищать его побайтно, без какой-либо специальной обработки в случае, когда буфер содержит менее 8 бит, но кодирует текущий символ переполнит его (поскольку этот случай полностью исключен — в худшем случае в буфере будет 7 бит, и вы попытаетесь закодировать 25-битный символ, который работает просто отлично).
Как то так (не проверял никак)
uint32_t buffer = 0;
int bufbits = 0;
for (int i = 0; i < symbolCount; i++)
{
int s = symbols[i];
buffer <<= lengths[s]; // make room for the bits
bufbits += lengths[s]; // buffer got longer
buffer |= values[s]; // put in the bits corresponding to the symbol
while (bufbits >= 8) // as long as there is at least a byte in the buffer
{
bufbits -= 8; // forget it's there
writeByte((buffer >> bufbits) & 0xFF); // and save it
}
}