Huffman Codierung

[JonnyF]

Hallo !

Ich würde mich freuen wenn mir jemand helfen könnte.

seit 2 Tagen versuche ich jetzt einen Huffman code zu basteln der mir einen byte array mit der Huffman codierung codiert. Ich konnte im web dazu nur eine Huffman codierung/dekodierung finden der mit einem String arbeitet. Jedoch möchte ich Dateien einlesen, diese codieren, dann die codierten Daten samt dem Baum serialisieren und abspeichern. Folglich dann wieder das einlesen der serialisierten Daten, und das dekodieren.

Ich habe versucht den Huffman code der mit Strings als Eingabe arbeitet so umzuschreiben, das er mit byte Arrays zurecht kommt, das klappt aber von vorne bis hinten nicht.

hat vielleicht jemand noch irgendwo einen Huffman code zur codierung/decodierung (byte arrays) rumliegen ?

 

[PyroPi]

Ich wäre euch sehr dankbar für eure Hilfe da ich morgen meine Arbeit vorstellen muss :/

Am Samstag!? Dann wird das ja noch ne lange Nacht ...

Also wenn du eine Implementierung hast, die einen String codieren kann, sollte doch eine Codierung von Byte-Arrays kein großes Problem darstellen. Die Häufigkeitsberechnung führst du halt über Bytes, nicht über Chars aus, und bei der Codierung brauchst du auch nur die Typen auszutauschen.

Poste doch mal ein bißchen Code, wo genau das Problem liegt.

 

[JonnyF]

ok also Schnippsel werden wenig bringen, auch meine bisherigen änderungen würden nur verwirren.

die main simuliert einen Durchlauf mit dem String "TEST". Daher ist das ganze Script auf Strings aufgebaut.

ich wollte es so hinbekommen das ich damit ein byte Array einlesen kann, und dieses auch nur ausschließlich mit bytes arbeitet.

Hier die Original und noch unbearbeitete:

//////////////////////////////////////////////////////////////////////////////////////
// File: Huffman.java                Date: 12/11/1999		      Version: 1.00 //
// -------------------------------------------------------------------------------- //
//  										    //
// Dynamic huffman coder class for java.				    	    //
// Written from scratch and copyright (c) 1999 by Gerald Friedland.		    //
//										    //
// This program is released under the GNU Library Public License 2.00. 	            //  
// You must agree to this license before using, copying or modifying this	    //
// piece of code.								    //
//										    //
// You should have received a copy of the GNU Library General Public		    //
// License along with this class (see the file COPYING.LIB); if not, write to the   // 
// Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.          //
//										    //
// Please send bug reports, improvements, or proposals to: [email]fractor@germanymail.com[/email]  //
// Please consult the file README for details of using this software.  		    //
// -------------------------------------------------------------------------------- //
//  										    //
// 06/28/1999 Version 0.99e -- unofficial pre-version				    //
// 12/11/1999 Version 1.00 -- release, but still needs to be optimized heavily.     //
//////////////////////////////////////////////////////////////////////////////////////

import java.lang.*;
import java.io.*;
import java.math.*;

// ----------------------------- will be needed... -------------------
class node {
        public int edge1;
        public int edge2;
}

class chartableentry {
        public long count;
        public int character;
}

