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 ).