LZ78

[Sduni]

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.

 

[Nicer]

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

 

[Landei]

"Algorithmus" hat übrigens nichts mit "Rhythmus" zu tun, sondern mit einem alten Araber...

 

[Nicer]

"Algorithmus" hat übrigens nichts mit "Rhythmus" zu tun, sondern mit einem alten Araber...

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

 

[Sduni]

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:

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?

 

[fastjack]

So weit ich mich erinnern kann, durch formale Beweise ala Haskel-Funktionen zum Bleistift.

 

[Sduni]

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?

 

[Nicer]

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?

HÄ ? ^^ keine anung was Huffmann ist

 

[Landei]

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.