Twój output to kolejno:
'a' - jeden bajt dosłowny,
0 - jeden bit (0
oznacza, że dodajemy nowy element do słownika i następne 8 bitów reprezentuje kolejny bajt, gdyby była to 1
że wyciągamy ze słownika litrę a
)
'l' - jeden bajt oznaczjący nową literę
1 - jeden bit - tu w słowniku mamy 3 elementy, jeśli pierwszy bitem jest 1 to oznacza to litrę a
(ten przypadek), jeśli byłby to bit 0 to następny bit określałby czy jest to litera l
czy nowy element słownika
00 - dwa bity - słownik bez zmian, pierwszy bit to zero, drugi też zero, czyli dodajemy nową literę do słownika
'o' - jeden bajt z nową literą, od teraz w słowniku mam teraz 3 znaki i oznaczanie dodawania nowych znaków (przebudowa drzewa)
01 - dwa bity, pierwszy bit oznacza, że nie jest to a
, a drugi bit oznacza, że jest to l
. gdyby miało by to być znowu o
to byłby to ciąg bitów: 001
0 - jeden bit oznaczający a
w sumie: 3 bajty i 7 bitów, co mieści się w 4 bajtach
Cały problem w tym algorytmie to aktualizowanie drzewa kodowania w zależności od tego jak zmienia się częstość występowania liter, co powoduje zmianę sposobu kodowania znaków (i zmianę długości w bitach poszczególnych znaków).
Musisz napisać sobie klasę, która będzie przesuwać bity i łączyć wcześniej zapisane bity z nowymi dodawanymi.
Coś w tym stylu:
class MyOutputBitStream {
QIODevice *dev;
unsigned int bitOffset, data;
public:
MyOutputBitStream(QIODevice *dev) : dev(dev), bitOffset(0), data(0) {}
bool writeBits(unsigned char x, int numberOfBits) {
Q_ASSERT(numberOfBits<=8 && numberOfBits>0);
bool result = true;
x &= (1<<numberOfBits)-1; // clear additional bits
data |= ((unsigned int)x)<<bitOffset; // merge with previous data
bitOffset += numberOfBits;
if (bitOffset>=8) {
char toWrite = data&&0xff; // endians
result = 1==dev->write(&toWrite, 1);
data >>=8;
bitOffset-=8;
}
return result;
}
int flush() { // returns number of bits flushed or -1 on error
int result = -1;
if (bitOffset) {
char toWrite = data&0xff; // endians
if (1==dev->write(&toWrite, 1)) {
result = bitOffset;
bitOffset = 0;
data = 0;
}
}
return result;
}
};