Estou implementando um algoritmo de compactação LZW, como ele é um merodo baseado em dicionario, preciso preciso criar um dicionário de dados que ira conter uma string e inteiro, mais ou menos assim:
String | Código
A 65
B 66
. .
. .
. .
AB 256
. .
Estou usando um Vector para armazenar essa estrutura, mas como o algoritimo realiza "muitas’ operações envolvendo esta tabela (adiçao , consultas) ele esta sendo muito ‘lento’, justamente por causa dessas operações. Entao se alguem tiver alguma sugestão de alguma outra forma de implementar este dicionario (usando outro tipo de dado ou qualquer outra sugestão ) agradeço.
Uma maneira “ingênua” de implementar esse dicionário é usar o que existe pronto - o java.util.HashMap.
No seu caso em particular existem algumas outras maneiras que gastam menos memória para o dicionário, mas se você está implementando o LZW como um trabalho de escola, use o HashMap mesmo.
entao thingol, o lzw é so uma pequena parte do meu trabalho. tenho q construir um codec de video para gravar o desktop, explicando melhor, estou capturando ‘print screens’ do desktop (todo ou de uma determinada regiao) e preciso compactar essa imagem usando o algoritmo LZW ( tenho que compactar com este metodo, é exigencia do professor). tenho tudo implementado já o problema é desempenho, preciso ‘gravar’ ao menos 10 frames por segundo, ou seja, compactar 10 imagens em 1s usando o F… do Lzw e com a minha implementação atual isso esta impossivel, este é o real motivo deu vir pedir ajuda hehe, preciso fazer ele ser rápido
[quote=ragonzato]entao thingol, o lzw é so uma pequena parte do meu trabalho. tenho q construir um codec de video para gravar o desktop, explicando melhor, estou capturando ‘print screens’ do desktop (todo ou de uma determinada regiao) e preciso compactar essa imagem usando o algoritmo LZW ( tenho que compactar com este metodo, é exigencia do professor). tenho tudo implementado já o problema é desempenho, preciso ‘gravar’ ao menos 10 frames por segundo, ou seja, compactar 10 imagens em 1s usando o F… do Lzw e com a minha implementação atual isso esta impossivel, este é o real motivo deu vir pedir ajuda hehe, preciso fazer ele ser rápido
abs[/quote]
Hum… seu professor não aceita o fato que o ZLIB (pronto no Java) usa um algoritmo semelhante ao LZW?
LZ77 -> DEFLATE (usado no ZLIB)
LZ77 -> LZ78 -> LZW (que é o que seu professor quer)
No seu caso em particular, você não tem strings e sim arrays de bytes (cuidado - isso é MUITO relevante; você vai ter problemas infernais, e põe infernais nisso, se ficar desconsiderando essa diferença.) Pelamordedeus, não use strings, já que sua tela é um array gigante de bytes. É que ao converter bytes para strings, você acaba tendo erros, já que alguns bytes são convertidos para o mesmo caracter “?” e você percebe que a conversão não tem volta - ou seja, a string não consegue retornar o array de bytes original.
Você pode usar um hashmap mesmo, mas tem de criar uma função de hash especial para um array de bytes.
Provavelmente você terá de fazer o seguinte: crie um objeto que guarda uma referência para o início (offset) e o comprimento dos dados que você deseja armazenar nesse dicionário. Esse objeto é que é posto no hashmap.
byte[] buffer = ...; // alocado e lido
class ByteString {
public ByteString (byte[] buf, int offset, int length) {
this.buf = buf; this.offset = offset; this.length = length;
}
public byte[] buf;
public int offset;
public int length;
public int hashCode() {
int hash = 0;
for (int i = 0; i < length; ++i) {
hash = hash * 37 + buf[i];
}
return hash;
}
// complete esta classe com mais métodos desejados.
}
...
Map <ByteString, Integer> dicionario = new HashMap <ByteString, Integer>();
2 - Converto pixel a pixel da imagem do tipo RGB do java para um tipo RGB meu.
RGB[][] frame = new RGB[screenSize.width][screenSize.height];
for (int i = 0; i < screenSize.getWidth(); i++) {
for (int j = 0; j < screenSize.getHeight(); j++) {
RGB rgb = new RGB();
int pixel = bufferedImage.getRGB(i, j);
rgb.setRed((pixel >> 16) & 0xFF);
rgb.setGreen((pixel >> 8) & 0xFF);
rgb.setBlue((pixel >> 0) & 0xFF);
frame[i][j] = rgb;
}
}
A conversão embora implique em um certo ‘gasto’ computacional, é necessaria uma vez que mais a frente eu trabalho com os valores R G B separadamente e o Java me disponibiliza eles ‘agrupado’ em 1 inteiro.
3 - Compacto usando lzw ( aqui onde esta o ‘gargalo’ no desempenho)
public Vector compressao(RGB[][] entrada) {
String K = new String();
tabela = new Tabela();
tabela.init();
Vector Saida = new Vector();
int index = 0;
StringAtual = new String();
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
// red
K = new String();
K += (char) entrada[i][j].getRed();
StringAtual = new String();
StringAtual = PrefixoAtual + K;
if (tabela.StringOnTable(StringAtual)) {
PrefixoAtual = new String();
PrefixoAtual = StringAtual;
} else {
tabela.add(StringAtual);
Saida.add(tabela.getCod(PrefixoAtual));
PrefixoAtual = new String();
PrefixoAtual += K;
}
// green
K = new String();
K += (char) entrada[i][j].getGreen();
StringAtual = new String();
StringAtual = PrefixoAtual + K;
if (tabela.StringOnTable(StringAtual)) {
PrefixoAtual = new String();
PrefixoAtual = StringAtual;
} else {
tabela.add(StringAtual);
Saida.add(tabela.getCod(PrefixoAtual));
PrefixoAtual = new String();
PrefixoAtual += K;
}
// Blue
K = new String();
K += (char) entrada[i][j].getBlue();
StringAtual = new String();
StringAtual = PrefixoAtual + K;
if (tabela.StringOnTable(StringAtual)) {
PrefixoAtual = new String();
PrefixoAtual = StringAtual;
} else {
tabela.add(StringAtual);
Saida.add(tabela.getCod(PrefixoAtual));
PrefixoAtual = new String();
PrefixoAtual += K;
}
}
}
Saida.add(tabela.getCod(PrefixoAtual));
return Saida;
}
Quanto a este algoritmo similar ao lzw que já existe em java eu nao o conheço, vou ler mais sobre ele e conversar com meu professor, mas duvido que ele aceite usar. Até pq ele não gosta nem 1 poco de java, é fã de C.
# K = new String();
# K += (char) entrada[i][j].getGreen();
Aimeudeus, não faça isso (criar uma String e usar o operador “+=”. Isso é absurdamente lento em Java. Não faça isso. Por favor, não faça nunca isso. Não é à toa que seu professor não é fã de Java, porque ele viu que tais coisas são lentas mesmo.
Nunca guarde bytes em Strings. Crie uma classe, mas não faça nunca isso. Se você conseguir codificar 1 tela por segundo, está bom.
No meu caso eu estou tratando de cada ‘valor r g b’ individualmente, tentando explica melhor, por exemplo o 1 dado a ser processado (compactado) é o valor red do 1 pixel, como ele varia entre 0 a 255 eu posso fazer um cast pra char e trabalhar ele como sendo um char (palavras do meu professor), em seguida processo o o green do 1 pixel e assim sussessivamente.
Posso estar fazendo confusão, mas teoricamente o lzw nao limita a tabela, assim ‘teoricamente’ ele aceita qualquer tamanho de entrada na tabela. entao ao menos que eu ‘limite’ o tamanho das ‘entradas’ da tabela eu nao poderia usar hashmap. seria isso?
Embora isso nao seja algo ruim pelos ultimos testes que fiz e algums materias que achei na net, oque ‘mata’ o desempenho do lzw e o crescimento ilimitado da tabela.
1 char no Java ocupa 2 BYTES. Isso quer dizer que você está gastando espaço à toa, além de deixar seu programa mais lento.
(NO JAVA, estou falando NO JAVA; seu professor sabe C/C++, onde um char é 1 byte. Portanto, evite usar char para representar bytes. Por favor).
Pode usar hashmap sem problemas, já que ele aumenta dinamicamente. (Obviamente, quando for necessário realocar o hashmap, um processo que ocorre automaticamente, todos os hashes dos objetos incluídos no hashmap deverão ser recalculados, mas isso é um preço a pagar pela velocidade de alocação e acesso).
De qualquer maneira, nos algoritmos práticos, normalmente você não trabalha com buffers de tamanhos indefinidos, até para poder reduzir o impacto de você ter um dicionário muito grande. Raramente os buffers passam de 1 MB. No seu caso, onde você vai efetuar snapshots da tela (1280 x 1024), você dificilmente terá mais de 1280Kbytes de dados sendo processados ao mesmo tempo.
Dica: como telas costumam ter pouquíssimos pixels diferentes entre um snapshot e outro, acho que é interessante você ter um esquema semelhante ao seguinte: guarde sempre a tela anterior. Ao efetuar a compressão, em vez de comprimir a tela atual, comprima a diferença entre a tela anterior e a tela atual (por diferença eu quero dizer XOR). Como você deve saber, o XOR de um byte com ele mesmo é o byte 0. Você vai ver que a compressão será muito boa, porque você irá comprimir sequências repetidas de zeros. Seu professor não comentou nada sobre RLE? Eu recomendaria, nesse caso, efetuar uma primeira compressão com RLE e uma segunda com LZW.
Dica: estude a classe java.lang.StringBuilder. Uma vez entendendo para que serve essa classe, crie uma classe ByteBuffer que seja parecida com essa classe, já que você insiste em pensar em sequências de bytes como sendo strings. Isso pode até funcionar em C++ (onde std::string é um array “contado” de bytes), mas não em Java (onde java.lang.String é um tipo “imutável” e por baixo dos panos tem um array “contado” de shorts, aham, de chars - um char, no Java, é um “unsigned short”).
Eu esqueci de comentar, mas na descrição do trabalho ja esta pedindo pra realizar subtração de imagens, ou seja, subtrair o frame atual do anterior , compactar e armazenar a diefrença. mas como o desempenho ja pra armazenar o 1 (que deve ser armazenado integralmente) esta sofrivel nem cheguei nessa parte.
Quanto ao RLE ele nao comentou nada eu nem siquer sabia q existia.
Agora uma grande duvida, se eu nao fizer aquela parte de converter um byte pra um char e talz… desculpe minha ignorancia mas como irrei montar meu dicionario?
em C existe o tipo unsigned char que varia de 0 a 255, seria perfeito já em java nao conheço um tipo correspondente. já que o tipo byte se nao me engano é de -127 a 128
alguma sugestao? e muito obrigado pela ajuda.
a) Você continua a usar o tipo byte do Java, apesar de ele ter um intervalo de valores diferente, até porque você só vai precisar dele para armazenar seus dados, não para fazer alguma manipulação aritmética. Se o byte 0xFF do C é representado como -1 em decimal no Java, isso não tem problema para armazenar as coisas.
b) Estude o tipo StringBuilder e sua relação com o tipo String. Depois disso, pense em criar uma classe ByteBuffer que armazene bytes. OK?
Vo posta abaixo o pseudo-código do lzw, talvez ajude.
1. No início o dicionário contém todas as raízes possíveis e I é vazio;
2. c <= próximo caractere da sequência de entrada;
3. A string I+c existe no dicionário?
a. se sim,
i. I <= I+c;
b. se não,
i. coloque a palavra código correspondente a I na sequência codificada;
ii. adicione a string I+c ao dicionário;
iii. I <= c;
4. Existem mais caracteres na sequência de entrada ?
a. se sim,
i. volte ao passo 2;
b. se não,
ii. coloque a palavra código correspondente a I na sequência codificada;
iii. FIM.
Eu estava utilizando strings porque a priorí parecia se encaixar bem ao algoritmo, mas a partir do momento que percebi que nao estava obtendo o desempenho desejado, começei a procurar opçoes. Como não sou um grande conhecedor de java (conheço muito pouco) resolvi postar neste forun em busca de ajuda para sanar este problema.
Cara acho eu finalmente entendi oque vc queria diser, não tem porque eu converter byte em char, vou analisar byte a byte e armazenar array de byte na tabela. tava viajando…
Se você leu meu código acima (que já dá uma função de hash),
a) Uma função de hash apropriada para seu caso é a que postei,
b) Não é preciso que uma função de hash nunca repita valores (isso se prova que não é possível, pelo princípio da contagem). Basta que efetue um bom espalhamento.