public class Huffman {

// ----------------------------- constants ---------------------------

public static final String VERSION = "1.00";
public static final int ALPHABETSIZE = 256;

// ----------------------------- static variables --------------------
private short usedchars;
private String[] transtable = new String[ALPHABETSIZE];  
private node[] tree=new node[ALPHABETSIZE*2];

// ----------------------------- general code ------------------------
static {
}

// Convert signed byte to unsigned byte (in Java we must use short for this)
public static short makeunsigned(byte x)
{
        return ( (x<0) ? (short) (x+256) : (short) x);
}    


// ----------------------------- compress ----------------------------

// Generate a lookuptable with the frequencies of the char in the alphabet
void gencounttable (byte[] datain, long[] counttable) 
{
	int i;
        for (i=0;i<counttable.length;i++) counttable[i]=0;
	for (i=0;i<datain.length;i++) {
		counttable[makeunsigned(datain[i])]=counttable[makeunsigned(datain[i])]+1;
	}
}

// Get the lowest frequented char
int getlowest(chartableentry[] chartable)
{
	int min=0;
	while (chartable[min].count==0) {
		min++;
		if (min==chartable.length) return(-1);
	}
	for (int i=min;i<chartable.length;i++) {
		if ((chartable[min].count>chartable[i].count) && (chartable[i].count>0)) min=i;
	}
	return(min);
}

// Builds a translation table from a given huffman tree.
void buildtranstable(node[] tree, int i, String code)
{
//	System.out.println("bt(tree,"+i+","+code+")");
	if (tree[i].edge1>=0) {
		transtable[tree[i].edge1]=code+"0";
	} else buildtranstable(tree,Math.abs(tree[i].edge1),code+0);
	if (tree[i].edge2>=0) {
		transtable[tree[i].edge2]=code+"1";
	} else buildtranstable(tree,Math.abs(tree[i].edge2),code+1);
}


// Generates huffman tree and then calls buildtranstable().
int generatecode (byte[] data, int[] treeout)
{
	int i,index,l;
	long k,n=0,addi;
	int j;
	long [] counttable = new long[ALPHABETSIZE]; 
	for (i=0;i<ALPHABETSIZE;i++) transtable[i] = new String();
	chartableentry[] chartable = new chartableentry[ALPHABETSIZE];
	node[] tree=new node[ALPHABETSIZE*2];
	gencounttable(data,counttable);
	usedchars=0;
	for (i=0;i<ALPHABETSIZE;i++) {
		chartable[i] = new chartableentry();
		if (counttable[i]!=0) {
		        chartable[usedchars].count=counttable[i];
			chartable[usedchars].character=(short) i;
		        usedchars++;
		}	
	}
	index=getlowest(chartable);
	tree[0]=new node(); // We do not use tree[0] but we must
	tree[0].edge1=0;    // initialize for not getting a
	tree[0].edge2=0;    // Null Pointer exception... :(
	j=1;
 	while (index!=-1) {
		tree[j]=new node();
		tree[j].edge1=chartable[index].character;
		addi=chartable[index].count;
		chartable[index].count=0;
		index=getlowest(chartable);
		if (index!=-1) {
			tree[j].edge2=chartable[index].character;
			chartable[index].count+=addi;
			chartable[index].character=(-1)*j;
		} else {
			tree[j].edge2=(-1)*j;
		}
		index=getlowest(chartable);
		j++;
	
	}
	buildtranstable(tree,j-2,""); 
	i=0;
        l=1;
        while (l<j-1) {
                treeout[i]=tree[l].edge1;
                treeout[i+1]=tree[l].edge2;
                i+=2;
                l+=1;
        }
	return(j-2);
}

// This routine sets bit n in b.
byte BitSet(byte b, int n)
{
	b|=1<<(n-1);
	return(b);
}

// Convert a dual number representation in String format to an array of bytes.
void String2Bytes(String s, byte[] barray)
{
	int i,j,l=s.length()/8;
	for (j=0;j<l;j++) {
		for (i=0;i<8;i++) {	
			if (s.charAt(i+(j*8))=='1') barray[j]=BitSet(barray[j],8-i);
		}
	}
	l=s.length()%8;
	for (i=0;i<l;i++) {
        	if (s.charAt(i+(j*8))=='1') barray[j]=BitSet(barray[j],8-i);
	}
}


// ----------------------------- uncompress --------------------------
// Does what name says...
void uncode(String s, byte[] dataout, int[] tree)
{
	int outcount=0;
	int incount=0;
	int treesize=0;
	int treecount=0;
	while (!((tree[treesize]==0) && (tree[treesize+1]==0))) treesize++;
	treecount=treesize-2;
	while ((outcount<dataout.length) && (incount<s.length())) {
		if (s.charAt(incount)=='0') {
			if (tree[treecount]>=0) {
				dataout[outcount]=(byte) tree[treecount];
				treecount=treesize-2;
				outcount++;
			} else {
				treecount=(Math.abs(tree[treecount]*2)-2);
			} 
		}
		if (s.charAt(incount)=='1') {
			if (tree[treecount+1]>=0) {
				dataout[outcount]=(byte) tree[treecount+1];
				treecount=treesize-2;
				outcount++;
			} else {
				treecount=(Math.abs(tree[treecount+1])*2)-2;
			} 			
		}
		incount++;
	}
}

// Convert decimal number to dual number fitted to 8^n bits.
String dual(int i)
{
	int h=1;
	String s="";
	while (h<=i/2) h*=2;
	while (h>0) {
		s+=(i/h);
		i=i%h;
		h=h/2;
	}
	if (s.length()%8!=0) {
		h=s.length()/8;
		h=((h+1)*8)-s.length();
		for (int j=0;j<h;j++) s="0"+s;
	}
	return(s);
}


// ----------------------------- interface ---------------------------
// compress
// compresses datain and gives the result in dataout 
// and the decoding tree in treeout.
// Returns the length of the resulting code as integer value.
public int compress(byte[] datain, byte[] dataout, int[] treeout)
{
	int len,j,l,i;
	String s = "";
	j=generatecode(datain,treeout);
	for (i=0;i<datain.length;i++) s+=transtable[makeunsigned(datain[i])];
	String2Bytes(s,dataout);
	len=s.length()/8;
	if ((s.length()%8)>0) len++; 
	return(len);			
}

public int treesize(int[] treein)
{
	int ts=0;
	while (!((treein[ts]==0) && (treein[ts+1]==0))) ts++;
	return ts;
}


// uncompresses datain using tree into dataout.
// dataout will be filled up exactly (-> may not be longer than code expected!)
public void uncompress(byte[] datain, byte dataout[], int[] treein)
{
	int i;
	String s="";
	for (i=0;i<datain.length;i++) s+=dual(makeunsigned(datain[i]));		
	uncode(s,dataout,treein);
}

// Test and demonstration method.
public static void main(String[] args) 
{
	Huffman h = new Huffman();
	System.out.println();
	System.out.println("Dynamic Huffman Compression Class for Java.");
	System.out.println("Version "+VERSION);
	System.out.println("Copyright (c) 1999 by Gerald Friedland");
	System.out.println("This library is free software according to the terms");
	System.out.println("of the GNU Library Public License 2.00 (see COPYING.LIB).\n\n");
	if ((args.length!=1) && (args.length!=2)) { 
		System.out.println("huffman <teststring> [d]");
		System.out.println("If you specify a second argument, you will get debugging output"); 		
		return;
	}
	int i,l2,ts;
	int l=args[0].length();
	int huftree[] = new int[ALPHABETSIZE];
	byte dataout2[] = new byte[l];
	byte datain[] = new byte[l];
	byte dataout[] = new byte[l];
	
	for (i=0;i<l;i++) datain[i]=(byte) args[0].charAt(i); 
	
	if (args.length==2) {
		System.out.println("Input (ASCII Code):");
		for (i=0;i<l;i++) System.out.print(makeunsigned(datain[i])+" ");
	}
	
	l=datain.length;
	l2=h.compress(datain,dataout,huftree);
	ts=h.treesize(huftree);
	if (args.length==2) {
		System.out.println("\nCompressed (New Code):");
		for (i=0;i<l2;i++) System.out.print((byte) dataout[i]+" ");
	}
	
	h.uncompress(dataout,dataout2,huftree);
	
	if (args.length==2) {	
		System.out.println("\nUncompressed:");
		for (i=0;i<dataout.length;i++) System.out.print((byte) dataout2[i]+" ");
		System.out.println();
		System.out.println();
		System.out.println("Tree length: "+ts);
	}
	
	System.out.println("Ratio (without tree):   1:"+(float) l/l2); 
	System.out.print  ("Real ratio (with tree): 1:"+(float) l/(l2+ts));	
	if (l/(l2+ts)<1) System.out.println(" => INFLATION!"); else System.out.println();
}
}

 

