Zadanie
Napisać trywialny program kompresujący trywialny plik tekstowy.
Jak to ma działać?
Załóżmy, że dopuszczamy możliwość użycia w skompresowanym tekście:
- dużych liter od A do Z,
- spacji,
- znaku nowej linii ('\n').
Teraz każdemu znakowi przyporządkujmy liczbę dwójkową według poniższej tabeli
Znak | Kod |
A | 00000 |
B | 00001 |
C | 00010 |
D | 00011 |
E | 00100 |
F | 00101 |
G | 00110 |
H | 00111 |
I | 01000 |
J | 01001 |
K | 01010 |
L | 01011 |
M | 01100 |
N | 01101 |
O | 01110 |
P | 01111 |
Q | 10000 |
R | 10001 |
S | 10010 |
T | 10011 |
U | 10100 |
V | 10101 |
W | 10110 |
X | 10111 |
Y | 11000 |
Z | 11001 |
spacja | 11010 |
'\n' | 11011 |
rezerwa | 11100 |
rezerwa | 11101 |
rezerwa | 11110 |
koniec napisu | 11111 |
Tak więc napis
ALA MA KOTA
powinien być reprezentowany przez następujący ciąg bitów
0000001011000001101001100000001101001010011101001100000
Długość tego ciągu to 55 bitów czyli 6 bajtów i 7 bitów. Dodatkowo przyjmujemy założenie, że napis musi kończyć sie sekwencją: 11111 a ostatni bajt musi zostać dopełniony zerami.
bajt 1: 00000010
bajt 2: 11000001
bajt 3: 10100110
bajt 4: 00000011
bajt 5: 01001010
bajt 6: 01110100
bajt 7: 1100000
po uwzględnieniu faktu, że napis musi kończyć sie sekwencją: 11111 i dopełnieniu zerami otrzymujemy:
bajt 7: 11000001
bajt 8: 11110000
Aby poradzić sobie z tym zadaniem przydatne mogą być informacje o
- przesunięciu bitowym
- operacje bitowe
Tak więc tekst o pierwotnej długości 11 bajtów teraz będzie miał długość 8 bajtów.
Moje rozwiązanie (kompresja)
Moje rozwiązanie (dekompresja)
Plik testowy 1
Skompresowany plik testowy, zapisany szesnastkowo, powinien wyglądać jak poniżej
02 C1 A6 03
4A 74 C1 B9
64 11 21 9D
A4 68 34 89
0C ED 83 4D
05 89 3D 30
1A 1D 81 A5
3A 78 DF 00