Невозможно сжать файл во время кодирования Хаффмана в Java - PullRequest
Новая
       46

Невозможно сжать файл во время кодирования Хаффмана в Java

0 голосов
/ 18 октября 2011

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

1 Ответ

0 голосов
/ 18 октября 2011

Вы, вероятно, используете StringBuilder и добавляете "0" или "1" или просто оператор + для объединения "0" или "1" в конец вашей строки. Или вы используете какой-то OutputStream и пишете в него.

Что вы хотите сделать, это написать фактические биты. Я бы предложил сделать целый байт, прежде чем писать. Байт выглядит так: 

0x05

Который будет представлять двоичную строку 0000 0011.

Вы можете сделать это, сделав тип byte, добавив и сдвинув: 

public void writeToFile(String binaryString, OutputStream os){
    int pos = 0;
    while(pos < binaryString.length()){
        byte nextByte = 0x00;
        for(int i=0;i<8 && pos+i < binaryString.length(); i++){
            nextByte << 1;
            nextByte += binaryString.charAt(pos+i)=='0'?0x0:0x1;
        }
        os.write(nextByte);
        pos+=8;
    }
}

Конечно, неэффективно писать по одному байту за раз, и вдобавок к этому интерфейс OutputStream принимает только байтовые массивы (byte[]). Так что вам лучше хранить байты в массиве (или даже проще, List), а затем записывать их большими кусками.

Если вам не разрешено использовать байтовые записи (почему, черт возьми, ObjectOutputStream не поддерживает запись байтовых массивов!), Тогда вы можете использовать Base64 для кодирования вашей двоичной строки. Но помните, что Base64 раздувает использование ваших данных на 33%.

Простой способ преобразования байтового массива в base64 - использование существующего кодера. После добавления следующего импорта: 

import sun.misc.BASE64Encoder;

Вы можете создать экземпляр кодировщика и превратить ваш байтовый массив в строку: 

byte[] bytes = getBytesFromHuffmanEncoding();
BASE64Encoder encoder = new BASE64Encoder();
String encodedString = encoder.encode(bytes);
...