• [Java] Compresor

 #446184  por overxfl0w13
 20 Jun 2014, 13:56
Bueno nunca había tocado nada de compresores y me apeteció escribir algo relacionado. Me interesó la compresión de Burrows-Wheeler (más bien transformación) y las ventajas que nos ofrece para la posterior aplicación de sencillos algoritmos de compresión tipo Run-Length. Si queréis saber más os dejo links a la wikipedia: [ Debe registrarse para ver este enlace ] , [ Debe registrarse para ver este enlace ]

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: [ Debe registrarse para ver este enlace ]
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;
        
    }       
}
[Compresor.java]
Código: [ Debe registrarse para ver este enlace ]
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){}
    }
}
[RunLength.java]
Código: [ Debe registrarse para ver este enlace ]
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;
        }
    }

}
[Package Algoritmos]

[MergeSort.java]
Código: [ Debe registrarse para ver este enlace ]
  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;
    }
}
Se usa MergeSort para evitar costes O(n^2) en los peores casos (además está tocado para evitar la doble copia del array), aunque el QuickSort que usa java para implementar Array.sort() está modificado para evitar algunos peores casos, siguen apareciendo en ocasiones y hay que evitarlos en burrows-wheeler.

Link .jar : [ Debe registrarse para ver este enlace ]

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
 #446227  por $DoC
 20 Jun 2014, 20:33
No sabia que le dabas también a JAVA XD, bonito el code!

Gracias
 #446230  por strup
 20 Jun 2014, 21:13
MAQUINA
como te dije por skype funciona perfecto y el code perfecto, un saludo fiera
 #450761  por Slek
 28 Jul 2014, 14:01
Buen código!
Un par de cosas a resaltar:
Considera el uso de una lista enlazada en lugar de array (para solucionar el problema de eof)
Héchale un ojo a [ Debe registrarse para ver este enlace ], para un número alto de elementos (del orden de 1 000 000 elementos) esta variante es más rápida.
Y para copiar un array a otro, es mucho mejor utilizar System.arraycopy();

Un saludo!