ep3: DIST maior que COMPR???

ep3: DIST maior que COMPR???

por Henrique Stagni -
Número de respostas: 13

Estava lendo no link que ha no ep para a wikipedia sobre o algoritmo de compactacao. Lá estava escrito que é possível termos um par (dist, compr), onde compr é MAIOR que dist. Depois de ler várias vezes percebi que esse procedimento melhoraria em muito a compressão de arquivos, principalmente quando ocorrer repetições consecutivas de um mesmo segmento de texto no arquivo a ser comprimido.

  • Gostaria de saber se o ep3 deve comprimir criando pares onde dist>compr quando for o caso.
  • Também gostaria de pedir, se possível, um link para um arquivo de texto grande a ser comprimido e sua taxa de compressão em um ep que funcione como o esperado. Assim eu poderia ver se entendi corretamente o algoritmo proprosto..... 

 

Em resposta à Henrique Stagni

Re: ep3: DIST maior que COMPR???

por Francisco Reverbel -
Sim, nas referências (dist, comp) geradas pelo LZ77 pode acontecer que comp seja maior que dist. Como você observou, uma referência na qual comp > dist aparece quando o arquivo original contiver repetições consecutivas de uma mesma seqüência de bytes. Por exemplo, se o arquivo original contiver o texto "xyzxyzxyzxyz", e se a primeira ocorrência de "xyz" tiver acabado de passar para o dicionário, a janela estará assim:

    ........xyzxyzxyzxyz..
    +++++++++++-----------

(Por simplicidade estou considerando uma janela de 22 bytes, como a do exemplo no enunciado. Para deixar claro o que está no dicionário e o que está no look-ahead,  coloquei caracteres '+' abaixo dos bytes no dicionário e caracteres '-' abaixo dos bytes no look-ahead.) Nessa situação, a seqüência "xyzxyzxyz", que está nos primeiros 9 bytes do look-ahead (a partir da posição 11 da janela), pode ser encontrada no dicionário (a partir da posição 8 da janela), embora ela não esteja inteiramente contida no dicionário! Apenas os primeiros 3 bytes da seqüência estão no dicionário, os 6 bytes restantes estão no início da janela. Mesmo assim, o LZ77 gerará a referência (3, 9) para representar essa a seqüência. Na descompressão, essa referência deve ser interpretada como uma ordem para "voltar 3 bytes na janela e, a partir desse ponto, copiar 9 bytes".
Em resposta à Francisco Reverbel

Re: ep3: DIST maior que COMPR???

por Gustavo Vilela -

Ainda em relação a situação quando compr>dist...utilizando um exemplo semelhante ao do professor, com o seguinte texto e janela.

........xyzxyzxyw..
+++++++++++-----------


(mantendo a utilização de '+' para representar o dicionário e '-' representando o look-ahead). Nessa situação a saída deverá ser (0,x) (0,y) (0,z) (3,5) (0,w) ???

Em resposta à Gustavo Vilela

Re: ep3: DIST maior que COMPR???

por Henrique Stagni -

Também tenho uma dúvida sobre a questão de compr>dist:

Imagine que "||" indica a separacao entre a parte que eh dicionario e a outra que eh look-ahead, que o look-ahead e o dicionario tem 8 caracetres de comprimento e que exista um arquivo que permita chegar a essa situação:

Z   A   B   A   Z   Z   A   B   || A   B   A   B   A   B   A   B
<------DICIONARIO---------->  <---------LOOK-AHEAD-------->

Nesse caso, existe um par que jah comprime tdo o look-ahead: (2, 8), certo?

Mas, por outro lado, o maior segmento do look-ahead que é uma repetição do dicionário é "A B A" e não "A B".

Então, o par (2, 8) deve ser usado mesmo nao representando o maior segmento em comum entre look-ahead e dicionário??

Em resposta à Henrique Stagni

Re: ep3: DIST maior que COMPR???

