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

Question

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

Однако, вместо уменьшения размера файла, размер моего файла увеличивается, как для каждого символа типа '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 

Answer 1

Как я понял из комментариев, вы пишете текст, но то, что вы действительно хотите достигнуть написания двоичных данных. То, что у вас сейчас есть, - это хорошая демо для кодирования huffman, но непрактичная для фактического сжатия данных.

Для достижения сжатия, вам нужно вывести Хаффмана символы как двоичные данные, где вы в данный момент вывести строку «11» для «а», вам нужно будет только выходные два бита 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(); 

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

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

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

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

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