Brauche den Namen dieses Algorithmusses
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
- Krishty
- Establishment
- Beiträge: 8229
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Brauche den Namen dieses Algorithmusses
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
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
Zuletzt geändert von Krishty am 04.12.2011, 11:29, insgesamt 1-mal geändert.
Re: Brauche den Namen dieses Algorithmusses
Klingt fuer mich nach "String dictionaries"-Gegend.
- Krishty
- Establishment
- Beiträge: 8229
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Brauche den Namen dieses Algorithmusses
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)
Die drei Wörter
hello
low
hell
sollen gepoolt werden. Die Ausgabe wäre dann:
hellow
(0, 5); (3, 3); (0, 4)
Re: Brauche den Namen dieses Algorithmusses
Dann würdest du Strings ja mit Start+Länge identifizieren.
ich würde das KA nennen... Krishty Algorithmus
ich würde das KA nennen... Krishty Algorithmus
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
- Krishty
- Establishment
- Beiträge: 8229
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Brauche den Namen dieses Algorithmusses
Off Topic:
Re: Brauche den Namen dieses Algorithmusses
Off Topic:
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
Re: Brauche den Namen dieses Algorithmusses
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 ;)
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 ;)
- Krishty
- Establishment
- Beiträge: 8229
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Brauche den Namen dieses Algorithmusses
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?
OT:
Also doch Dictionaries? Na, dann mal auf in die Fluten …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 ;)
OT:
- dot
- Establishment
- Beiträge: 1734
- Registriert: 06.03.2004, 18:10
- Echter Name: Michael Kenzel
- Kontaktdaten:
Re: Brauche den Namen dieses Algorithmusses
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
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
Re: Brauche den Namen dieses Algorithmusses
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?
- Krishty
- Establishment
- Beiträge: 8229
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Brauche den Namen dieses Algorithmusses
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
Re: Brauche den Namen dieses Algorithmusses
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 .
Re: Brauche den Namen dieses Algorithmusses
http://en.wikipedia.org/wiki/Radix_tree (PATRICIA Tries)
http://en.wikipedia.org/wiki/Suffix_tree (Suffix Tree)
http://en.wikipedia.org/wiki/Suffix_tree (Suffix Tree)
Ohne Input kein Output.
Re: Brauche den Namen dieses Algorithmusses
Kommt der hier nicht recht nah dran? http://de.wikipedia.org/wiki/LZ78
-
- Establishment
- Beiträge: 467
- Registriert: 18.04.2002, 15:31
Re: Brauche den Namen dieses Algorithmusses
Wieso leider?Krishty hat geschrieben:Aber leider ist es auch nicht ineffizient.
"Mir ist auch klar, dass der Tag, an dem ZFX und Developia zusammengehen werden der selbe Tag sein wird, an dem DirectGL rauskommt."
DirectGL, endlich ist es da :)
"According to the C++ standard, it's "undefined". That's a technical term that means, in theory, anything can happen: the program can crash, or keep running but generate garbage results, or send Bjarne Stroustrup an e-mail saying how ugly you are and how funny your mother dresses you." :shock:[/size]
DirectGL, endlich ist es da :)
"According to the C++ standard, it's "undefined". That's a technical term that means, in theory, anything can happen: the program can crash, or keep running but generate garbage results, or send Bjarne Stroustrup an e-mail saying how ugly you are and how funny your mother dresses you." :shock:[/size]
- Krishty
- Establishment
- Beiträge: 8229
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Brauche den Namen dieses Algorithmusses
Vertippt. Habe ich zuerst selbst im Zitat nicht erkannt m[ Dankeschön!kaiserludi hat geschrieben:Wieso leider?Krishty hat geschrieben:Aber leider ist es auch nicht ineffizient.
Re: Brauche den Namen dieses Algorithmusses
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?
Re: Brauche den Namen dieses Algorithmusses
Ich glaube Krishty wollte auf Dekodierung/Dekompression verzichten.Eisflamme hat geschrieben:Kommt der hier nicht recht nah dran? http://de.wikipedia.org/wiki/LZ78
@Krishty: Schonmal die PATRICIA Tries angeguckt?
Ohne Input kein Output.
- Krishty
- Establishment
- Beiträge: 8229
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Brauche den Namen dieses Algorithmusses
Ganz genau – es ist essentiell, dass man zur Laufzeit nicht merkt, dass eine Kompression zugange war.BeRsErKeR hat geschrieben:Ich glaube Krishty wollte auf Dekodierung/Dekompression verzichten.
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").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?
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.