por Rodrigo Cordeiro Godoy -
Eu acho que o que você ainda não está fazendo é que quando você está medindo o compr da maior repetição, não necessariamente vc para quando entra no look-ahead, entendeu?

então usando o mesmo algoritmo (não 2 separados) você encontraria o ABA (7,3) e o (2,8) e então decidiria pelo 2,8 por ser maior
Em resposta à Rodrigo Cordeiro Godoy

Re: ep3: DIST maior que COMPR???

por Henrique Stagni -

eh entao:  eu tava fazendo com dois algoritmos separados e dai eu tive essa mesma ideia sua de dexar o mesmo algoritmo soh q rodando ateh o final..dai fui checar as diferencas......Neste exemplo, o meu primeira usa o (7,3) e o segundo (2,8). Queria saber qual o certo, pq o primeiro apesar de menor n está fazendo à risca [o que eu entendi q] o enunciado pede.

Em resposta à Henrique Stagni

Re: ep3: DIST maior que COMPR???

por Francisco Reverbel -
Os dois estão certos, mas o segundo (o que produz o par (2,8)) é o melhor, pois aumenta a taxa de compressão. Mas eu concordo que o enunciado deveria ser mais claro... Em vez de dizer "procure nos caracteres do look-ahead o segmento de maior comprimento...", o enunciado deveria dizer "procure o segmento de maior comprimento que começa em algum dos caracteres do look-ahead..."
Em resposta à Gustavo Vilela

Re: ep3: DIST maior que COMPR???

por Francisco Reverbel -
Sim, a saída será essa. No instante em que a janela estiver como você mostrou, os pares (0,x) (0,y) (0,z) já foram escritos no arquivo de saída e o próximo par a ser escrito é o (3,5).
Em resposta à Henrique Stagni

Re: ep3: DIST maior que COMPR???

por Francisco Reverbel -
Pressionei o botão "post" antes de ter respondido suas questões...

Sim, o EP3 deve, quando for o caso, gerar pares com dist > comp.

Quanto ao arquivo de exemplo, eu não tenho. Não cheguei a fazer medidas de taxa de compressão. Quem já tiver feito isso e quiser publicar aqui, fique à vontade!
Em resposta à Francisco Reverbel

Re: ep3: DIST maior que COMPR???

por Henrique Stagni -
Muito Obrigado pela resposta.

Vou concertar meu ep e ver se as taxas de compressão aumentam...
Em resposta à Francisco Reverbel

Re: ep3: DIST maior que COMPR???

por Rodrigo Cordeiro Godoy -

O professor disse:
Quanto ao arquivo de exemplo, eu não tenho. Não cheguei a fazer medidas de taxa de compressão. Quem já tiver feito isso e quiser publicar aqui, fique à vontade!

 

Então, se alguém já conseguiu comprimir e descomprimir arquivos com sucesso (devolvendo arquivos identicos ao original), coloque algum como exemplo aqui (comprimido e descomprimido) para outros compararem!

É só um pedido hehehe...

Em resposta à Rodrigo Cordeiro Godoy

Re: ep3: DIST maior que COMPR???

por Henrique Stagni -

Acho que meu ep não está fazendo a melhor compressão que deveria ser feita, mas aqui estão alguns resultados:

                  Comprimido Binario: http://www.linux.ime.usp.br/~hstagni/biblia.out

 

                   Taxa Compressão: 14.14%

                  Comprimido Binario: http://www.linux.ime.usp.br/~hstagni/const.out

 

                   Taxa Compressão: 6.18%

                  Comprimido Binario: http://www.linux.ime.usp.br/~hstagni/frank.out

 

                   Taxa Compressão: -0.01%(0.01% maior q o original)

Em resposta à Henrique Stagni

Re: ep3: DIST maior que COMPR???

por Alexandre Ouno Atoji -
Minhas taxas de compressao estão identicas as suas.
Acho que com esse algoritmo a taxa deve ser essa mesmo.

Mas com um texto com caracteres repetidos, eu consegui algo em torno de 93%