# LZ78



## Sduni (18. Mai 2010)

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 (19. Mai 2010)

mal gegoogelt und bei wikipedia was gefunden 

Klick Mich



> Das Wörterbuch wird am Anfang folgendermaßen aussehen:
> 
> # = 00000
> A = 00001
> ...



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 (19. Mai 2010)

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


----------



## Nicer (19. Mai 2010)

> "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 (19. Mai 2010)

Nicer hat gesagt.:


> 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 (19. Mai 2010)

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


----------



## Sduni (19. Mai 2010)

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 (19. Mai 2010)

Sduni hat gesagt.:


> 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 (20. Mai 2010)

Sduni hat gesagt.:


> 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.


----------

