Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune.stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme



Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Informatica


Index » educatie » Informatica
» PROIECT LIMBAJE DE ASAMBLARE - Compresia fisierelor utilizand algoritmul Limpel - Ziv


PROIECT LIMBAJE DE ASAMBLARE - Compresia fisierelor utilizand algoritmul Limpel - Ziv




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:

  1. Initializarea tabelului cu stringuri de un singur caracter.
  2. Citeste primul caracter. Seteaza <w> (stringul prefix) la acel caracter.
  3. Citeste urmatorul caracter, k.
  4. Daca se intalneste sfarsitul de fisier, cod output <w> si iesire.
  5. Daca <w>k este in table, seteaza <w> la <w>k; mergi la pasul C.
  6. Cod output <w>
  7. Pune <w>k in table.
  8. Seteaza <w> la k. Mergi la pas 3.

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

5. MACROURI

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 ;Cary inseamna sf de fisier

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

CONCLUZII

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.

7. BIBLIOGRAFIE

[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




loading...




Politica de confidentialitate


Copyright © 2020 - Toate drepturile rezervate