[PyroPi]

So, hat nen Moment gedauert, war noch andersweitig beschäftigt. Also die Codierung funktioniert für Byte Arrays prima (zumindest für die paar Testfälle, die ich versucht hab). Wenn du die main-Methode wie folgt änderst, kannst du das Byte-Array datain beliebig mit Bytes füllen und dann codieren. Fehlt dann nur noch das Abspeichern und Laden.

public static void main(String[] args) 
{ 
   Huffman h = new Huffman(); 

   int i,l2,ts; 
   int huftree[] = new int[ALPHABETSIZE]; 
   
   // Eingabefeld
   byte datain[] = new byte[] {0,1,0,1,0,0,1,1, 1}; 
   int l = datain.length; 
   
   byte dataout2[] = new byte[l]; 
   byte dataout[] = new byte[l]; 

   
   System.out.println("Input (ASCII Code):"); 
   for (i=0;i<l;i++) System.out.print(makeunsigned(datain[i])+" "); 
    
   l2=h.compress(datain,dataout,huftree); 
   ts=h.treesize(huftree); 

   System.out.println("\nCompressed (New Code):"); 
   for (i=0;i<l2;i++) System.out.print((byte) dataout[i]+" ");
   
   h.uncompress(dataout,dataout2,huftree); 
    
   System.out.println("\nUncompressed:"); 
   for (i=0;i<dataout.length;i++) System.out.print((byte) dataout2[i]+" "); 
   System.out.println(); 
   System.out.println(); 
   System.out.println("Tree length: "+ts); 
    
   System.out.println("Ratio (without tree):   1:"+(float) l/l2); 
   System.out.print  ("Real ratio (with tree): 1:"+(float) l/(l2+ts));    
   if (l/(l2+ts)<1) System.out.println(" => INFLATION!"); else System.out.println(); 
}

 

[JonnyF]

Danke das du dir soviel Arbeit machst, bis dahin hatte ich das aber schon durchgetestet.
Der Code kommt nicht mit vielen Daten klar. Bei eine 20kb Datei braucht er über 5 Sekunden und der Rechner friert fast ein.

Das Problem ist das er das Bitshifting als String ausführt. Es muss jedoch alles auf byte[] basis geschehen da sich so sonst keine Dateien byte Ströme einlesen lassen.

Ich habe hier schon geänderte Methoden, möchte die jedoch ungern hier posten. Ich würde dir das gerne zusenden wenn du magst. Du blickst da sicher schnell den Fehler.

 

[PyroPi]

Ok, wenn's noch nicht zu spät ist, kannst du mir ne Mitteilung schicken.