ZFX + Developia

Hi,

Ich habe hier so eine Art Kompressionsalgorithmus, der beliebige Strings erwartet und dann in einen Pool schmeißt. Dabei werden die Strings auf eine Art und Weise sortiert, dass sie sich maximal überlappen; d.h., dass der Pool minimal groß wird.

Das ist ganz nützlich, wenn man eine Große Menge kurzer Datenfetzen optimieren, dabei aber auf Dekompressionsalgorithmen verzichten möchte. Aber leider ist es auch nicht effizient. Darum brauche ich jetzt einen Namen für das Problem oder den Algorithmus, nach dem ich suchen kann, um herauszufinden, wie sich das besser lösen lässt …

Gruß, Ky

Klingt fuer mich nach "String dictionaries"-Gegend.

So, wie ich das sehe, geht es dort vor allem um die Suchalgorithmen, um Strings im Verzeichnis zu finden … sowas habe ich garnicht. Mal ein Beispiel:

Die drei Wörter

hello
low
hell

sollen gepoolt werden. Die Ausgabe wäre dann:

hellow
(0, 5); (3, 3); (0, 4)

Dann würdest du Strings ja mit Start+Länge identifizieren.

ich würde das KA nennen... Krishty Algorithmus

Off Topic:

Off Topic:

Ja, haste recht, im Woerterbuch sucht man nur.
Ansonsten klingt das von der Idee her wie ein Lempel-Ziv Abkoemmling. Sind denn alle Strings bekannt , bevor der Pool (optimal?) gebaut wird, oder laeuft das dynamisch, also kommen immer neue Strings dazu?

Ha und jetzt sehe ich, dass in beiden Kontexten (Woerterbuch-Suchbaum und Stringpool) in der Literatur das Wort Woerterbuch/Dictionary verwendet wird. Du brauchst halt ein kompaktes mit Index ;)

Der Pool ist statisch. Er ist nicht optimal (da würde das eh schon günstige Laufzeitverhalten nochmal explodieren) aber bis auf, sagen wir, ein Prozent dran.

Bei LZ wird afaik nicht zwischen Wörterbuch und Symbolliste getrennt, oder?

Jörg hat geschrieben:Ha und jetzt sehe ich, dass in beiden Kontexten (Woerterbuch-Suchbaum und Stringpool) in der Literatur das Wort Woerterbuch/Dictionary verwendet wird. Du brauchst halt ein kompaktes mit Index ;)

Also doch Dictionaries? Na, dann mal auf in die Fluten …

OT:

Ich denk du suchst eins von denen (tippe vor allem mal in Richtung #2):
http://en.wikipedia.org/wiki/Trie
http://en.wikipedia.org/wiki/Directed_a ... word_graph
http://en.wikipedia.org/wiki/Prefix_Hash_Tree
http://en.wikipedia.org/wiki/Judy_array

LZ wuerde einem String aber nicht nur ein Paar (Index+Laenge zuweisen), sondern ihn in mehrere Teile splitten...was macht dein Code, wenn Du einen sich selbst wiederholenden String "FooBlaFooBla" verwendest? Volle Laenge abspeichern?

Volle Länge, genau. Allerdings kannst du das mit dem Splitten ja auch anders sehen – indem du in LZ Strings statt Buchstaben als Symbole nimmst, und dann im Sub-Symbol-Bereich nach Redundanz suchst … oder so ähnlich :D

Mir faellt eben ein, dass man natuerlich auch im Suchbaum indiziert auf Strings zugreiffen kann...einfach den Blatt-Index nehmen. ja, der String ist dann ru eckwaerts...aber was soll's .

http://en.wikipedia.org/wiki/Radix_tree (PATRICIA Tries)
http://en.wikipedia.org/wiki/Suffix_tree (Suffix Tree)

Kommt der hier nicht recht nah dran? http://de.wikipedia.org/wiki/LZ78

Krishty hat geschrieben:Aber leider ist es auch nicht ineffizient.

Wieso leider?

kaiserludi hat geschrieben:

Krishty hat geschrieben:Aber leider ist es auch nicht ineffizient.

Wieso leider?

Vertippt. Habe ich zuerst selbst im Zitat nicht erkannt m[ Dankeschön!

Noch eine Frgae dazu...in einem mit Objektnamen arbeitendem Umfeld (lass es einen Szenengraphen sein) ist es ja nicht ungewoehnlich, auf aussagekraeftige Bezeichner wie "Baum1" bis "BaumXXXX" zu treffen. Darunter leidet Dein Pool doch arg, was waere/ist denn das Einsatzgebiet?

Eisflamme hat geschrieben:Kommt der hier nicht recht nah dran? http://de.wikipedia.org/wiki/LZ78

Ich glaube Krishty wollte auf Dekodierung/Dekompression verzichten.

@Krishty: Schonmal die PATRICIA Tries angeguckt?

BeRsErKeR hat geschrieben:Ich glaube Krishty wollte auf Dekodierung/Dekompression verzichten.

Ganz genau – es ist essentiell, dass man zur Laufzeit nicht merkt, dass eine Kompression zugange war.

Jörg hat geschrieben:Noch eine Frgae dazu...in einem mit Objektnamen arbeitendem Umfeld (lass es einen Szenengraphen sein) ist es ja nicht ungewoehnlich, auf aussagekraeftige Bezeichner wie "Baum1" bis "BaumXXXX" zu treffen. Darunter leidet Dein Pool doch arg, was waere/ist denn das Einsatzgebiet?

Ursprünglich habe ich ihn für meinen Compiler entworfen, weil ich unzufrieden mit der Art und Weise bin, wie Visual C++ Strings poolt und Daten zusammenfasst (bspw. werden die Strings "bar" und "bar" im Datensegment zusammengefasst, nicht aber "bar" und "foobar").

Im Augenblick ist er in einem System im Einsatz, das automatisiert Funksprüche zusammensetzt (Berlin | tower, this is | Shark | – request vector for recovery). Die komprimierten Texte brauchen 30 % weniger Platz; 45 MiB PCM-Audiodaten werden durch Entfall redundanter Fetzen und optimales Überlappen der Pausen an Anfang und Ende immerhin noch 6 % kleiner (nur leider bei einer Laufzeit von mehreren Stunden).

@BeRsErKeR: Danke; schaue ich mir an, sobald ich mit den anderen Links durch bin.