[es] - Sistem za LZ kodiranje i dekodiranje!

MixMaster

Član broj: 10076
Poruke: 323
*.cis.cg.ac.yu.

+32 Profil

Sistem za LZ kodiranje i dekodiranje!

^{23.12.2005. u 22:36 - pre 222 meseci}

Pokusavam da napravim C/C++ algoritam za LZ kodiranje i dekodiranje binarnog alfabeta (sa razlicitim varijanama duzine rjecnika simbola, kao i sa mogucnoscu izbora pocetnog stanja u rjecniku podataka).
Ajde da probamo za sada ovo sto nije u zagradama, dakle da pocnemo od LZ kodiranja.

Napomena: LZ kodiranje je zasnovano na rjecniku (dictionary based) u kojem se pamte do sada vidjeni stringovi (ponavljanja kodnih simbola).

Evo i PRIMJER za one koji nisu upuceni u LZ kodiranje a znaju C/C++:
Polazimo od praznog rjecnika i pod pretpostavkom da nas rjecnik nema vise od 8 simbola kada je pun. Neka je dat string:
1011010100010...
OBJASNJENJE:
Ovaj string se dijeli dok se ne dobije najkraci string koji prethodno nije postojao u rjecniku. String se upisuje kao novi element u rjecnik, koji se sastoji od prethodnog prefiksa i novog bita. Npr. bit 1 nije bio vidjen prethodno i zato mi saljemo indeks njegovog prefixa (postavljen na 000) i zatim broj 1. Dodamo 1 u rjecnik (dakle 1 nema nista “ispred sebe”, odn. ima null ciji je LZ indeks 000). Zatim, nula nije postojala prethodno i mi postavljemo indeks njenog prefiksa i broj 0 (nulu smo dae, uzeli za novi string, ispred nule ne postoji nista, tj. postoji null ciji je LZ indeks 000). Dodamo 0 u rjecnik. Niz 11 ima prefiksni string 1 (dakle, gleda se samo zadnja cifra, sve ostalo se zove prefiks-u slucaju da niste uspjeli da to pohvatate) i zato se salje prefiks string od 1 i saljemo njegov indeks i broj 1. Tako idemo do kraja i rjecnik izgleda ovako:

LZ indeks|sadrzaj rjecnika
000|null <- null postavljamo jer smo rekli “polazimo od praznog rjecnika”
001|1
010|0
011|11
100|01
101|010
110|00
111|10

I napokon, kodirana sekvenca ima oblik:
(000,1),(000,0),(001,1),(000,1),(100,0),(000,0),(001,0)

Huh, cini mi se da sam sve dobro odradio.
Dakle, ima li ko ideju kako da odradim ovo. Vjerovatno cu LZ indekse raditi preko cijelih brojeva, a string koji zadajem za kodiranje preko stringova. Hm, mada i ne mora... Dakle?!

Vidi bako, DžEDAJ!

Odgovor na temu

MixMaster

Član broj: 10076
Poruke: 323
*.cis.cg.ac.yu.

+32 Profil

Re: Sistem za LZ kodiranje i dekodiranje!

^{23.12.2005. u 22:51 - pre 222 meseci}

Jedna od ideja koja mi je pala na pamet je bila da novi string stavljam u NIZ stringova (stringovi u tom NIZU ce, naravno, biti odvojeni znakom '\0'); za ovo je naravno napraviti i NIZ pokazivaca na stringove. Sve bi to islo, recimo ovako:

Code:

//Primer sa nizom stringova u jednom stringu, i sa nizom pokazivaca na iste.

#include <stdio.h>
#include <string.h>

void main()
     {
      char stringovi[100], *pokazivac[20], privremeno[20];
      int velicina=1, trenutna_poz=0, i, j=0;

      printf("Unesite redom nekoliko stringova: ");

      pokazivac[0]=stringovi; //pokazivac na prvu rijec iz stringova...
                  //...sada je pokazivac[0]
      while(velicina)
           {
        gets(privremeno);
        velicina=strlen(privremeno); //velicina stringa koji unosimo

        for(i=0; i<velicina; i++) //kopiramo sve iz stringa privremeno
           {                      //u niz stringova "stringovi[100]"
            stringovi[trenutna_poz+i]=privremeno[i];
            }

            //zavrsili smo kopiranje iz stringa "privremeno" u
            //niz stringova "stringovi", sada treba da apdejtujemo
            //trenutna_poz, ali prije toga...

        stringovi[trenutna_poz+velicina]='\0'; //na kraj svakog
                               //stringa mora ici '\0'

        trenutna_poz+=velicina+1; //trenutna_poz=0
                      //velicina 4 (ako smo unijeli zora)
                      //1 dodajemo zbog terminacionog k.

        if(velicina)
          {               //azuriramo pokazivac da bi se u sledecoj..
           pokazivac[++j]=stringovi+trenutna_poz;
           }              //iteraciji upisivalo od te pozicije
        }

      for(i=0; i<j; i++) //Istampaj sve na stapokazuju svi pokazivaci iz niza
         {               //pokazivaca u *pokazivac[20]
          printf("%s\n", pokazivac[i]);
          }
      }

Znaci, ovo je primjer bez kodiranja...najjednostavnije unosenje stringova koje se ubacuju u NIZ kada god pritisnemo ENTER. Sada to treba nekako ukombinovati sa LZ kodiranjem. Prije svega treba nam jedna petlja koja ce prolaziti KROZ STRING KOJI MI KODIRAMO itd itd.
Huhh.
Dakle, jeli moze neko malo da mi pomogne oko ovoga?
Zahvaljujem.

Vidi bako, DžEDAJ!

Odgovor na temu