Сжатый сжатый файл Хаффмана больше оригинального

Question

Я реализовал алгоритм кодирования Хаффмана в Java с использованием приоритетных очередей, где я перебираю дерево от корня к листу и получаю пример кодирования в виде # = 000011 на основе количества раз, которое символ появляется на входе. Все хорошо, дерево строится нормально, кодировка такая же, как и ожидалось: но выходной файл, который я получаю, имеет больший размер, чем исходный файл. В настоящее время я добавляю «0» и «1» к строке при обходе левого узла и правого узла дерева. Вот мой метод записи, который записывает с помощью OutputStream:

private void writeToFile(Map<Byte, BitSet> dictCode, byte[] data, OutputStream os) throws IOException {
    for (int i = 0; i < data.length; i++) {
        os.write(dictCode.get(data[i]).toByteArray());
    }
 }

data - это мой файл (файл, который я буду сжимать) в байтах

Map<Byte, BitSet> dictCode BitSet - путь кода дерева Хаффманав байт

Например, битсет для 10 будет 10={3}, потому что верен только третий бит: 000100

Я пишу в байтах, так почему мой новый файл больше, чеморигинал?

Answer 1

Похоже, ваша проблема здесь в том, что вы записываете поток байтов вместо потока битов .

Предполагая, что в вашем коде dictCode map имеет нетривиальную запись для каждого байта в data , тогда:

private void writeToFile(Map<Byte, BitSet> dictCode, byte[] data, OutputStream os) throws IOException {
    for (int i = 0; i < data.length; i++) {
        os.write(dictCode.get(data[i]).toByteArray());
    }
 }

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

Так, например, с потоком токенов

111 010 000 1101 111

вы пишете

00000111 00000010 00000000 00001101 00000111

вместо

11101000 01101111 

Вот почему вы не видите никакого сжатия.