Muy por encima, burrows-wheeler nos reordena las cadenas y tiende a agrupar todas las letras repetidas debido al proceso de rotación, gracias a esto, la tasa de aciertos del run-length (bloques que consigue agrupar) es bastante mayor. De todas formas sigue siendo inefectivo si el texto que se quiere cifrar no tiene repeticiones de palabras o conjuntos de letras iguales. También hay algunos problemas porque java ordena "lexicográficamente" según el código ascii y ese no es el orden que se requiere, además de problemas con el eof, si se quiere explotar el código hay que tocar un par de cosas. Dejo código para test y el .jar.
[Package Compresor]
[BurrowsWheeler.java]
Código: Seleccionar todo
package Compresor;
import Algoritmos.MergeSort;
public class BurrowsWheeler
{
private char eof;
public String bwTransform(char[] txt){
this.eof = txt[txt.length-1];
String spinneds[] = new String[txt.length];
char first;
spinneds[0] = new String(txt);
// Rotate
for(int i=1;i<txt.length;i++){
first = txt[0];
for(int j=0;j<txt.length-1;j++) txt[j] = txt[j+1];
txt[txt.length-1] = first;
spinneds[i] = new String(txt);
}
// Sort
MergeSort.mergeSort(spinneds);
// Complete
String res = "";
for(String spin : spinneds) res += spin.charAt(spin.length()-1);
return res;
}
public String bwTransformInv(String txt){
String[] fullTable = new String[txt.length()];
// Init fullTable
for(int i=0;i<txt.length();i++){
fullTable[i] = "";
fullTable[i] = fullTable[i]+txt.charAt(i);
}
// Process
for(int i=1;i<txt.length();i++){
MergeSort.mergeSort(fullTable);
for(int j=0;j<txt.length();j++) fullTable[j] = txt.toCharArray()[j] + fullTable[j];
}
// Take Correct
String msg = "There was an error, warn it";
for(String e : fullTable) if(e.charAt(txt.length()-1)==eof) msg = e;
return msg;
}
}
Código: Seleccionar todo
package Compresor;
import Compresor.RunLength;
import Compresor.BurrowsWheeler;
import java.io.IOException;
import java.util.Scanner; // Para tests
public class Compresor
{
public static void main(String args[]){
System.out.print("\nText: ");
BurrowsWheeler bw = new BurrowsWheeler();
Scanner scn = new Scanner(System.in);
String text = scn.nextLine();// Decompressed
String cmp = ""; // Compressed
String unc = ""; // Decompressed
try{
// Compress
cmp = bw.bwTransform(text.toCharArray());
System.out.println("\nBurrowsWheelered: " + cmp);
cmp = RunLength.compress(cmp,"compress.zpo");
System.out.println("\nCompressed: " + cmp);
// Decompress
unc = bw.bwTransformInv(RunLength.decompress("compress.zpo"));
System.out.println("\nDecompressed: " + unc);
}catch(IOException e){}
}
}
Código: Seleccionar todo
package Compresor;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
public class RunLength
{
public static String compress(String txt,String dname) throws IOException {
String res = "";
int count = 0;
FileOutputStream fos = new FileOutputStream(dname);
DataOutputStream dos = new DataOutputStream(fos);
try{
for(int i=0;i<txt.length();i++){
for(int j=i+1;j<txt.length();j++)
{
if(txt.charAt(i)==txt.charAt(j)) count++;
else break;
}
if(count==0){
dos.writeInt(1);
dos.writeChar(txt.charAt(i));
res += "1" + txt.charAt(i);
}
else{
dos.writeInt(count+1);
dos.writeChar(txt.charAt(i));
res += String.valueOf((count+1)) + txt.charAt(i);
i += count;
}
count = 0;
}
}catch(IOException e){}
finally{
dos.close();
fos.close();
return res;
}
}
public static String decompress(String fname) throws IOException {
FileInputStream fos = new FileInputStream(fname);
DataInputStream dos = new DataInputStream(fos);
String res = "";
int numRep = 1;
char actChr;
try{
while(true){
numRep = dos.readInt();
actChr = dos.readChar();
for(int i=0;i<numRep;i++) res += actChr;
}
}catch(IOException e){}
finally{
dos.close();
fos.close();
return res;
}
}
}
[MergeSort.java]
Código: Seleccionar todo
package Algoritmos;
public class MergeSort{
/* MergeSort */
public static <T extends Comparable<T>> void mergeSort(T[] v) {
T[] aux = mergeSort(v, 0, v.length - 1);
// Se copia el array resultante en el original //
for (int i = 0; i < v.length; i++) v[i] = aux[i];
}
/* PRECONDICION: i<=f */
@SuppressWarnings("unchecked")
private static <T extends Comparable<T>> T[] mergeSort(T[] v, int i, int f) {
T[] res;
if (i+1 >= f){
if(i==f){
res = (T[]) new Comparable[1];
res[0]=v[i];
}
else{
res = (T[]) new Comparable[2];
if(v[i].compareTo(v[f]) < 0){
res[0]=v[i];
res[1]=v[f];
}else{
res[0]=v[f];
res[1]=v[i];
}
}
}else { // if (i < f)
int m = (i + f) / 2;
T[] v1 = mergeSort(v, i, m);
T[] v2 = mergeSort(v, m + 1, f);
res = merge(v1, v2);
}
return res;
}
// Mezcla
@SuppressWarnings("unchecked")
private static <T extends Comparable<T>> T[] merge(T[] v1, T[] v2) {
int contv1 = 0;
int contv2 = 0;
int k = 0;
T[] res = (T[]) new Comparable[v1.length + v2.length];
while (contv1<v1.length && contv2<v2.length){
if (v1[contv1].compareTo(v2[contv2]) < 0){
res[k] = v1[contv1]; contv1++;
}else {
res[k] = v2[contv2]; contv2++;
}
k++;
}
while (contv1<v1.length) {res[k] = v1[contv1]; contv1++; k++;}
while (contv2<v2.length) {res[k] = v2[contv2]; contv2++; k++;}
return res;
}
}
Link .jar : [Enlace externo eliminado para invitados]
Veréis que da algunos problemas con algunos textos, es normal por lo que he comentado antes, pongo imagen de test "apañado".
Un saludo :D