 |
|
 |  |
|
|
| |
 | Biologie | Chimie | Didactica | Fizica | Geografie | Informatica |
| Istorie | Literatura | Matematica | Psihologie |
Academia de Studii Economice
Catedra de Informatica Economica
PROIECT
LIMBAJE DE ASAMBLARE
Compresia fisierelor utilizand algoritmul Limpel - Ziv
1. Introducere
Obiectivul acestei lucrari este conceperea unui produs software care realizeaza compresia unui fisier folosind algoritmul Limpel-Ziv .
Proiectul isi gaseste aplicabilitate in lucrul compresia de date.
Nu de putine ori se doreste economisirea de spatiu pe disc, iar in acest caz se apeleaza la diversi algoritmi de compresie. Printre acestia se numara si algoritmul Limpel-Ziv. Unele dintre cele mai recente compresoare sunt bazate pe algoritmii LZ77 si LZ78, facand referire la documentatia publicata de Ziv si Limpel in 1977, repspectiv 1978. Acesti algoritmi formeaza baza aproape a tuturor tehnicilor de comprimare a datelor cu ajutorul dictionarelor.
Ca o remarca amuzanta, sunt de asemenea patentate pana la moarte. Toate clasele de algoritmi LZ78 si multe clase de algoritmi LZ77 sunt victimele patentelor sofware, ceea ce inseamna ca folosirea lor implica plata celor care detin patentul sau, in caz contrar, confruntarea in instanta.
2. Definirea problemei
Programul realizeaza compresia unui fisier bazata pe algoritmul Limpel-Ziv.
Compresoarele care folosesc dictionare inlocuiesc un simbol sau o colectie de simboluri cu un index intr-un dictionar. Felul in care simbolurile sunt alese si cum este reprezentat indexul la iesire sunt dependente de implementare.
Compresoarele dictionar adaptative incep fara nici o valoare sau cu un mic dictionar static si apoi extind dictionarul cu bucati din sirul de date de intrare pe masura ce acesta este parcurs.
Ceea ce face acesti algoritmi valorosi este faptul ca ei combina avantajele unui model adaptativ cu viteza si eficienta modelelor dictionar. Nu numai ca LZ78 compreseaza mai bine decat compresorul semi-adaptativ Huffman, dar va realiza acest lucru si cu o viteza mult mai mare.
Ceea ce este surprinzator in legatura cu aceste scheme este ca sunt simple atat in ceea ce priveste conceptul, cat si implementarea.
Extrase din Jacob Ziv si Abraham Lempel, 'A universal algorithm for sequential data compression', IEEE Transactions on Information Theory, Volum 23,Numar 3, Mai 1977, pag 337-343.
LZ77 trateaza fisierul de intrare ca dictionary. In loc sa codeze un index referitor la un dictionary plin de stringrui, codeaza un triplet <off,len,char>, unde "off" este offsetul fisierului la care incepe stringul, "len" este lungimea potrivirii si "char" este primul caracter care nu se potriveste.
Pentru motive de eficienta, cele mai multe scheme bazate pe LZ77 folosesc o abordare "sliding window". Compresorul pastreaza urma ultimilor N octeti de de date (in mod usual 4K sau 8K) intr-un buffer, potrivindu-l impreuna cu un caracter o data, alaturand urmatorul caracter la inceputul bufferului si inlaturand caracterul la sfarsit. Bufferul arata cam asa:
0 1 2 3 4 5 6 || 7 8 9
a b b a c a c b a c
Caracterele din stanga deja au fost compresate. Caracterele din dreapta au un rol dublu ca un buffer care se uita inainte (ceea ce poate fi util) si ca string de compresat in continuare. Numarul de octeti in bufferul care se uita inainte este referit ca "F", asa ca primele N-F caractere din buffer au fost deja codate.
Atunci cand este realizata compresia, LZ77 cauta in buffer cea mai buna potrivire. Este o simpla comparare de stringuri, asa ca o abordare simplista va compara fiecare string la rand (de exemplu, compara F octeti incepand cu offsetul 0 cu baitii din bufferul care se uita inainte, apoi compara F baiti incepand cu offsetul 1 s.a.m.d.). Cand gaseste cea mai buna potrivire, returneaza offsetul bufferului la care a fost gasita si cate caractere au fost concordante.
Dupa compresia unui string, shiftam totul la stanga cu "len" caractere si preluam alte "len" caractere din datele de itnrare. Ar trebui sa fie clar ca cel mai lung string care poate fi potrivit este egal cu F, lungimea bufferului care se uita inainte. (Aceasta nu este o limitare a familiei de algoritmi).
Cea mai buna abordare a cazului in care nu s-a gasit nici o potrivire (poate un caracter intalnit pentru prima data), primul caracter care nu s-a potrivit este de asemenea output.
Tot ceea ce este nevoie la rutinele de decompresie este sa copieze "len" baiti de date la offsetul specificat la output. Aceasta fce extractia foarte rapida, de vreme ce nu este mai mult decat o copiere in memorie.
Dictionarul nu este nimic mai mult decat ultimii N-F baiti de input.
Sa presupunem ca avem situatia urmatoare:
1 2 3 4 5 6 7 8 9
a b c x || x x x x y
Comparatiile de stringuri au voie sa sara in bufferul care se uita inainte, atata vreme cat macar primul caracter este afara. Asadar pentru a comprima stringul "xxxxy", ar fi un output de genul <4, 4, 'y'> pentru ca prima potrivire a avut loc la 4, a mers pentru 4 octeti si prima nepotrivire a fost 'y'.
Cand este extras, decompresorul va vedea ceva de genul:
<?, ?, 'x'> <4, 4, 'y'>
Asa ca va avea deja 'x' la pozitia 4. Apoi copiaza 'x' de la pozitia 4 la pozitia 5, apoi copiaza pozitia 5 (care acum este un 'x') la pozitia 6, apoi copiaza pozitia 6 (care este de asemenea un 'x') la pozitia 7. Pozitia 7 este copiata la pozitia 8 si in final pune 'y' in pozitia 9.
Trucul consta in faptul ca se compara ultimele bucati ale stringului cu cele de dinainte si pe cele de dinainte cu bucati deja compresate sau extrase.
Mai sunt si alte detalii de implementare de luat in considerare. In primul rand, conceptul de sliding window. Caracterele shiftate peste 1 de fiecare data cand avem nevoie de mai mult input este incet. Solutia comuna este folosirea unui buffer circular si apoi sa se trateze toate valorile mod N. Din aceasta cauza, marimea bufferului este de obicei o putere a lui 2 (deci se poate efectua un AND).
In al doilea rand, am putea avea nevoie de structuri de date pentru a mari viteza cautarii. Acest lucru nu trebuie sa fie teribil de complicat. O tehnica uzuala este construirea unui arbore binary cu N-F intrari in el (cate una pentru fiecare string codat), in care fiecare este lung de F baiti. Desi pare ca foloseste multa memorie, in realitate nu se intampla acest lucru pentru ca fiecare nod al arborelui este doar un offset in sliding window. Nodurile sunt adaugate si sterse pe masura ce fereastra shifteaza.
In al treilea rand nu s-a precizat ce este in buffer la outset. De fapt nu conteaza atat vreme cat codorul si decodorul au aceeasi imagine. Traditional este umplut cu spatii sau zerouri.
Variatii ale acestui model permit stringului sa inceapa la orice pozitie in fisier si sa mearga pentru orice lungime, dar aceasta necesita ceva tehnici mai elaborate si pot necesita multa memorie.
Lucrul bun totusi este ca se vor trata cuvinte intregi sau chiar grupuri de cuvinte care au fost folosite in trecutul apropiat. Penalitatea pentru intalnirea de noi cuvinte este mica, de vreme ce multe cuvinte pot fi despartite in cuvinte mai mici care au fost intalnite inainte. Aceasta, plus natura de RLE a bufferului care se uita inainte (care merge pentru grupuri de simboluri), contribuie la un model foarte efficient.
Cel mai important dezavantaj al LZ77 este viteza de compresie. Aceasta poate fi redusa cu tehnici avansate de hashing, dar nu exista nici o cale pentru a evita multe comparari de stringuri.
Din punct de vedere theoretic, punctual foarte slab al algoritmului LZ77 este ca "uita" de date mai vechi de 4K sau 8K. Pentru a trece de aceasta problema, nu numai ca este necesara foarte multa memorie, dar implica si comparari de stringuri chiar cu intregul fisier, asa ca timpul necesar creste liniar. De asemenea, lungimea fixa a valorii "len" se interpune, pentru ca limiteaza compresia maxima de atins la "len" impartit la marimea trimpletului <offset, size, char>.
Din punct de vedere practice, daca primele caractere sunt 'abcde" atunci vor aparea o serie de triplete ca: <0, 0, 'a'> <0, 0, 'b'> etc.
LZSS inlatura aceasta dureroasa irosire de codare si LZH si LZB duc lucrurile putin mai departe codand offsetul si valoare lungimii mai efficient.
LZ78
Jacob Ziv and Abraham Lempel, 'Compression of individual sequences via
variable-rate coding', IEEE Transactions on Information Theory, Volum
24, Numar 5, Septembrie 1978, pag 530-536.
Familia de algoritmi LZ78 reprezinta o abordare diferita a problemei. Este interesanta din punct de vedere practice (pentru viteza mai rapida de compresie) sin din punct de vedere theoretic (compresia devine gradual optimala).
LZ78 fragmenteaza inputul in "expresii", unde fiecare expresie este cea mai lunga potrivire cu expresia de dinainte plus primul caracter care nu s-a potrivit.
Iata un exemplu. Sa presupunem ca avem stringul 'aaabbabaabaaabab'. Compresorul LZ78 ia cate un caracter o data.
Prima data, ia 'a'. Nu exista nici o expresie in dictionary, asa ca spune "1 = a' si ca output avem <0, 'a'>. Aceasta inseamna, "la decodare ia expresia 0 (expresia vida) si adauga un "a". Decodorul asigneaza automat rezultatul expresiei 1, care pastreaza decodorul in sync cu codorul.
Apoi, mai ia un 'a'. Are o expresie in dictionar care I se potriveste, asa ca merge si ia urmatorul caracter, inca un 'a'. Asigneaza '2 = 1+a', si ca output <1, 'a'>, de vreme ce expresia #1 este urmata de un 'a'.
Urmatorul caracter este 'b'. Nu a mai fost intalnit inainte, asa ca seteaza '3 = b' si ca output <0, 'b'>.
Urmatorul este inca un 'b'. Se potriveste cu expresia 3, ia urmatorul caracter, un 'a'. Nu avem un 'ba' in dictionary, asa ca seteaza '4 = 3+a' si ca output <3, 'a'>.
Pana acum avem:
Input: a aa b ba
Nr expresiei: 1 2 3 4
Output: <0,a> <1,a> <0,b> <3,a>
("ab" nu este o expresie cunoscuta, desi a aparut in input. LZ78 nu preia toate substringurile asa ca LZ77.)
Urmatorul caracter este un 'b', expresia 3. Apoi avem un 'a', expresia 4 (NU expresia 1. Cautam expresia 3 urmata de un 'a', nu expresia 0 urmata de un 'a'). Apoi este inca un a, dar nu a fost intalnit nici un "baa" inainte, seteaza '5 = 4+a' si ca output <4, 'a'>. Decodorul va sti ca 4 = 3+a, si ca 3 = 0+b, asa ca outputul va fi 'baa'.)
Urmatorul caracter este un 'b' (expresia 3), urmat de un 'a' (expresia 4), urmat de un alt 'a' (expresia 5) si apoi inca un 'a'. Asa ca seteaza '6 = 5+a' si ca <5, 'a'>. Aceasta inseamna ca am inlocuit stringul "baaa" cu perechea <5, 'a'>, asa ca rata compresiei este imbunatatita.
In final, avem un 'b' (expresia 3), un 'a' (expresia 4) si un 'b' (neintalnit inca), asa ca setam "7=4+b" si output <4,'b'>. Rezultatele finale arata astfel:
Input: a aa b ba baa baaa bab
Nr expresiei: 1 2 3 4 5 6 7
Output: <0,a> <1,a> <0,b> <3,a> <4,a> <5,a> <4,b>
De remarcat ca inputul este fragmentat in bucatele mici, asa incat daca urmatorul string input este 'baabaaa', ne vom allege cu o expresie noua pentru "baab" (5+b), in vreme ce LZ77 ar fi fost in stare sa potriveasta intregul.
Pe de alta parte, nu este limita in lungimea expresiilor. Dupa cum se poate observa, acestea devin usor usor mai lungi pe masura ce se proceseaza mai mult input. Nu este limita in ceea ce priveste cat de in urma o expresie poate referi. Atunci cand umplem memoria disponibila, putem pur si simplu sa curatam tabelul si sa incepem sa compresam din nou doar cu expresia nula.
Din punct de vedere practice, LZ78 are o compresie mult mai rapida, pentru ca expresiile pot fi reprezentate de o structura de date "trie". Fiecare nod din "trie" reprezinta o expresie anume. Exista un copil pentru fiecare caracter care poate urma expresia. Ca nota nu este necesar sa fie un copil pentru fiecare carcater posibil care poate urma; doar pentru cele care au fost deja intalnite. Trieul pentru secventa de mai sus arata cam asa:
0
a / b
/
/
1 3
a / a /
/ /
/ /
2 4
a / b
/
/
5 7
a /
/
/
6
Este un arbore binary pentru ca au fost doar doua caractere distincte in input. In practica pot fi pana la 256 de copii ai unui anumit nod.
Considerand stringul de input, incepem cu nodul 0 si traversam ramura adecvata la fiecare pas. Deci daca avem "baab" apoi, am incepe la 0, luand ramura 'b' la 3, ramura 'a' la 4, ramura 'a' la 5 si apoi incercam sa luam calea ramurii nonexistente 'b'.
Cand ajungem la un nod care nu are ramura pentu caracterul urmator, cream un nod nou si o ramura catre el, apoi se da outputul cu numarul nodului la care s-a oprit si caracterul la care ne-am oprit.Aceasta permite decodorului sa reconstruiasca un arbore ideal.
O consideratie importanta este cum numarul expresiei va fi codat. De vreme ce nu exista limita asupra marimii, trebuie sa existe o cale eficienta de codare. Solutia este sa fie codata intr-un numar variabil de biti. Deci se incepe cu 1 bit. Dupa expresia 1, se folosesc 2 biti. Dupa expresia 3, 3 biti. Dupa expresia 7, 4 biti si tot asa. Marimea este automat expandata de compressor si decompresor, deci nu este nici o confuzie asupra numarului de biti de folosit.
Deci nu este limita in lungimea expresiilor, dar trebuie sa ne gandim la cazul in care ramanem fara memorie. De asemenea fiecare expresie noua este alcatuita dintr-o expresie veche plus un caracter.
Constructia dictionarului nu contine setul complet de stringuri. Totusi, contine un set unic de stringuri intalnite - fiecare adaugare in table este un prefix intalnit inainte plus un caracter care se comiba pentru a forma un string inca neintalnit.
LZ78 este baza LZW.
Programul fiind scris in limbaj de asamblare pune in valoare resursele de baza ale calculatorului pe care ruleaza .
3. Utilitatea economica
Utilitatea economica al acestui produs software este data de reducerea costurilor de stocare si de regasire a datelor pentru care se aplica.
4. Solutia propusa
Algoritmul de compresie construieste o translatie a stringului intr0un table care mapeaza substringuri din sirul de intrare in coduri de lungimi fixate. Aceste coduri sunt folosite de algoritmul de decompresie pentru a reconstrui tabela compresorului si a reconstrui sirul initial de date. In forma simpla, algoritmul se poate prezenta in felul urmator: Daca <w>k este in table, atunci <w> este in table.
Algoritmul este inspirat din articolul "A Technique for High
Performance Data Compression' de Teryy A. Welch in IEEE Computer Volume 17, Nr 6, pg 8-19.
Pasii algoritmului in linii mari:
<w> este un cod care reprezinta un string in table. Cand un caracter nou k este citit, se cauta in table <w>k. Daca aceasta combinatie este gasita, <w> este setat la codul pentru care combinatia si urmatorul caracter este citit. In caz contrar, aceasta combinatie este adaugata in table, codul <w> este scris in sirul de output si <w> este setat la k.
Codurile de output au lungime variabila. Pornesc de la 9 biti. O data ce numarul de coduri depaseste marimea codului curent, numarul de biti din cod este incrementat. Cand tabela este complet plinaun cod curata este transim pentru decompresor si tabela este reinitializata. Programul foloseste o lungime maxima de cod de 12 biti pe un total de 4096 coduri.
Fisierul MACROS.MLB contine macrourile necesare programului. Aceste sunt:
print str
input buf
hcreat path,attrib
hdeschid path,mode
hinkid handle
hcit handle,buf,siz
hscriu handle,buf,siz
deletp path
malloc siz
setmem siz,segm
exit
6. Codul sursa comentat
title lzcomp - compresor de fisiere utilizand algoritmul Limpel-Ziv
;Sectiune Constante
curata equ 256 ;cod Clear
eof equ 257 ;marcator de sfarsit de fisier
prim_liber equ 258 ;cod primul liber
maximum equ 4096 ;cod Max + 1
include macros.mlb
;intrari in Tabela Hash - structura pt usurinta
hash_intr struc
primul dw ? ; prima data cu aceasta valoare
urmat dw ? ; urmatoarea data de-a lungul sirului
char db ? ; caracter sufix
hash_intr ends
;declararea segmentelor
code segment byte public 'code'
code ends
stack segment word stack 'stack'
dw 128 dup (?)
stack ends
data segment word public 'data'
data ends
memory segment para public 'memory'
hash label hash_intr
memory ends
;Codul
code segment
assume cs:code,ds:data,es:data,ss:stack
start proc far
mov bx,seg hash ;Sfarsitul programului
mov ax,ds ;Inceputul programului
sub bx,ax ;Marimea programului
inc bx ;ca sa fim siguri
setmem bx ;Stabiliarea marimii
mov bx,data ;set up adresare segment de date
mov es,bx
mov ds,bx
print prompt_in ;Preluarea numelui fisierului de comprimat
input fisier_in
print crlf
print prompt_out ;Preluarea numelui fisierului comprimat
input fisier_out
print crlf
mov al,fisier_in+1 ;Numele fisierelor se termina cu null
xor ah,ah
mov si,ax
mov fisier_in+2[si],0
mov al,fisier_out+1
mov si,ax
mov fisier_out+2[si],0
hdeschid fisier_in+2,0
mov handler_input,ax
hcreat fisier_out+2,0
mov handler_output,ax
call compresie ;Compresarea fisierului
hinkid handler_input ;inchidere in si out
hinkid handler_output
exit ;sfarsit
start endp
data segment
prompt_in db 'Calea completa a fisierului de comprimat: $'
prompt_out db 'Calea completa a fisierului comprimat: $'
fisier_in db 80,0,80 dup (?)
fisier_out db 80,0,80 dup (?)
crlf db 13,10,'$'
handler_input dw ?
handler_output dw ?
data ends
compresie proc near
malloc 1280 ;Alocare de spatiu pentru tabela hash
mov hash_seg,ax ;salvarea segmentului de adresa
c1: call init_tabela ;initializarea tabelei si variabile
mov ax,curata ;scrie curata code
call scrie_cod
call cit_caracter ;citeste primul caracter
c4: xor ah,ah ;transforma caracter in cod
c4a: mov cod_prefix,ax ;Seteaza cod prefix
call cit_caracter ;Citeste urmatorul caracter
jc c17 ;
mov k,al ;salveaza caracter in k
mov bx,cod_prefix ;Preia cod prefix
call caut_cod ;verifica daca exista potrivire in tabela
jnc c4a ;nc inseamna da, cod nou in ax
call adaugare ;adauga perechea in tabela
push bx ;salveaza noul cod
mov ax,cod_prefix ;scrie vechiul cod prefix
call scrie_cod
pop bx
mov al,k ;Preia ultimul caracter
cmp bx,cod_maxim ;S-a depasit marimea codului?
jl c4 ;less inseamna nu
cmp nrbiti,12 ;actualmente mai putin de 12 biti?
jl c14 ;da
mov ax,curata ;scrie cod curata
call scrie_cod
call init_tabela ;Reinitializare tabela
mov al,k ;preia ultimul caracter
jmp c4 ;incepe iar
c14: inc nrbiti ;incrementare numar biti
shl cod_maxim,1 ;dublare marimea max de cod
jmp c4 ;preia urmatorul caracter
c17: mov ax,cod_prefix ;scrie ultimul cod
call scrie_cod
mov ax,eof ;scrie codul eof
call scrie_cod
mov ax,bit_offset ;asigurarea ca bufferul e flushed la fisier
cmp ax,0
je c18
mov cx,8 ;converteste biti in baiti
xor dx,dx
div cx
or dx,dx ;daca sunt biti in plus, asigurare ca
je c17a ;sunt scrisi
inc ax
c17a: call flush
c18: ret
compresie endp
data segment
hash_seg dw ?
cod_prefix dw ?
cod_liber dw ?
cod_maxim dw ?
nrbiti dw ?
k db ?
data ends
init_tabela proc near
mov nrbiti,9 ;seteaza marimea codului la 9
mov cod_maxim,512 ;seteaza cod maxim la 512
push es ;salv reg de segm
mov es,hash_seg ;adreseaza tabela hash
mov ax,-1 ;flag neutilizat
mov cx,640 ;goleste primele 256 intrari
mov di,offset hash ;pointeaza prima intrare
rep stosw ;goleste
pop es ;restaurarea reg segm
mov cod_liber,prim_liber ;seteaza cod urmator pe utilizat
ret ;gata
init_tabela endp
scrie_cod proc near
push ax ;salveaza cod
mov ax,bit_offset ;preia offsetul bitului
mov cx,nrbiti ;ajustare offset bit cu marime cod
add bit_offset,cx
mov cx,8 ;converteste offset bit in offset bait
xor dx,dx
div cx
cmp ax,1020 ;se apropie de sfarsitul bufferului?
jl scrc1 ;less inseamna nu
call flush ;scrie buffer
push dx ;dx contine offset in octet
add dx,nrbiti ;ajusteaza cu marimea codului
mov bit_offset,dx ;offset bit nou
pop dx ;restaureaza dx
add ax,offset outputul ;pointeaza spre ultimul bait
mov si,ax ;pune in si
mov al,byte ptr [si] ;muta baitul pe prima pozitie
mov outputul,al
xor ax,ax ;offset bait de zero
scrc1: add ax,offset outputul ;pointeaza in buffer
mov di,ax ;destinatie
pop ax ;cod restaurare
mov cx,dx ;offset in bait
xor dx,dx
jcxz scrc3 ;daca offset in bait este zero, sare peste shift
scrc2: shl ax,1 ;cod rotate
rcl dx,1
loop scrc2
or al,byte ptr [di] ;preia bitii aflati momentan in buffer
scrc3: stosw ;salveaza datele
mov al,dl ;preia bitii extra
stosb ;si salveaza
ret
scrie_cod endp
data segment
bit_offset dw ?
outputul db 1024 dup (?)
data ends
flush proc near
push ax ;salveaza toti registrii
push bx ;AX contine numarul de baiti de scris
push cx
push dx
hscriu handler_output,outputul,ax ;scrie fisierul compresat
pop dx
pop cx
pop bx
pop ax
ret
flush endp
cit_caracter proc near
mov di,offset_input ;a mai ramas ceva in buffer?
cmp di,marime_input
jl citch1 ;less inseamna da
hcit handler_input,data_intr,1024 ;citeste urmatoarea bucata de input
cmp ax,0 ;a mai ramas ceva?
je citch2 ;egal inseamna nu, terminat
mov marime_input,ax ;salveaza baitii cititi
mov offset_input,0 ;Pointeaza la inceputul bufferului
mov di,0
citch1: lea si,data_intr[di] ;Pointeaza la caracter
lodsb ;il citeste
inc offset_input ;Ajusteaza pointer
clc ;succes
ret
citch2: stc ;nu a ramas nimic
ret
cit_caracter endp
data segment
data_intr db 1024 dup (?)
offset_input dw 0
marime_input dw 0
data ends
caut_cod proc near
push ds ;Salveaza reg segm
mov ds,hash_seg ;pointeaza catre tabela hash
call index ;converteste cod in adresa
mov di,0 ;flag
cmp [si].primul,-1 ;a mai fost acest cod folosit?
je cauc4 ;egal inseamna nu
inc di ;seteaza flag
mov bx,[si].primul ;preia prima intrare
cauc2: call index ;converteste cod in adresa
cmp [si].char,al ;este acelasi caracter?
jne cauc3 ;ne inseamna nu
clc
mov ax,bx ;pune cod gasit in ax
pop ds ;restaureaza reg segm
ret ;gata
cauc3: cmp [si].urmat,-1 ;au mai ramas cu acest prefix?
je cauc4 ;egal inseamna nu
mov bx,[si].urmat ;preia cod urmator
jmp cauc2 ;incearca din nou
cauc4: stc ;nu a fost gasit
pop ds ;restaureaza reg segm
ret ;gata
caut_cod endp
index proc near
mov si,bx ;si = bx * 5 (5 baiti de intrari in hash)
shl si,1 ;si = bx * 2 * 2 + bx
shl si,1
add si,bx
ret
index endp
adaugare proc near
mov bx,cod_liber ;preia cod de folosit
push ds ;pointeaza spre tabela hash
mov ds,hash_seg
cmp di,0 ;este folosit acest prefix prima data?
je adaugc1 ;egal inseamna da
mov [si].urmat,bx ;pointeaza ultima utilizare la noua intrare
jmp short adaugc2
adaugc1: mov [si].primul,bx ;Pointeaza prima utilizare la noua intrare
adaugc2: cmp bx,maximum ;s-a ajuns la limita codului?
je adaugc3 ;egal inseamna da, doar return
call index ;preia adresa noii intrari
mov [si].primul,-1 ;initializeaza pointerii
mov [si].urmat,-1
mov [si].char,al ;salveaza caracterul sufix
inc es:cod_liber ;ajusteaza noul cod
adaugc3: pop ds ;restaureaza reg segm
ret
adaugare endp
code ends
end start
Compresia de fisiere este o metoda buna de a elimina informatia redundanta care se regaseste din ce in ce mai mult in spatiile de stocare odata cu marirea acestora din urma si cu dezvoltarea unor retele de spatii de stocare.
Multa din informatia stocata la un moment dat de timp, la care se fac regasiri si modificari dese se preteaza la un nivel de redundanta acceptabil daca nu, uneori, chiar mare.
Însa in cazul in care informatia este stocata la un moment dat doar pentru verificare pentru un anumit timp datele va trebui sa prezinte o redundanta ce tinde catre zero.
De aceea, programul prezentat in aceasta lucrare este util din punct de vedere economic.
[Jac77] Jacob Ziv si Abraham Lempel, 'A universal algorithm for sequential data compression', IEEE Transactions on Information Theory, Volum 23, Nr 3, Mai 1977, pag 337-343.
{Jac78] Jacob Ziv and Abraham Lempel, 'Compression of individual sequences via
variable-rate coding', IEEE Transactions on Information Theory, Volum
24, Nr 5, Septbrie 1978, pag 530-536.
[SOMN92] Somnea D., Vladut T., Programare in assembler, Editura Tehnica, Bucuresti, 1992
Copyright © 2024 - Toate drepturile rezervate
