Сжатый файл расшифровки Хаффмана - PullRequest
Новая
       13

Сжатый файл расшифровки Хаффмана

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

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

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

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

В настоящее время я запустил функцию, но я застрял и ищу руководство по написанию текущей функции decodeOutput. Вся помощь приветствуется.
Моя завершенная функция encodedOutput и функция decodeOutput находятся ниже:

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

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

код [256] является параметром для обеих этих функций и содержит код Хаффмана для каждого уникального символа, считываемого в исходном входном файле, например, символ «Н», читаемый во входном файле, может иметь код «111» хранится в массиве кода для кода [72] во время его передачи функциям. 

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");
    }
    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
    char buffer = 0, bit_count = 0;
    while (read != -1) {
        for (unsigned b = 0; b < code[read].size(); b++) { // loop through bits (code[read] outputs huffman code)
            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));

    ifile.close();
    ofile.close();
}

//Work in progress
void decodeOutput(const string & fileName2, const string & fileName3, string code[256]) {
    ifstream ifile;
    ifile.open(fileName2, ios::binary);
    if (!ifile)
    {
        die("Can't read again");
    }
    ofstream ofile;
    ofile.open(fileName3, ios::binary);
    if (!ofile) {
        die("Can't open encoding output file");
    }
    string n = ""; 
    for (int c; (c = ifile.get()) != EOF;) {
        for (unsigned p = 8; p--;) {
            if ((c >> p & 1) == '0') { // if bit is a 0

            }
            else if ((c >> p & 1) == '1') { // if bit is a 1

            }
            else { // Output string n (decoded character) to output file
              ofile << n;
            }
        }
    }
}

1 Ответ

0 голосов
/ 12 марта 2019

Декодирование было бы проще, если бы у вас было оригинальное дерево Хоффмана, использованное для построения кодовой книги.Но предположим, что у вас есть только книга кодов (то есть string code[256]), но нет оригинального дерева Хоффмана.Вы можете сделать следующее:

  • Разделить кодовую книгу на группы кодовых слов различной длины.Скажем, кодовая книга состоит из кодовых слов n различных длин: L 0 1 <... <L <sub>n-1 .
  • Считайте (но пока не используйте) k битов из входного файла, увеличивая k с L 0 до L n-1 , пока не найдете соответствие между входными k битами икодовое слово длины k = L i для некоторого i.
  • Вывести 8-битный символ, соответствующий соответствующему кодовому слову, и использовать k битов из входного файла.
  • Повторяйте до тех пор, пока не будут использованы все биты из входного файла.

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

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

...