• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Cypher

Escrita em ficheiros dados do algorimto LZ77

20 mensagens neste tópico

Tenho aqui um problema que nao estou a perceber muito bem ....

pra quem não conheça o algorimto LZ77

http://pt.wikipedia.org/wiki/LZ77#Algoritmo

no resultado final esta em "tuplas"

Abaixo ilustramos o algoritmo LZ77 com um exemplo da compressão da cadeia A_ASA_DA_CASA, usando janela de tamanho 8 e buffer de look-ahead de tamanho 4.

VEJAM O EXEMPLO ->  http://pt.wikipedia.org/wiki/LZ77#Algoritmo

Temos então 6 tuplas, cada tupla ocupa 15 bits (4 para a posição dentro da janela, 3 para o tamanho e 8 para o caractere no final), perfazendo 90 bits. Comparado com a cadeia original de 104 bits (13 bytes) a compressão não é muito boa, mas para arquivos maiores o tamanho da janela pode ser ajustado, assim como o tamanho do buffer, conseguindo taxas de compressão bem melhores.

o meu problema é que quando mando escrever pro ficheiro cada digito que escrevo ocupa um byte, como é que escrevo cada tupla no ficheiro a ocupar os 15 bits ???

cumps....

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Por outras palavras

como é que gravo (2,2,C) este valor so ocupando 15 bits ??

(4 para a posição dentro da janela, 3 para o tamanho , 8 para o caractere no final)

é que cada digito ocupame um byte

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

um possível solução é trabalhar com um array de bytes, recorrendo aos operadores de bits para o manipular, e no final escrever os dados do array num ficheiro.

se tentares trabalhar directamente com o ficheiro acho que não vai dar, pois as funções que lidam com ficheiro acho que só trabalham com bytes.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

sim podia passar os dados pra binario mas mesmo assim cada 0 e cada 1 vale 1 byte

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

podes pegar em 8 sequências de 15bits e já ficas com 15bytes, que já podes escrever num ficheiro.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

pois ai é que esta o problema é que eu qria escrever esses bit no ficheiro... se for a escrever os 15 bytes o algorimto de optimizaçao nao faz nada pois estou a escrever mal no ficheiro.... o meu problema era escrever esses 15 bytes mas em bits como mostra no algorimto....

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não, as operações bitwise trabalham bite a bit, doute 1 ex,

tinhas 4 bits para a posição dentro da janela, logo essa posição varia de 0000->0 a 1111->31

então o que tu fazes é escrever num byte um valor de 0 a 31, e depois shiftar 4 bits para a esquerda de forma a ficarem na ordem pretendida

para a análise bitwise o formato que deves usar é o hexadecimal ...

código:

unsigned char byte = 0;          #byte = 0000 0000

byte= 10;                                #byte = 0000 1010

byte << 4;                              #byte= 1010 0000

prontos, agora ja tens os 4 bits postos, agora falta por 3 bist pa posição n é?

para guardar o trabalho realizado e juntar os 3 bits é necessário fazer uma mascara que para os 4 bits iniciais é 0x0F (formato hex)

agora vamos aos 3 bist com variavle auxiliar

unsigned char byte2 =0;          #byte2= 0000 0000

byte2=3;                                  #byte2=0000 0011,    posição 3 por ex

agora queres colocar os 3 bits menos significativos, contendo o valor de posição numa posição imediatamente a seguir aos 4 anteriores

byte2=byte2<<1                    #byte2=0000 0110

agora tens os valores nas posições correctas mas em variáveis diferentes, para os juntares neste caso n é necessário mas podia ser, usas uma mascara 0xF0

byte=(byte | (byte2 & 0x0F))  #byte =1010 0110

como tas a ver, coloquei nos 4 bits mais significativos o valor 10 e nos 3 bist seguintes o valor 3, valores bit bit...

Agora é so continuar o raciocínio e completar com o que falta!   

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não, as operações bitwise trabalham bite a bit, doute 1 ex,

tinhas 4 bits para a posição dentro da janela, logo essa posição varia de 0000->0 a 1111->31

