Запись двоичного значения в файл для кодирования Хаффмана

Я пытаюсь реализовать сжатие файлов с использованием кодировки Хаффмана. В настоящее время я пишу заголовок как первую строку сжатого файла, а затем пишу закодированные двоичные строки (т.е. строки, имеющие двоичное закодированное значение).

Однако вместо уменьшения размера файла размер моего файла увеличивается, так как для каждого символа, такого как «a», я пишу соответствующий двоичный файл, например 01010001, который занимает больше места.

Как я могу записать его в файл таким образом, чтобы он уменьшил пространство?

это мой код

public void write( String aWord ) {

        counter++;
        String content;
        byte[] contentInBytes;

        //Write header before writing file contents
        if ( counter == 1 )
        {
            //content gets the header in String format from the tree
            content = myTree.myHeader;
            contentInBytes = content.getBytes();

            try {
                fileOutputStream.write(contentInBytes);
                fileOutputStream.write(System.getProperty("line.separator").getBytes());
            } catch (IOException e) {
                System.err.println(e);
            }
        }

        //content gets the encoded binary in String format from the tree
        content = myTree.writeMe(aWord);
        contentInBytes = content.getBytes();


            try {
                fileOutputStream.write(contentInBytes);
                fileOutputStream.write(System.getProperty("line.separator").getBytes());
            } catch (IOException e) {
                System.err.println(e);
            }
        }

Пример входного файла:

abc
aef
aeg

Сжатый файл:

{'g':"010",'f':"011",'c':"000",'b':"001",'e':"10",'a':"11"}
11001000
1110011
1110010

java file compression huffman-code
person JGPhilip    schedule 12.10.2015    source источник
comment
Есть ли какой-нибудь код вызова для этого? Как вы заполняете myTree?   -  person J E Carter II    schedule 12.10.2015
comment
Да, есть связанный список, в котором есть символы и их значения, и содержимое получает правильное двоичное значение для этой конкретной строки. Моя единственная проблема - это место здесь, поэтому мне нужно записать в файл таким образом, чтобы он занимал меньше места, чем то, что он делает сейчас, поскольку мой текущий сжатый файл в конечном итоге в 4-5 раз превышает размер оригинала.   -  person JGPhilip    schedule 12.10.2015
comment
Таким образом, вы можете проверить или зарегистрировать, чтобы убедиться, что myTree имеет уникальных членов... например. а не повторяется.   -  person J E Carter II    schedule 12.10.2015
comment
Да, в дереве нет экземпляров дубликатов. Мне просто нужно, чтобы письмо было сделано эффективно.   -  person JGPhilip    schedule 12.10.2015
comment
Когда-то решением было бы использовать набор символов ASCII 0-255, группирующий биты в байт (8).. поскольку теперь, когда вы пишете 0, вы фактически пишете байт 48.   -  person Petter Friberg    schedule 12.10.2015
comment
Как я могу это сделать @PetterFriberg?   -  person JGPhilip    schedule 12.10.2015
comment
Что-то вроде этого stackoverflow.com/questions/18975764/   -  person Petter Friberg    schedule 12.10.2015
comment
Как упражнение результат выглядит хорошо для меня. Вы не можете ожидать уменьшения размера, потому что вы пишете текст (если вы выводите двоичный файл, вывод не будет удобочитаемым для человека без дополнительных инструментов). Кроме того, поскольку ваш ввод очень мал, заголовок (таблица символов) уже будет больше исходного ввода, даже если вы выводите двоичные данные. Сама кодировка Хаффмана выглядит нормально, чего вы пытаетесь достичь?   -  person Durandal    schedule 12.10.2015
comment
Как я могу писать в двоичном формате? Мне не нужно, чтобы мой сжатый файл был в удобочитаемом формате @Durandal. А для больших файлов размер значительно увеличивается, например, для файла размером 11 МБ я получаю сжатый файл размером около 55 МБ.   -  person JGPhilip    schedule 12.10.2015
comment
Вы не можете записывать отдельные биты в файл, вам нужно что-то вроде ответа, улучшите логику для группировки и все в порядке, например, 1 байт говорит, сколько цифр используется, а второй - цифры. Обратите внимание также на этот простой способ, которым вы уменьшите файл размер до 1/4   -  person Petter Friberg    schedule 12.10.2015

Ответы (1)


arrow_upward
6
arrow_downward

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

Чтобы достичь сжатия, вам нужно будет вывести символы Хаффмана в виде двоичных данных, где вы в настоящее время выводите строку «11» для «a», вам нужно будет просто вывести два бита 11.

Я предполагаю, что в настоящее время это закодировано в myTree.writeMe(), вам нужно изменить метод, чтобы не возвращал строку, а что-то более подходящее для двоичного вывода, например. байт[].

Это немного зависит от внутренней работы вашего древовидного класса, как это сделать. Я предполагаю, что вы используете какой-то StringBuilder внутри и просто добавляете закодированные строки символов, зацикливая ввод. Вместо StringBuilder вам понадобится контейнер, способный работать с отдельными битами. Единственный подходящий класс, который сразу приходит на ум, это java.util.BitSet (на практике для этого часто пишут специализированный класс со специализированным API, чтобы сделать это быстро). Но для простоты давайте пока воспользуемся BitSet.

В методе writeMe вы в принципе будете делать следующее:

 BitSet buffer = new BitSet();
 int bitIndex = 0;
 loop over input symbols {
     huff_code = getCodeForSymbol(symbol)
     foreach bit in huff_code {
         buffer.put(bitIndex++, bit)
     }
 }
 return buffer.toByteArray();

Как это сделать эффективно, зависит от того, как вы внутренне определили кодовую таблицу Хаффмана. Но принцип прост, перебрать код, определить, является ли каждое место единицей или нулем, и поместить их в BitSet с последовательными индексами.

if (digits == '1') {
    buffer.set(bitIndex);
} else {
    buffer.clear(bitIndex);
}

Теперь у вас есть данные, закодированные методом Хаффмана. Но результирующие данные будет невозможно правильно распаковать, так как вы сейчас обрабатываете слова и не указываете, где на самом деле заканчиваются сжатые данные (в настоящее время вы делаете это с перевод строки). Если вы закодировали, например, 3 раза 'a', BitSet будет содержать 11 11 11. Это 6 бит, но когда вы конвертируете в byte[], он дополняется до 8 бит: 0b11_11_11_00.

Эти дополнительные, неизбежные биты запутают вашу декомпрессию. Вам нужно будет каким-то образом справиться с этим, либо сначала закодировав количество символов в данных, либо используя явный символ, сигнализирующий о конце данных.

Это должно дать вам идею, что делать дальше. Многие детали зависят от того, как вы реализуете свой древовидный класс и закодированные символы.

person Durandal    schedule 12.10.2015