Реализация дерева Хаффмана - PullRequest
Новая
       8

Реализация дерева Хаффмана

2 голосов
/ 07 марта 2019

У меня есть программа, которая создает дерево Хаффмана на основе частоты символов ascii, считываемой в текстовом файле ввода.Коды Хаффмана хранятся в строковом массиве из 256 элементов, пустая строка, если символ не читается.

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

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

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

Моя текущая функция (fileName - параметр входного файла, fileName2 - параметр выходного файла): 

void encodeOutput(const string & fileName, const string & fileName2, string code[256]) {
    ifstream ifile;//to read file
    ifile.open(fileName, ios::binary);
    if (!ifile)//to check if file is open or not
    {
        die("Can't read again"); // function that exits program if can't open
    }
    ofstream ofile; 
    ofile.open(fileName2, ios::binary); 
    if (!ofile) {
        die("Can't open encoding output file"); 
    }
    int read;
    read = ifile.get();//read one char from file and store it in int
    while (read != -1) {//run this loop until reached to end of file(-1)
        ofile << code[read]; //put huffman code of character into output file
        read = ifile.get();//read next character
    }
    ifile.close();
    ofile.close();
}

1 Ответ

1 голос
/ 07 марта 2019

Вы не можете просто использовать ofile << code[read];, если вам нужно написать биты , наименьшая единица, которую ofstream понимает, является байтом.

Чтобы преодолеть это, вы можете записать свои биты в своего рода «битовый буфер» (подойдет char) и записать , что , как только у него будет 8 бит. Я не знаю точно, как выглядят строки кода, но это должно сделать: 

char buffer = 0, bit_count = 0;
while (read != -1) {
  for (int b = 0; b < code[read].size(); b++) {
    buffer << 1;
    buffer |= code[read][b] != 0;
    bit_count++;
    if (bit_count == 8) {
      ofile << buffer;
      buffer = 0;
      bit_count = 0;
    }
  }
  read = ifile.get();
}

if (bit_count != 0)
  ofile << (buffer << (8 - bit_count));
...