1111 é 15 :P

e ao mandar escrever no ficheiro os 15 bits nao me escreve 15  numeros (0 e 1s) ???

é que o meu problema é mesmo esse ao escrever no ficheiro nao consigo escrever os 15 bits referentes a cada tupla... escreveme 15 bytes!!!!

nao sabes se a trabalhar com bits irá escrever em bits e nao em bytes ??

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tu tas a trabalhar com a variàvel que defines,

char é a menor e são 8bits 1 byte, mas tanbém podes trabalhar com inteiros que são 4 bytes,

o tamanho n interessa desde que a informação que ele contenha bit a bit  for a correcta,

o que quero dizer é que é a mesma coisa escreveres 8 bits seguidos 0000 0011, como escreveres logo um byte com o valor 3, o que la esta é exactamente a mesma coisa ...

1111 é 15 decimal :biggrin: tens razão escapou  :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

funciona dessa maneira :P

agora tenho um pequeno problema ... sao 16 bits no total nao sao 15 porque a tabela ascii precisa de 7 e nao de 8...

cada char tem 8 bits = 1 byte  logo eu tenho 4+5+7=16 bits logo preciso de dois char ou seja 2 bytes para os 16 bits... e nao estou a ver mesmo como juntar a informaçao toda... tipo 5+4 ja da mais que um byte... como é que eu posso resover isto??

da pra juntar dois bytes ou seja dois char e trabalhar com manipulaçao de bits =??? ou sera mais facil com um inteiro visto que o inteiro tem 16 bits ??

cumps...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É isso mesmo, usas inteiros e ja tens o problema resolvido e fica-te muito mais facil de trabalhar, se bem que com 2 chars tb funcionava...

Ja agora por curiosidade o facto de a unidade mais baixa ser um byte, deve-se ao facto de o pc ter registos de 32 bits, e se com esses 32 bits endereçasses posições de memória bit a bit, a tua memória maxima endereçável seria de aprox 4G, para melhorar esta situação e aumentar a capacidade de endereçamento de memória, as instruções de endereçamento não usam os 4 bits menos significativos entre outras coisas é claro ...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

yah deves tar a falar do big & litlle endian e dessas cenas !! mas isso é outra historia! XD

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Um inteiro tem 16 bits? Em que plataforma estás a trabalhar? É que em plataformas de 32 bits, int tem 32 bits.

O short é que tem 16 bits.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

nao. depende é sim da arquitecturas em que trabalhas, os valores variam de arquitectuta para arquitectura o normal é 2 bytes e 4 bytes ou seja os 16 bits e 32 bits ...

por exmplo em unix um inteiro tem tamanho de 4 bytes, ja num microcomputador tem 2.

Exprimenta

printf("int = %d", sizeof(int));

cumps...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

nao. depende é sim da arquitecturas em que trabalhas, os valores variam de arquitectuta para arquitectura o normal é 2 bytes e 4 bytes ou seja os 16 bits e 32 bits ...

por exmplo em unix um inteiro tem tamanho de 4 bytes, ja num microcomputador tem 2.

Exprimenta

printf("int = %d", sizeof(int));

cumps...

acabaste por dizer o mesmo que o TheDark.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Plataforma

por exmplo em unix um inteiro tem tamanho de 4 bytes, ja num microcomputador tem 2.

É engraçado como falas em arquitecturas e depois dás o exemplo de um Sistema Operativo :;)

Microcontroladores como o ARM têm int de 32 bits. Daí a minha pergunta ("Em que plataforma estás a trabalhar?") à qual não chegaste a responder =P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

yah e ?? ...

pag 46 luis damas ;) ....

ja agora tou a trabalhar numa CISC :)  (intel)..

cumps...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

IA32? Então int tem (provavelmente) 32 bits. A não ser que uses um compilador esquisito...

De qualquer forma, o meu 1º post foi por teres dito que um int tem 16 bits. O que comprovadamente sabes que não é verdade numa arquitectura de 32 bits ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora