Compressão de dados

Ter tem, é só procurar alguma implementação Java ou JNI de algum outro algoritmo, tal como o utilizado pelo BZIP2.

Mas em termos de compressão, qual é o melhor?

A resposta é “depende”. Por exemplo, se no seu caso você quer comprimir objetos serializados (é isso mesmo que você quer?), então qualquer algoritmo que faça compressão “sem perdas” é razoável, já que o tamanho dos objetos é relativamente pequeno.
O próprio algoritmo Deflate, do java.util.zip já é muito bom para isso.
Se o objeto tiver muitos bytes repetidos, você pode primeiro aplicar RLE, depois aplicar Deflate (experimente comprimir um arquivo de 10 MB somente com zeros binários usando apenas Deflate, para comprovar o que estou falando).
Talvez seja necessário usar algum outro recurso para diminuir um pouco o tamanho dos dados transmitidos via serialização, que acho que é o que você quer.
Por exemplo, se você conseguir juntar vários objetos e comprimi-los todos de uma vez, obterá uma compressão melhor que se comprimir um por um.
É como você comprimir arquivos usando .zip (cada arquivo é comprimido separadamente) ou usando .tar.gz (primeiro os arquivos são juntados, a seguir são comprimidos todos de uma vez). O algoritmo é exatamente o mesmo para os dois casos (Deflate), mas normalmente arquivos .tar.gz são um pouco menores. Isso é levado ao extremo pelo compressor 7-Zip (que basicamente tenta reordenar os arquivos de modo que arquivos parecidos fiquem juntos, para que a compressão seja a melhor possível).
Se você quer comprimir imagens com perdas, há diversos algoritmos (como os usados pelo JPEG); assim como sons com perdas (o famoso algoritmo MPEG usado no MP3), ou vídeos com perdas (MPEG-4, etc).

Bom, a minha idéia no geral é a seguinte, no projeto do trabalho teremos que gerar um código de barras no formato pdf417 que comporta até 2700 caracteres (aqui tem uma foto do código: http://pdf417.dlawas.com/przyklad2.gif. Então, nesse código de barras eu teria que passar uma chave pública, a assinatura digital e o arquivo assinado… Eu estava pensando em passar todos essas informações em um array de bytes grande, tendo cada informação separada por tokens, mas não estou conseguindo um resultado muito satisfatório, usando a compressão deflate… Ao passar um objeto a um array de bytes e depois comprimir esse array, ele passa de 950 pra 870 bytes (cada item do array), o arquivo é um documento xml, que até consegue uma boa compressão de 2300 passa pra 650 bytes e a assinatura possui 256 bytes e cada token possui 3 bytes… O problema eh que teria que eu estou passando para uma string hexadecimal e cada eu faça isso, irá dobrar o tamanho da saída… Sugestões do que fazer?

Bom, hexadecimal está fora de questão nesse caso (já que duplica o tamanho de seus dados). “Joga fora no lixo!”
Use uma codificação melhor.
Parece que dependendo do leitor ( http://www.bizfonts.com/pdf417/faq.html ) é possível até codificar 256 símbolos possíveis ( = 1 byte), ou seja, não seria preciso a conversão de dados.
Mas como 256 símbolos podem dar problemas, é melhor usar Base-64 (converte 3 bytes em 4 caracteres; usado normalmente em certificados digitais, como você já deve ter visto), ou Base-85 (converte 4 bytes para 5 caracteres; usado no Adobe Postscript para transmitir dados para algumas impressoras que não aceitam dados com 8 bits; você pode até encontrar alguns arquivos .PDF que são codificados dessa maneira.)
Base-64 tem pronto no http://jakarta.apache.org/commons , e Base-85 não é difícil de codificar também (fiz um em Javascript, que é meio complicado para trabalhar com bits ou fazer contas com números inteiros; em Java seria muito mais fácil).
E XML é realmente muito “gastão” - ainda bem que seu compressor está funcionando bem com os dados XML que você está lhe fornecendo.

bom, valeu por tudo ae, vou ver se utilizo o base64, espero que resolva os meus problemas ;), ah, poderias disponibilizar a fonte do base85 que tu fez?

Hum, quanto ao Base-85 não posso pôr o fonte aqui (aqueles famosos contratos de confidencialidade etc.)

Mas não é excessivamente difícil de fazer.

Basicamente para decodificar um dado que foi escrito em Base-85, é necessário quebrar o dado em conjuntos de 5 caracteres, então procurar cada caracter em uma tabela (‘A’ = 0, ‘B’ = 1 etc.), que retorna um número de 0 a 84. Deve-se então acumular os números (multiplicando o número anterior por 85 e adicionar o número obtido), até obter um inteiro que tem o comprimento de 4 bytes.

Para codificar, deve-se efetuar o processo inverso (ir dividindo por 85 e ir pegando o resto etc.)

mas uma coisa, com base64 o meu array de bytes quando encodado diminuiria de tamanho ao passa-lo pra uma string?

Quando convertemos um array de bytes para Base-64, cada 3 bytes são convertidos para 4 caracteres.

Quando convertemos uma string Base-64 para um array de bytes, cada 4 caracteres são convertidos para 3 bytes.

Então, no meu caso eu precisaria de uma string menor para enviar para o codigo de barras

entendi agora, realmente diminui, heheh valeu

uma coisa, haveria na internet alguma implementação do algoritmo bzip2 para o java? onde eu poderia encontrar um texto explicativo sobre base85?

Ué… quem sabe? Ahhh, mas se nós procurarmos no google descobriremos… Fui no google e procurei por: bzip2 java

http://www.google.com/search?hl=en&q=bzip2+java&btnG=Google+Search

Com uma rápida olhada nos resultados, tem um que pode ser interessante:

:arrow: bzip2 library from Apache Ant

Se esse não for interessante, basta dar uma outra olhada nos resultados!

po, valeu ae cara, mto obrigado msm

Uma coisa, pra comprimir arquivos xml, o q vocês recomendariam?

Bom, eu recomendaria não usar XML se você tem problemas com tamanho - mesmo compactado o XML ainda é muito gastão.
Mas se ambos os lados (cliente e servidor) sabem exatamente quais são os dados a serem trocados e a aplicação não precisa ser flexível, pode-se tentar algum método como “Fast Web Services” (procure no site da Sun o que é isso, nem sei se isso já está pronto para ser usado. Na verdade o nome é só um argumento de venda; a intenção do “Fast Web Services” é a recodificação do XML em uma codificação do ASN.1 chamada PER - não é indicado para estômagos mais sensíveis.)
No seu caso um método tradicional de compressão acho que já dá para o gasto. Só testar e ver.

O problema do meu projeto, eh que eu teria que por o conteudo do xml num código de barras, já tentei de tudo heh

Tudo é questão de reavaliar os requisitos quando não é possível implementá-los.
Por exemplo, se mesmo comprimindo o XML e codificando-o para Base-85 não é possível incluir no código de barras, pode-se ver se é possível eliminar a exigência de usar XML e usar em seu lugar um código separado por vírgulas, ou um código posicional (tal como os códigos usados em EDI).

Poderias me dizer um pouco mais sobre esse EDI?
A compressão até que é boa, de um arquivo de 2400 bytes passa pra uns 650, já tentei com várias, bzip2, gzip, zip e a ke obtive melhor resultado foi com a deflate

Cara, XML num codigo de barras foi novidade

Como eh esse XML? Que dados vc realmente tem que passar?

EDI = Electronic Data Interchange
Esse é um nome genérico para os protocolos usados para troca de dados antes que o XML fosse inventado. Esses protocolos são do tempo em que a gente usava só 2 dígitos para o ano, para não gastar espaço à toa, e que compressão de dados não existia. (A rigor existia sim - quem usou mainframes IBM há 20 anos atrás lembra-se do programa ‘hpack’ - , mas era patenteado e muito caro)
Exemplos de protocolos EDI: EDIFACT, etc.
Esses protocolos são muito chatos, descritivos e bitolados; muita gente ainda ganha direito fazendo “tradutores EDI” ou “EDI mappers” que são bibliotecas que convertem um formato EDI em outro.
No seu caso, só valeria a pena se um dos lados requer que os dados venham em formato padrão EDIFACT (por exemplo).
Só que EDIFACT e outros protocolos não efetuam compressão - a rigor, se você vir uma mensagem EDIFACT, não só não vai entender nada, como vai achar que tem algum espaço desperdiçado.
O equivalente desses protocolos EDI hoje em dia é o ebXML e o BizTalk.

Sem cair nos protocolos e formatos de dados da epoca do guarana com rolha de cortica, voce pode usar o bom e velho CSV caso seu documento nao precise de estrutura hierarquica, ou se a hierarquia for facil de “remontar” a partir de uma sequencia do tipo

Nome,Tel1,Tel2,Tel3 Carlos,5551234,5554321,5551324 Eduardo,5556789,5559876,5556879

Isso evita que vc sequer tenha que fazer mta compressao, pq vc ja desperdica pouco espaco em primeiro lugar. Passar um gzip num arquivo assim dexa ele ridiculamente pequeno… mas talvez nao tanto a ponto de caber num codigo de barras…

Quantos bytes voce pode gastar, no total?

Bom, eu estou pensando pelo menos no código de barras, fazer algo do tipo csv mesmo pra economizar espaço… Uma outra alternativa seria alterar o código de barras de pdf417 para supercode, que comporta mais caracteres, ao redor de 4000. Mas uma coisa que não estou entendendo, é que nas documentações do PDF417 que li, informa-se 2710 caracteres alfanuméricos máximos, porém, só consigo colocar bem menos que isso… O problema é que não há muita documentação do supercode pela internet, já o pdf417 já é mais padronizado. Ah, uma dúvida, tentei comprimir um arquivo pequeno, em torno de 10 bytes usando o algoritmo Deflater e acabou aumentando o tamanho do arquivo, assim como ocorreu quando eu tentei comprimir a assinatura digital do mesmo…

Bom, dados que não podem ser comprimidos com sucesso:

• Dados muito pequenos (como é o caso dos seus 10 bytes);

• Dados quase-aleatórios (como é o caso das assinaturas digitais, que aparentam ser dados “quase-aleatórios” - o nome técnico é “de alta entropia” - basta examinar o dump hexadecimal de uma assinatura para ver que há muitos lugares onde não é possivel enxergar seqüências repetidas ou previsíveis.)

• Se você tiver uma imagem escaneada mas não comprimida - por exemplo, um BMP ou um TIFF sem compressão - , também terá algo que ao ser examinado com um dump hexadecimal parece um pouco aleatório (ao tentar comprimir uma figura dessas usando zip você não vai obter uma boa taxa de compressão.) É necessário perder alguma informação (“lossy compression”) para poder comprimir uma imagem.

Agora, não estou conseguindo descomprimir, não sei o q está havendo…

Aqui está o código:

public class Compressao
{	
	public static byte[] comprime( byte[] bytes ) throws IOException
	{
		ByteArrayOutputStream baos = new ByteArrayOutputStream();
		DeflaterOutputStream dos = new DeflaterOutputStream( baos, new Deflater( Deflater.BEST_COMPRESSION ) );

		dos.write( bytes );
		dos.flush();
		dos.close();
		
		return baos.toByteArray();
	}
	
	public static byte[] decomprime( byte[] arrayComprimido ) throws DataFormatException
	{
		Inflater decompressor = new Inflater();
		decompressor.setInput( arrayComprimido );
		
		byte[] saida = new byte[4096];
		int tamanhoResultado = decompressor.inflate( saida );
		decompressor.end();
		
		byte[] byteFinal = new byte[tamanhoResultado];
		System.arraycopy( saida, 0, byteFinal, 0, tamanhoResultado );
	
		return byteFinal;
	}
}

Também já tentei usar InflaterInputStream, mas não consegui… Ocorre a seguinte exceção:

java.util.zip.DataFormatException: incorrect data check

at java.util.zip.Inflater.inflateBytes(Native Method)

at java.util.zip.Inflater.inflate(Unknown Source)

at java.util.zip.Inflater.inflate(Unknown Source)

at ecfv.util.Compressao.decomprime(Compressao.java:33)

at ecfv.cliente.Cliente$2.run(Cliente.java:561)

at java.lang.Thread.run(Unknown Source)

usando deflate, bzip2 ou qualquer outro método aritmético com um volume de dados tão pequeno (2400 bytes) vai ser MUITO dificil conseguir uma taxa de compressão superior a atual sem “roubar” e usar compressores especializados.

Existem algumas formas boas de “roubar” que vão melhorar a taxa de compressão e explodir o número de horas do teu projeto, via de regra você pode fazer as seguintes coisas (em ordem progressiva de dificuldade):

1)Pré-condicionar os seus dados para melhorar a compressão, isso envolve saber primeiro como funciona os algoritmos da classe lzw. Nessa etapa vão ser feitas transformações com dicionarios estáticos ou que diminua a entropia usada pelo modelo do lzw (translação, transformações afins, re-codificação, troca de base, etc)

