Frage zum LZW Komprimierungsalgorithmus

seux

Hallo,
in der Uni haben wir letztens den LZW algorithmus besprochen, leider allerdings nur theoretisch anhand eines Beispiels und später in einer Übungsaufgabe. Dabei ging es jeweils darum, ein vorgegebenes Wort mit Stift und Zettel zu komprimieren.
Ich wollte das jetzt mal praktisch nachvollziehen, indem ich eine simple .txt Datei mit einem Satz komprimiere und die komprimiert Version in eine andere Datei schreibe.

Nun zu meinem Problem:
Wenn ich ein Byte der Datei einlese, ist jedem Wert dieses Bytes ja schon ein Zeichen zugeordnet (ASCII Zeichensatz). Beim LZW Verfahren bastelt man sich ein Wörterbuch zusammen. Da die ersten 255 Zeichen schon vergeben sind, fängt mein Wörterbuch, wie in der Uni gezeigt, bei 256 an.
Problem:
Der Wert 256 lässt sich nicht mehr mit nur einem Byte darstellen. Wie kann ich das so machen, dass der Computer weiß, dass er nun 2 Byte (oder vielleicht sogar mehr) einlesen müsste, um den richtigen Wörterbucheintrag zu erhalten?

Lg seux

Na indem du für jedes Zeichen in der komprimierten Datei mehr als 8Bit verwendest, z.B. 12Bit (oder 16Bit wenn du es dir einfach machen willst).

seux

Und wie kann ich das machen? Ich versuch das in Java umzusetzen, so wie ich das verstanden hab, ist da ein Byte = 8 Bit. Kann man das ändern?
Andererseits, würde die datei dadurch überhaupt komprimiert werden? wenn ich für jedes Zeichen 16Bit statt 8 nehme, wird die Datei doch eher größer.

seux schrieb:

Und wie kann ich das machen? Ich versuch das in Java umzusetzen, so wie ich das verstanden hab, ist da ein Byte = 8 Bit. Kann man das ändern?

Nein, aber wenn du 16 bit nimmst ist das doch nicht so schwer, bei 12 bit musst du halt schiften << >> und verodern.

Andererseits, würde die datei dadurch überhaupt komprimiert werden? wenn ich für jedes Zeichen 16Bit statt 8 nehme, wird die Datei doch eher größer.

möglicherweise

volkard

seux schrieb:

Andererseits, würde die datei dadurch überhaupt komprimiert werden? wenn ich für jedes Zeichen 16Bit statt 8 nehme, wird die Datei doch eher größer.

Da hast Du recht. So alleine funktioniert das noch nicht.
Aber wenn Du als Endstufe noch einen Entropie-Encoder nachschaltest, ist alles in Butter. Dem ist ja egal, wie groß der Zeichenvorrat ist, er spuckt einen Bitstom aus, wobei es ihm ein Genuß ist, wenn es Zeichen gibt, die extrem selten vorkommen. Die werden dann duch überlange Bitfolgen dargestellt, während häufigere Zeichen durch besonders kurze glänzen.

Siehe auch die Burrows-Wheeler-Transformation, da wird es besonders deutlöich, finde ich. Die alleine tut noch gar nichts komprimieren. Aber sie macht Ähnlichkeiten dichter beieinanderliegend. Ihre Ausgabe kann dann von irgendwas wie dem Umsetzen in Indizes einer Move-To-Front-List so umgewandelt werden, daß man eine prima Schieflage in der Werteverteilung hat und dann kann ein Entropie-Encoder zuschlagen und den Deckel zu machen.

seux schrieb:

Und wie kann ich das machen? Ich versuch das in Java umzusetzen, so wie ich das verstanden hab, ist da ein Byte = 8 Bit. Kann man das ändern?
Andererseits, würde die datei dadurch überhaupt komprimiert werden? wenn ich für jedes Zeichen 16Bit statt 8 nehme, wird die Datei doch eher größer.

Ja, da du in den 16 Bit ja mehr als zwei Zeichen speichern kannst. Du hat lzw ja schon auf Papier durchgeführt, dann ist dir ja sicher aufgefallen, dass man mit einer zahl auch sehr viele Zeichen der Eingabe auf einmal kodieren kann. Ob an Ende die Daten tatsächlich kleiner kodiert werden hängt von der Entropie ab.

Wie volkard schon angedeutet hat, verwendet man in der Praxis meist noch ein zweites Verfahren, das lzw nachgeschaltet ist. Aber man kann auch ohne ein solches schon ordentlich komprimieren.

seux

So, wollte mich nur noch nachträglich für die Kommentare bedanken. Hab da doch länger dran gesessen als ich vermutet hab. Dachte das wäre einfacher.
Das mit dem Entropie Encoder werd ich mir noch angucken, denn bisher vergrößert sich die Datei wie erwartet nur.

Hier ist erstmal der Quellcode der Java Datei, wie weit ich bisher bin.

import java.io.File;
import java.io.RandomAccessFile;
import java.io.IOException;

class LZW
{

	private int dictionaryIndexToPrint = 0;		//Befindet sich das Teilwort schon im Wörterbuch, wird hier der Index gespeichert
	private boolean wasInDictionary = false;	//Wird für die Funktion isAlreadyInCodeTable benötigt

