LZ78

Sduni

Mitglied
hallo zusammen.

Wir sollen einen Algorythmus zur dekodierung eines mit Lempel Ziv (LZ78) komprimierten Text schreiben.

Der Algorythmus soll das bei der Kodierung benutzte Wörterbuch nicht explizit übergeben bekommen, sondern neu aufbauen.

Wie soll ich dekodieren ohne Wörterbuch? Versteh nicht ganz wie das gemeint ist.
 
Zuletzt bearbeitet:

Nicer

Bekanntes Mitglied
mal gegoogelt und bei wikipedia was gefunden :)

Klick Mich


Das Wörterbuch wird am Anfang folgendermaßen aussehen:

# = 00000
A = 00001
B = 00010
C = 00011



Z = 11010

da findest du eine erklärung wie die kodierung und dekodierung geht ( an einem beispiel ) und aus dem kannst du ja dann die Logik dahinter rauslesen
 

Sduni

Mitglied
unschwer daran zu erkennen das das eine mit i und das andere mit y geschrieben wird ^.^

hab halt rhytmus im blut :autsch:

habs jetzt mal so gemacht:
Java:
public LV78(String[] args){
		List<String> dict = new ArrayList<String>();
		dict.add("");
		for(int i = 0; i < args.length; i++){
			dict.add(dict.get(Integer.parseInt(String.valueOf(args[i].charAt(0)))) + String.valueOf(args[i].charAt(args[i].length()-1)));
		}
		String ausgabe = "";
		for(int j = 0; j < dict.size(); j++){
			ausgabe = ausgabe + dict.get(j);
		}
		System.out.println(ausgabe);
	}

Wie beweist man nun die Korrektheit ohne explizites Beispiel?
 
Zuletzt bearbeitet:

Sduni

Mitglied
schöner Mist, das kann ich nicht. Gibt es eigentlich eine Datenstruktur als den Array oder Liste für das Wörterbuch, die mit der Größe O(c) anstatt Omega(c²) auskommt?

Wie wäre es wenn man Huffman und LZ kombiniert? ALso im Wörterbuch Adressen in binär speichert? dadurch würde sich die Größe des Wörterbuches doch verringern?
 
Zuletzt bearbeitet:

Landei

Top Contributor
schöner Mist, das kann ich nicht. Gibt es eigentlich eine Datenstruktur als den Array oder Liste für das Wörterbuch, die mit der Größe O(c) anstatt Omega(c²) auskommt?

Wie wäre es wenn man Huffman und LZ kombiniert? ALso im Wörterbuch Adressen in binär speichert? dadurch würde sich die Größe des Wörterbuches doch verringern?

Das ist, wie wenn du ein Zip nochmal zippst, es bringt kaum was, denn deine Daten werden beim packen absolut zufällig, nur noch weißes Rauschen, und da kann kein Pack-Algorithmus mehr etwas herausholen.
 

Neue Themen


Oben