Как записать файл в Java после кодировки Хаффмана

Question

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

Например, пусть строка «aravind_is_a_good_boy» будет единственной строкой в ​​файле. Когда вы строите дерево huffman и генерируете код huffman для каждого символа, мы можем видеть, что для символа «a» код huffman равен «101», а для символа «r» код huffman равен «0101» и т. Д. .

Мое намерение состоит в том, чтобы сжать файл. Поэтому я не могу написать строку, которая создается путем замены каждого символа его кодом huffman непосредственно в файл. Поскольку каждый символ заменяется не менее чем на 3 символа (каждый '1' и '0' все равно записываются в файл как символ, а не биты). Поэтому я решил записать его в файл как байты, так как вы не можете записать биты в файл. Но тогда «a» и «r» записываются как «5» в файл. Это может вызвать проблемы при распаковке файла.

Это, как я уверен, преобразование последовательности бит в байты:

public byte[] compressString(String s, CharCodeHashMap map) { 
     String byteString = ""; 
     byte[] byteArr = new byte[s.length()]; 
     int size = 0; 
     for (int i = 0; i < s.length(); i++) { 
      byteString += addPaddingZeros(map.getCompressedChar(s.charAt(i))); 
      byteArr[size++] = new BigInteger(byteString, 2).toByteArray()[0]; 
      byteString = ""; 
     } 

     return byteArr; 
    } 

Я попытался префиксов «1» для каждого из hashcodes, чтобы решить эту проблему. Но тогда, когда вы строите дерево хаффмана, читая файл, некоторые символы имеют более 8 бит. Тогда проблема new BigInteger(byteString, 2).toByteArray() будет иметь более чем на 1 элемент в массиве. (Для например, если «v» имеет «11010001 хэш-код» и new BigInteger(byteString, 2).toByteArray() возвращает массив элементов [0, -47].)

Can кто-то, пожалуйста, предложите мне способ записи в файл таким образом, чтобы файл был сжат и в то же время эти проблемы также позаботились.

Answer 1

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

Так что вам нужен способ кодирования факта, что ваш файл представляет собой число бит, которое может не быть, кратным 8. Это означает, что размер битового потока не обязательно является размером файла (в байтах) умножается на 8.

Есть целый ряд решений:

• Резерв N байтов в начале файла для размера файла в битах. Например, резервирование 4 байта позволяет вам представить размеры файлов до 2 бит.
• Зарезервируйте 3 бита в начале файла, чтобы сохранить количество бит по модулю 8. Вы можете использовать это, чтобы определить, сколько бит в последнем байте файла игнорируется.
• Используйте какое-то кодирование для представления конца потока; например представляют его как символ в текстовом потоке, который вы кодируете.

Есть ли способ справиться с этим без с использованием некоторых бит? AFAIK, №

---

^{1 - А на более низком уровне, файлы представлены в виде последовательностей дисковых блоков, состоящих из нескольких байт. Таким образом, с точки зрения физического хранения сжатие файлов, которые уже являются небольшими (например, меньше, чем блок диска), ничего не достигает.Аналогично, сохранение или не сохранение (скажем) 3 битов, когда представление моделируется как последовательность байтов, находится на границе без смысла ... если это было то, что касалось вас.}

Answer 2

Да, вы можете записать бит в файл. На самом деле вы всегда записываете бит в файл. Единственное, что вы пишете восемь бит за раз.

Что вам нужно, это бит-буфер, скажем, 32-разрядная неподписанная переменная, в которую вы накапливаете биты. Иметь другое целое число, которое отслеживает количество бит в буфере бит. Используйте операторы сдвига влево и/или (или плюс), чтобы поместить больше бит в буфер бит, а также операторы and и shift right, чтобы удалить их. Всякий раз, когда у вас есть восемь или более бит в буфере бит, вы записываете эти восемь бит в файл в виде байта. В конце напишите оставшиеся биты (если есть) в файл в качестве последнего байта.

Таким образом, чтобы добавить биты биты значения в буфер:

bitBuffer |= value << bitCount; 
bitcount += bits; 

писать и удалять имеющиеся байты:

while (bitCount >= 8) { 
    writeByte(bitBuffer & 0xff); 
    bitBuffer >>>= 8; 
    bitCount -= 8; 
} 

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

Другая проблема заключается в том, что вам также необходимо передать код Хаффмана самому декодеру перед кодированными символами, чтобы декодер знал, как декодировать. Посмотрите на «канонические коды Хаффмана» для того, как эффективно это делать.