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

Tsunamy_boy

Descobri um método de compressão minimamente interessante

27 mensagens neste tópico

Após esturrar os miolos a ver como seria a melhor maneira de comprimir ficheiros, cheguei a uma "brilhante conclusão" (acho).

Comecei a pensar em limpar a redondancia em caracteres, mas vi que o resultado seria muito ruim ou nulo, caso o ficheiro se tratasse de um ficheiro escrito por alguem, pois comprimir ss e rr apenas, não seria o melhor método.

Aprendi aqui que os ficheiros são guardados de 8 em 8 bits e são lidos da mesma maneira pela maquina(tinha umas luzes disto apenas), e cada 8 bits têm uma correspondência na tabela ASCII (http://www.ascii-code.com/) que vão corresponder a um carácter, dai ouvirmos dizer que cada carácter corresponde a 8 bits (e blá blá blá).

(este foi o meu processo de raciocínio)

Após verificar isto (que veio dos meus registos):

Onde o binário é cheio:
decimal - binário

1   - 00000001
3   - 00000011
7   - 00000111
15  - 00001111
31  - 00011111
63  - 00111111
127 - 01111111
255 - 11111111

Reparei que o binário é cheio de 1's, usando esta formula:

(anterior * 2) + 1

dai: o 31 resultar do (15*2)+1

ou formula directa (o que aqui não interessa)

2^(posição) - 1 >> para encontrar logo a posição decimal

Como vêm todos resultam do dobro dos anteriores + 1(o próprio)

Então eu cheguei a esta conclusão:

Se eu em vez de ler de 8 em 8 bits, ler de 9 em 9?

Se repararem bem, 9 vai ser igual ao anterior*2 +1, conclusão: vou ter o dobro de 8bits (anteriores) e ainda me sobra 1 caracter no final.

Tendo o doblo de 8 bits é como unir 2caracteres(ou 2Bytes).

Conclusão: Eu com 9bits em vez de os 8(usados actualmente) posso unir 2bytes sem problema, compactando quase a metade o ficheiro, deixando de ter 16bits(2 bytes) e passando a ter 9bits(a junção desses 2).

Como podem concluir:

com 9 bits eu consigo ir até ao decimal 511(ou na posição 511 da tabela ASCII)

com 8 bits consigo ir até ao decimal 255 (actuais na tabela ASCII).

Se somar 255 + 255 (que corresponde á união de 2 bytes quaisquer) da-me 510 e ainda me sobra 1 caracter dos 511 que me deu anteriormente(que me vai ser util).

O problema é:

Só consigo concatenar apelas 2 caracteres diferentes, pois estou a somar 255+255 e não a multiplicar, pois caso multiplicasse acharia todas as opções possíveis de unir 2bytes que dá o total de 65025 opções (o que é um numero gigantesco  :thumbdown:)

A solução

Caso os meus caracteres sejam os dois iguais, separo-os com o meu caracter especial(que me sobra) ex:

Sopondo que o meu caracter especial será o $, e acontecesse o caso de AA(2 caracteres iguais), ficaria:

$A

No caso de AAAA:

$A$A - pois caso tenham reparado estou a ler de 2 em 2 caracteres e junta-los, como reparo que $ é o meu caracter especial apenas dobro o valor a frente.

No caso de o numero de bytes não ser múltiplo de dois(ou seja, no final em vez de ter 2caracteres passo a ter um) ponho na mesma o caracter e junto um $ no fim, assim é a minha maneira de dizer que me sobrou um caracter no fim, ex:

suponhamos: AAA, ficava:

$AA$  (AA+A)

Agora eu pergunto: o meu raciocínio está correcto?

Quando fizer a minha tabela ASCII posto aqui para perceberem melhor.

;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Impossível.

Existe um número infinito de pares (a,;) tal que a+b = c

Ou seja, não consegues comprimir 2 bytes em 9 bits.

Se esse teu raciocínio fosse válido, podias comprimir os grupos de 9 bites em grupos de 10 e por aí fora, e terias um ficheiro com tamanho perto de 0. (log N bits, tal que N seria o número de bits do ficheiro).

E eu acho que já te expliquei isto noutro tópico. Aliás, nem sei para que criaste outro.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

não vi o outro.

Existe um número infinito de pares (a,;) tal que a+b = c

explica melhor

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Tendo o doblo de 8 bits é como unir 2caracteres(ou 2Bytes).

Conclusão: Eu com 9bits em vez de os 8(usados actualmente) posso unir 2bytes sem problema, compactando quase a metade o ficheiro, deixando de ter 16bits(2 bytes) e passando a ter 9bits(a junção desses 2).

O teu raciocínio falha aqui.

Tu com 9 bits não sabes que par de 8 bits lhe deu origem.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu nao percebi nada do método de compressão. Se a tentativa é encontrar um código binário que represente texto de forma mais económica que um código de comprimento fixo, isso é possivel. Mas há metodos bem desenvolvidos para isso.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

tenho, lembras-te que o meu metodo cria uma tabela ASCII com 511 opções distintas, cada opção é a junção de 2caracteres.

Ex:

(junção de dois caracteres) - posição ASCII

AB - 1

BA - 2

BC - 3

...

Não existe é a junção de 2 iguais como expliquei antes

só mostrando mesmo a tabela ascii podes perceber.

quando tiver tempo faço um FOR e crio isso.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

tenho, lembras-te que o meu metodo cria uma tabela ASCII com 511 opções distintas, cada opção é a junção de 2caracteres.

Não sabia que tinhas criado uma nova American Standard Code for Information Interchange ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não sabia que tinhas criado uma nova American Standard Code for Information Interchange ;)

Coitado do moço, até parece que nunca disseste nenhuma bacorada. :)

Já agora Tsunamy_boy, podes é dizer algo nas linhas de charset (embora não o seja).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podes fazer isso se só quiseres comprimir texto, e portanto descartares o resto dos códigos.

Se fosse a ti parava de tentar inventar o impossível. Tenta perceber que existe muita gente com mais conhecimentos que tu a fazer compressão, e se isso fosse assim tão simples..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Estava enganado sim, após ter feito melhor os cálculos descobri que os 511são as opções possíveis se repetir o carácter, assim como: AA BB CC e os 65025são todas as opções possíveis que se podem fazer com2caracteres.

Quanto a tabela ascii era com base no raciocínio apenas,eu sei que s existe uma...

Bem tenho que começar do 0novamente...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu tenho a opinião do Warrior e de outros que já postaram nos teus tópicos sobre compressão: lê sobre compressão aí pelas internets e só depois tenta fazer o que estás a tentar fazer.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tenho a mesma opinião do pedrotuga: estuda teoria da informação!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não sei talvez seja melhor ter a cabeça limpa de idéias de compressão para não ficar mais confuso.caso veja que não consigo aí sim vou estudar isso a fundo(que e o mais provável pois acredito que isto e complexo)

obrigado a todos.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Existem montes de algoritmos de compressão como huffman, huffman adaptative, lz77, lz78 e sei lá que mais pk inventar 1 ?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se se pensasse assim tinham ficado pelo primeiro que apareceu.

E não se criavam mais coisas porque já o tinham feito antes e não havia evolução. Eu não digo que venha a criar o maior método de compressão do mundo mas se tirar 2bytes já fico contente:)

também é mais pela desportiva e a intenção de aprender mais umas coisas pois eu até gosto disto...cumps

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Então começa por estudar os existentes e depois então tenta adaptar de uma forma melhor.

Estes algoritmos também não são os melhores mas deram origens a muitos outros utilizados ainda hoje, são algoritmos que levam N tempo a desenvolver e se a ideia é aprender nada melhor do que aprender com algo que já existe e tá bem feito. ;)

Não estou a criticar estou apenas a tentar mostrar que inventar do nada nem sempre é o melhor cominho.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

[quote name='Warrior' timestamp='1208800819' post='180403']
Impossível.
Existe um número infinito de pares (a,b) tal que a+b = c

Agora percebi o que querias dizer, eu não me referia a somar dois bytes mas sim a dar-lhes um novo índice, a criar uma tabela com 2caracteres e indexa-los.

mas isso não funka e não vejo solução em mais nada.

Então começa por estudar os existentes e depois então tenta adaptar de uma forma melhor.

Estes algoritmos também não são os melhores mas deram origens a muitos outros utilizados ainda hoje, são algoritmos que levam N tempo a desenvolver e se a ideia é aprender nada melhor do que aprender com algo que já existe e tá bem feito. :)

Não estou a criticar estou apenas a tentar mostrar que inventar do nada nem sempre é o melhor cominho.

Vou-me agarrar a wikipedia e ao google.... é uma solução fiável

não conheces bons sites (de preferencia em portugues para não torrar mais os miolos com traduções) que falem disto?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

tenho outro metodo:

Na posição 31 da tabela ASCII o binário é preenchido com 1's no máximo de 5bits (00011111).

Fazendo com que o numero 31 use apenas 5 Bits, dai:

Se eu dividir a tabela ASCII em 16 tabelas (sendo a segunda a continuação da primeira e continuamente)

cada tabela vai ter 16 simbolos que vai dar os 256 simbolos existentes na tebala ASCII:

256(simbolos)=16(tabelas)*16(simbolos)

Depois é eliminar a redondancia, e esta vai ser eliminada usando:

-5bits para dizer qual a tabela.

-5bits para dizer qual a posição desse símbolo na tabela.

-5bits para tirar a redondancia (até 31 repetições)

ex:

Imagiem o caracter A, este está na posição 65 da tabela ASCII, esta dividida, o caracter A fica na 5º tabela, na posição 0.

Agora imaginem isto:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

Logo eu vou traduzir isto assim:

(posição na tabela)(posição do caracter)(vezes que se repete), logo:

00101 00000 11111

de binário para decimal ficaria:

5 - 0 - 31

ficando com 15bits de 248

Que me dizem?

---editado----

Melhor imaginem:

AAAAAAAAAAAAAAA

Não divido a tabela e passo a dizer que 15(1111) vão ser as vezes que se repete, dai:

(Posição da tabela ASCII sem divisões) (vezes que se repete)

01000001 1111

passando de 120bits para 12.

assim fica melhor visto que é mais provável haver mais repetições até 15 caracteres do que ate 31.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não precisas de 10 bits para representar um caracter, 8 chegam. (estou a falar dos dois primeiros grupos), isto porque podes representar 16 números com 4 bits, não precisas de 5.

O que tu pretendes fazer é basicamente um RLE, algo que já te foi explicado e que acho que tu até testaste uns tópicos atrás.

Na altura chegaste à conclusão que não valia a pena por ser um método que só funcionava em sequências que houvesse muitas repetições seguidas, caso contrário ainda ficas com um ficheiro maior.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

pois eu parti para e eliminação de sequências visto não avistar mais nada.

Mas a ideia de eliminar sequências não está desfuncional, visto que se quisesses representar a eliminação da sequência

AAAAAAAAAAAAAAA - ficavas com 15A que são 24bits e eu fazia isso por metade como ves acima na minha mensagem depois de editada

editado

o problema era caso fossem 16, ficaria:

01000001 1111 (já fiz os 15) + 01000001 0000 (o outro A que faltava)

A ideia é representar em 8bits o caracter e em 4bits as vezes que se repete

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas aí ias gastar 1,5 bytes/caracter... A menos que existam muitas repetições não ganhas nada com isso.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não.no caso de não valer a pena a compressão de certo texto existe uma maneira dizer que aquele texto não foi comprimido e que se vai manter(como já li) agora tenho e que arranjar maneira talvez guarde 1111 para dizer o começo e fim de onde não foi comprimido só que deixo de poder juntar 15caracteres e passo só a podes juntar 14.

Pelo menos este método ganha 1,5caracteres por junção coisa que não tinha visto antes quando li.caso eu queira escrever 15A o meu método e mais eficaz só que não existe nada para além do 15, 15e o máximo que se pode juntar e como vou usar o 1111 fico só a pedr usar a junção de 14 mas também duvido que exista muita repetição para além de 14caracteres

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

começa por ver o algoritmo de huffman

o conceito é simples, contas as ocorrências de símbolos de 8 bits e os de maior ocorrência são codificados com menos bits e por aí fora, depois está tudo organizado por uma arvore binária e reconstróis na boa o ficheiro de entrada através dela. lê para saber os pormenores sórdidos :)

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