Problem

Wczytaj strumień bajtów, stwórz dla niego drzewo prefixowe dla wczytanych oktetów (w terminologii x86 - bajtów) algorytmem kompresji Huffmana. Potem wypisz ile bitów (nie bajtów) plik zajmuje przed i po skompresowaniu tym kodowaniem.

Łącząc dwa poddrzewa, umieszczamy po lewej - to w którym suma wystąpień zawartych znaków jest mniejsza. (W przypadku kiedy sumy są równe, nie ma znaczenia - więc pod tym względem wasze wyjścia mogą się różnić).

Przy budowie drzewa uwzględniamy tylko te oktety (wartości/bajty), które wystąpiły więcej niż zero razy (tylko takie trafiają w ogóle do kolejki).

Specyfikacja wejścia

Dane binarne(!), strumień oktetów (tzw. bajtów), co najmniej jeden oktet na wejściu.

Specyfikacja wyjścia

Wypisane w porządku pre-order węzły drzewa prefixowego utworzonego algorytmem Huffmana, zbudowanego dla wczytanych oktetów (w terminologii x86 - bajtów), zgodnie z następującym kodowaniem:

  • w - dla węzła wewnętrznego

  • _x - dla liścia, gdzie x ma być wartością oktetu zawierająca się w liściu (kodem znaku, w przypadku liter alfabetu angielskiego będą to zapewne kody ASCII). (Wypisaną jako liczba całkowita w systemie dziesiętnym)

Powyższe opisy węzłów będą oddzielone spacją w pierszym wierszu.

  • W drugim wierszu: ilość bitów jaką zajmuje oryginalnie

  • W trzecim wierszu ilość bitów jaką zajmuje po zakodowaniu kodowaniem opisanym drzewem

W trzecim wierszu chodzi tylko o tekst zakodowany drzewem prefixowym bez drzewa kodów prefixowych.

Każdy z trzech wierszy zakończony enterem Unixowym (Linux).

Limity

Ilość oktetów (na x86 - bajtów) na wejściu będzie mniejsza od 230 . Ilość dostępnej pamięci 16MB (i to tak jest z zapasem, generalnie implementujcie tak by mieścić się w max kilku MB, to będziecie mieć bardzo duży zapas… wejścia NIE wczytujemy (całego) do pamięci, tylko przetwarzamy w trakcie wczytywania).

Przykłady

A.in

A

Sama litera "A" bez entera.

A.out

_65
8
1

Tylko jeden oktet - litera "A", więc tylko jeden węzeł w drzewie.

ABBCCC.in

ABBCCC

Tym razem z enterem Linuxowym (dziesiętne "10") na końcu.

ABBCCC.out

w _67 w _66 w _10 _65
56
13

Tutaj widać że mamy następujące kodowania

C _67 0
B _66 10
A _65 111
enter _10 110

Po zakodowaniu ilość bitów

A - 1 * 3b
B - 2 * 2b
C - 3 * 1b
enter - 1 * 3b

Więc mamy 13b.

Ala_ma_kota.in

Ala_ma_kota

Ala_ma_kota.out

w w w _10 _108 _97 w w _111 _95 w w _65 _107 w _109 _116
96
37

Wczytywanie bajt po bajcie

Przykładowe metody wczytywania bajt po bajcie, mogą pomóc w implementacji.

Poniższe programy prezentują jako przykład jak wczytywać dane binarne bajt po bajcie, wypisują wartości numeryczne bajtów. Możecie porównać między sobą wyniki działania.

main.cpp

#include <cstdio>
#include <unistd.h>
int main(){
        unsigned char ch;
        while(fread(&ch, 1, 1, stdin)==1){
                unsigned int integer = ch;
                printf("%u\n", integer);
        }
        return 0;
}

Main.java

class Main {
        public static void main(String[] args) throws java.lang.Exception {
                java.io.BufferedInputStream bufferedInputStream = new java.io.BufferedInputStream(System.in);
                int b;
                while ((b=bufferedInputStream.read())!=-1) {
                        System.out.println(b);
                }
        }
}

W razie uwag do przykładowych kodów, czy porpozycji poprawy/zmian zapraszam do skorzystania fomularza: http://tnij.org/asd2010zad7kom (wymaga zalogowania do google-apps-pjwstk, np. gmail.pjwstk.edu.pl ).