	public static void main(String[] args)
	{
		LZW lzw = new LZW();
		lzw.compress(new File("meinText.txt"));
	}

	public void compress(File file)
	{
		if(file.exists() != true)
		{
			System.out.println("Datei existiert nicht, programm wird beendet");
			return;
		}

		try{
			File comFile = new File(file.getName() + "Kompr.txt");		//Später die Extension von getName() noch entfernen!!!
			comFile.createNewFile();

			RandomAccessFile fileReader = new RandomAccessFile(file, "r");
			RandomAccessFile fileWriter = new RandomAccessFile(comFile, "rw");

			System.out.println("Die Originaldatei hat eine groesse von " + fileReader.length() + " Bytes");

			short gelesenesByte;
			String puffer = new String();
			short index = 256;
			String[][] codeTable = new String[(int)fileReader.length()][2];	//Spalte zwei für den Index

			//Codetabelle mit "" füllen
			for(long i = 0; i < fileReader.length(); i++)
				codeTable[(int)i][0] = "";

			//LZW Tabelle
			System.out.println("Lesen\tCodetabelle\tAusgabe\t\tPuffer");

			for(long i = 0; i < fileReader.length(); i++)
			{
				gelesenesByte = (short)fileReader.read();	//Einlesen des nächsten zeichens

				if(i == 0)						//Im ersten durchgang wird noch nichts ins Wörterbuch geschrieben
				{
					puffer = Integer.toString(gelesenesByte);			//sondern nur das gelesene zeichen in den puffer übernommen
					System.out.println(gelesenesByte + "\t\t\t\t\t" + puffer);
					continue;
				}

				//Befindet sich das Teilwort bestehen aus puffer + gelesenesByte schon in der Codetabelle
				if(isAlreadyInCodeTable(codeTable, new String(puffer + Integer.toString(gelesenesByte)), i) == false)
				{	
					//Es befindet sich noch nicht in der Codetabelle
					codeTable[(int)i][0] = "" + puffer + gelesenesByte;
					codeTable[(int)i][1] = Integer.toString(index);
					//System.out.println(codeTable[(int)i][0] + '\t' + codeTable[(int)i][1]);
					index++;

					//Den Puffer in die Datei schreiben
					//for(int j = 0; i < puffer.length(); j++)
						//fileWriter.write(puffer.charAt(j));

					//Ausgabe für die Tabelle
					if(wasInDictionary == false) 
					{
						System.out.println(Integer.toString(gelesenesByte) + '\t' + (puffer + Integer.toString(gelesenesByte)) + "\t\t" + puffer + "\t\t" + Integer.toString(gelesenesByte) );
						fileWriter.writeShort(Integer.parseInt(puffer));
					}
					else
					{
						System.out.println(Integer.toString(gelesenesByte) + '\t' + (puffer + Integer.toString(gelesenesByte)) + "\t\t" + dictionaryIndexToPrint + "\t\t" + Integer.toString(gelesenesByte) );
						fileWriter.writeShort(dictionaryIndexToPrint);
					}
					puffer = Integer.toString(gelesenesByte);
					wasInDictionary = false;
				}
				else
				{
					//Es befindet sich schon in der Codetabelle
					puffer += gelesenesByte;
					System.out.println(gelesenesByte + "\t\t\t\t" + puffer);
				}
			}
			System.out.println("EOF\t\t\t\t" + puffer);
			fileWriter.writeShort(Short.parseShort(puffer));

			System.out.println("\nDie komprimierte Datei hat eine groesse von " + fileWriter.length() + " Bytes");

			fileReader.close();
			fileWriter.close();

		} catch(IOException e) {
		}
	}

	private boolean isAlreadyInCodeTable(String[][] ct, String s, long lCounter)
	{
		for(long i = 0; i < lCounter; i++)
		{
			if(ct[(int)i][0].equals(s))		
			{
				dictionaryIndexToPrint = Integer.parseInt(ct[(int)i][1]); 
				wasInDictionary = true;
				return true;
			}
		}

		return false;
	}

	public void decompress(File file)
	{

	}
}

Für Hinweise bezüglich stilistischer Fehler wäre ich sehr dankbar

Ein Tipp: man kann das Wörterbuch bei N Bit Kodierung in (N+8)^N Bits abspeichern. Bei dir wäre N=16.

Tippgeber schrieb:

Ein Tipp: man kann das Wörterbuch bei N Bit Kodierung in (N+8)^N Bits abspeichern. Bei dir wäre N=16.

Sorry, da war ich gestern wohl zu müde. Bei N Bit Kodierug kann man für Tabelle in (N+8)*2^N Bits abspeichern

seux

Tippgeber schrieb:

Tippgeber schrieb:

Ein Tipp: man kann das Wörterbuch bei N Bit Kodierung in (N+8)^N Bits abspeichern. Bei dir wäre N=16.

Sorry, da war ich gestern wohl zu müde. Bei N Bit Kodierug kann man für Tabelle in (N+8)*2^N Bits abspeichern

Ähm, sorry, Ich hab davon nichts verstanden. Ich hab doch jetzt absichtlich N=16 gewählt, damit ich auch Werte über 255 speichern kann. Wenn ich jetzt die Daten aus der komprimierten Datei einlese, lese ich immer 2 Byte ein und verarbeite die.