2)Gerar algumas tabelas de símbolos do lwz que sejam as mais comuns pros teus dados, coloca elas como dados externos, modificar as classes de zip para o stream gerado incluir uma referencia para essas tabelas em vez delas e o compressor usar uma das tabelas.

3)Desistir de conseguir mais que o atual e rever os requisitos do projeto. Você pode calcular a entropia do XML gerado e provar matemáticamente pro teu chefe que você já está próximo demais do limite de compressão que é, científicamente possivel de provar, o menor.

Simples, né?

bom, eu sugeri ao meu chefe utilizarmos dois códigos de barras ao invés de apenas um, então um ficaria com a chave publica e a assinatura e o outro código de barras conteria o xml…

pro primeiro código eu criaria um grande array de bytes, tendo a chave separada da assinatura por um token de 3 bytes…, sendo a chave comprimida individualmente… blz, o token é criado, o problema eh que ele não consegue extrair os dados, no dump hexadecimal que eu fiz, está tudo correto…

Aqui vai o codigo…

public static byte[] criaArrayInformacoes( byte[][] conteudo )
	{					
		int tamanhoToken = ECFVClienteConstants.TOKEN.length;
		int[] tamanhoElementos = new int[ conteudo.length ];
		
		for ( int i = 0; i < conteudo.length; i++ )
			tamanhoElementos[i] = conteudo[i].length;
		
		int tamanhoTotal = 0;
		
		for ( int i = 0; i < tamanhoElementos.length; i++ )
			tamanhoTotal += tamanhoElementos[i];
		
		if ( !( tamanhoElementos.length == 1 ) )
			tamanhoTotal += tamanhoToken * ( tamanhoElementos.length - 1 );
		
		byte[] arrayTudo = new byte[ tamanhoTotal ];
		
		int indiceAtual = 0,
			indiceFinal = conteudo.length;
		
		for ( int i = 0; i < indiceFinal; i++ ) {
			System.arraycopy( conteudo[i], 0, arrayTudo, indiceAtual, tamanhoElementos[i] );
			indiceAtual += tamanhoElementos[i];
			
			if ( !( i == indiceFinal - 1 ) ) {
				System.arraycopy( ECFVClienteConstants.TOKEN, 0, arrayTudo, indiceAtual, tamanhoToken );
				indiceAtual += tamanhoToken;
			}
		}
		
		return arrayTudo;
	}
	
	public static byte[][] extraiInformacoes( byte[] array )
	{
		String str = new String( array );
		Pattern reg = Pattern.compile( new String( ECFVClienteConstants.TOKEN ) );
		String[] arrStr = reg.split( str );
		byte[][] b = new byte[ arrStr.length ][];
		
		for ( int i = 0; i < b.length; i++ )
			b[i] = arrStr[i].getBytes();
		
		return b;
	}

to há um tempao nisso e nao consegui resolver ainda…