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

sh4dyPT

BWT - Burrows Wheeler Transformation (Compressão de texto)

3 mensagens neste tópico

Boa noite.

Estou a desenvolver um algoritmo para Compressão e Descompressão de texto, seguindo umas regras para o fazer. Não sei se alguém está familiar com as técnicas de RLE e BWT.

Tenho umas dúvidas em relação a transformação inversa do BWT.

Deixo aqui o código, o Problema é que o processo é demasiado lento quando o texto é grande, deve ser da maneira como é feita a ordenação dos arrays. Portanto se alguém puder analisar e indicara-me as falhas agradecia imenso.

import java.util.Arrays;
public class Uncompress {

public static void main (String[] args){

	String inputSTR = "1T1E1X1Y1D1S1T1S1.1E1.1I1X1I1X1I2X2S1M2P1S1.1B2.2E1.1@1.1U1S1F1X1D2I1O3I1T";
	String invRLE = InvRLE(inputSTR);
	System.out.print(InvBWT(invRLE));
}

public static String InvBWT(String tmp){
	int z = 0, i = 0, f;
	String[] test = new String[tmp.length()];

	while (z < tmp.length()){
		if (z == 0){
			for (int j=0; j < tmp.length(); j++)
				test[j] = new String(Character.toString(tmp.charAt(j)));
			z++;
		}
		Arrays.sort(test);
		for (int j=0; j < tmp.length(); j++)
			test[j] = new String(Character.toString(tmp.charAt(j)) + test[j]);
		z++;
		if (z == 112)
			f = 0;
	}
	while (i < tmp.length()){
		if (test[i].charAt(tmp.length()-1) == '@')
			return test[i];
		i++;
	}
	return "Error";
}

public static String InvRLE (String tmp){
	int i = 0, j;
	String aux = new String();
	while (i < tmp.length()-1){
		j = 0;
		while(j < tmp.charAt(i) - '0'){
			aux += tmp.charAt(i+1);
			j++;
		}
		i = i + 2;
	}
	return aux;
}

}

com os melhores cumprimentos Sh4dyPT.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não tendo conhecimento dos algoritmos que estás a usar, posso indicar-te que métodos estáticos não serão a melhor escolha, mas o que pode estar a afectar mais será a ordenação e a criação de tantas instâncias de String. Em Java criar Strings é algo lento, que consome alguns recursos, se conseguires substituir essas instanciações todas pelo uso de StringBuffers seria melhor.

Quanto à ordenação, não sei que tipo de ordenação precisas, é apenas a ordenação natural das strings?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Em termos de ordenação só preciso de constantemente ordenar a string alfabeticament. Em relação ao StringBuffers, nunca trabalhei com isso, mas vou dar uma olha dela na net.

Obrigado

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