Я работаю над алгоритмом сжатия Хаффмана. У меня есть код для каждого символа. Например, f=1100
d=111
e=1101
b=101
c=100
a=0
Теперь, чтобы добиться сжатия, мне нужно записать коды в виде битов в двоичный файл. Прямо сейчас я могу записать их в виде байтов, что ничего не делает, кроме увеличения размера сжатого файла. Как записать коды в виде битов в двоичный файл на Java?
Что ж, если у вас есть текст «fdebcafdbca», вам нужно будет написать это как биты:
110011111011011000110011111011011000
Раздельные и дополненные:
11001111 10110110 00110011 11101101 10000000 //4 bits of padding here
В шестнадцатеричном формате:
CF B6 33 ED 80
Таким образом, вы должны записать массив байтов 0xCF 0xB6 0x33 0xED 0x80 в файл. Это 5 байт = 40 бит, 4 потерянных бита. Текст изначально занимает 12 байт, поэтому экономия невелика, так как вам также нужно хранить дерево. Вы не можете избежать использования заполнения, если они не выровнены по границе байта.
Хотя это вообще не рекомендуется, если у вас есть строка, вы можете сделать это:
public class BitWriter {
private byte nthBit = 0;
private int index = 0;
private byte[] data;
public BitWriter( int nBits ) {
this.data = new byte[(int)Math.ceil(nBits / 8.0)];
}
public void writeBit(boolean bit) {
if( nthBit >= 8) {
nthBit = 0;
index++;
if( index >= data.length) {
throw new IndexOutOfBoundsException();
}
}
byte b = data[index];
int mask = (1 << (7 - nthBit));
if( bit ) {
b = (byte)(b | mask);
}
data[index] = b;
nthBit++;
}
public byte[] toArray() {
byte[] ret = new byte[data.length];
System.arraycopy(data, 0, ret, 0, data.length);
return ret;
}
public static void main( String... args ) {
BitWriter bw = new BitWriter(6);
String strbits = "101010";
for( int i = 0; i < strbits.length(); i++) {
bw.writeBit( strbits.charAt(i) == '1');
}
byte[] b = bw.toArray();
for( byte a : b ) {
System.out.format("%02X", a);
//A8 == 10101000
}
}
}
