man compress:
DESCRIPTION de már jópár éve lejárt a szabadalmi oltalom, egyik eredmény: a gif visszaszorult, a png elterjedt. (A Lempel-Ziv-Welch algoritmust használja a gif formátuma, sok tömörítő, például a compress, gzip, zip.)
The compress utility shall attempt to reduce the size of the named files by using adaptive Lempel-Ziv coding algorithm.
Note: Lempel-Ziv is US Patent 4464650, issued to William Eastman, Abraham Lempel, Jacob Ziv, Martin Cohn on August 7th, 1984, and assigned to Sperry Corporation.
Lempel-Ziv-Welch compression is covered by US Patent 4558302, issued to Terry A. Welch on December 10th, 1985, and assigned to Sperry Corporation."
Az algoritmus remek leírását találjuk a Rónyai-Iványos-Szabó Algoritmusok könyvben. Alább egy naivabb implementációt adunk a Tusnády: Sztochasztikus számítástechnika című könyv alapján: jön a 0-1 sorozat, betűnként olvassuk, ha olyan rész jön, ami még "nincs a zsákban", akkor "letörjük és be a zsákba":
00011101110 -> 0 00 1 11 01 110
a tördelést egy bináris fával könnyen meg tudjuk valósítani:
/
0 1
0 1 1
0
Így használd:
[norbi@sgu C]$ more b.txt
00011101110
[norbi@sgu C]$ gcc z.c -o z -std=c99
[norbi@sgu C]$ ./z < b.txt
00011101110
---------1
------------0
------1
---/
---------1
------0
---------0
A kód, a harmadik labor billenytűzős feladata lesz, de immár nem csak képpel:
#include <stdio.h> #include <stdlib.h> #include <unistd.h> typedef struct binfa { int ertek; struct binfa *bal_nulla; struct binfa *jobb_egy; } BINFA, *BINFA_PTR; BINFA_PTR uj_elem () { BINFA_PTR p; if ((p = (BINFA_PTR) malloc (sizeof (BINFA))) == NULL) { perror ("memoria"); exit (EXIT_FAILURE); } return p; } extern void kiir (BINFA_PTR elem); extern void szabadit (BINFA_PTR elem); int main (int argc, char **argv) { char b; BINFA_PTR gyoker = uj_elem (); gyoker->ertek = '/'; BINFA_PTR fa = gyoker; while (read (0, (void *) &b, 1)) { write (1, &b, 1); if (b == '0') { if (fa->bal_nulla == NULL) { fa->bal_nulla = uj_elem (); fa->bal_nulla->ertek = 0; fa->bal_nulla->bal_nulla = fa->bal_nulla->jobb_egy = NULL; fa = gyoker; } else { fa = fa->bal_nulla; } } else { if (fa->jobb_egy == NULL) { fa->jobb_egy = uj_elem (); fa->jobb_egy->ertek = 1; fa->jobb_egy->bal_nulla = fa->jobb_egy->jobb_egy = NULL; fa = gyoker; } else { fa = fa->jobb_egy; } } } printf ("\n"); kiir (gyoker); extern int max_melyseg; printf ("melyseg=%d", max_melyseg); szabadit (gyoker); } static int melyseg = 0; int max_melyseg = 0; void kiir (BINFA_PTR elem) { if (elem != NULL) { ++melyseg; if (melyseg > max_melyseg) max_melyseg = melyseg; kiir (elem->jobb_egy); for (int i = 0; i < melyseg; ++i) printf ("---"); printf ("%c(%d)\n", elem->ertek < 2 ? '0' + elem->ertek : elem->ertek, melyseg); kiir (elem->bal_nulla); --melyseg; } } void szabadit (BINFA_PTR elem) { if (elem != NULL) { szabadit (elem->jobb_egy); szabadit (elem->bal_nulla); free (elem); } }
3 kisbajnokság
Annak, aki először megmondja, hogy a esr.fsf.hu/hacker-howto.html lap bitenként nézve milyen mély ilyen "Ziv-Lempel" fát épít fel. Tipp: írj egy dump progit, ami 0-1 karakterekben kiköpi a bináris bemenetét és tedd ezt:
[norbi@sgu C]$ wget http://esr.fsf.hu/hacker-howto.htmlezt már megeszi a fenti kód, csak ki kell íratnod a mélységet. (Ne feledd: a laborteljesítés feladata olyasmi lesz, hogy binárisan kell majd feldolgoznod a bemenetet, pontos specifikáció majd később.)
[norbi@sgu C]$ cat hacker-howto.html|./d >hacker-howto.html.01
[norbi@sgu C]$ more hacker-howto.html.01
A program a 4. laboron kerül terítékre, de már a harmadikon szerepel majd az említett dump:
Előrehivatkozok itt most a Labormérés otthon, avagy hogyan dolgozok fel egy pédát c. posztra, aminek Móricka rajza segít a "mélység" értelmezésében.
A laborok teljesítésének egyik szükséges feltétele
Idézet az 1. előadásból:
Labor teljesítésének további szükséges feltétele egy saját program
bemutatása a laborközösség előtt, a félév közepén. A feladat kötött:
adok egy karakterekre (0,1 betűkre) működő algoritmust, azt kell
átírni, hogy bináris bemenetre (0, 1 bitekre) működjön (lásd 3 előadás
és labor). A félév végén pedig egy saját robofocis fejlesztés
bemutatása..
S ugye annyit nehezítettünk, hogy idén már a C++ változatot kell védeni (de éppen e miatt ettől még elválaszt minket pár előadás). A karakterekre működő LZW fa építő most szerepelt, de binárisra úgy engedtük rá, hogy azt először az iménti dump progival karakteres 0,1 állománnyá alakítottuk. Most olyat kell írnod, ami kapásból binárisat dolgoz fel! Íme a specifikáció:
Állomány: BNbeadando.c (saját monogram, ékezetes betű nincs)
Parancssor: ./BNbeadando input_fájl_neve -o kimeneti_fájl_neve (ha nem így indítják, kiírja, hogy így kellene használni és leáll)
Kimenet: tartalmazza a 0,1 bináris LZW fát, majd a fa mélységét, végül a fa ághosszainak szórását (utóbbi a negyedik laboron is téma)
(Lesz néhány teszt állomány megadva, ahol előre meg lehet nézni, hogy megfelelően működik-e a kifejlesztett progitok. Aki előre dolgozna: z.c, illetve a humán genom 2. kromoszómája mindig kéznél van: hs_...chr2.fa.gz a posztban használt fájlnév változott, dolgozz majd ezzel: ftp://ftp.ncbi.nlm.nih.gov/genomes/H_sapiens/CHR_02/hs_alt_HuRef_chr2.fa.gz aki kiszámolja itt elsőként az LZW fa mélységét, annak 3 trófea, ha a d.c-t módosítja, hogy az az első "sort" kidobja, további 1, s az így kapott mélységre további 1.)
