Página 1 de 1

[Java] Compresor

Publicado: 20 Jun 2014, 13:56
por overxfl0w13
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: [Enlace externo eliminado para invitados] , [Enlace externo eliminado para invitados]

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;
        
    }       
}
[Compresor.java]

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){}
    }
}
[RunLength.java]

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;
        }
    }

}
[Package Algoritmos]

[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;
    }
}
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 : [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".

Imagen


Un saludo :D

Re: [Java] Compresor

Publicado: 20 Jun 2014, 19:54
por adwind
:) Buena esa

Re: [Java] Compresor

Publicado: 20 Jun 2014, 20:33
por $DoC
No sabia que le dabas también a JAVA XD, bonito el code!

Gracias

Re: [Java] Compresor

Publicado: 20 Jun 2014, 21:13
por strup
MAQUINA
como te dije por skype funciona perfecto y el code perfecto, un saludo fiera

Re: [Java] Compresor

Publicado: 28 Jul 2014, 14:01
por Slek
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 http://indetectables.net/viewtopic.php?f=92&t=49843, 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!