Brauche den Namen dieses Algorithmusses

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Brauche den Namen dieses Algorithmusses

Beitrag von Krishty »

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
Zuletzt geändert von Krishty am 04.12.2011, 11:29, insgesamt 1-mal geändert.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Jörg
Establishment
Beiträge: 296
Registriert: 03.12.2005, 13:06
Wohnort: Trondheim
Kontaktdaten:

Re: Brauche den Namen dieses Algorithmusses

Beitrag von Jörg »

Klingt fuer mich nach "String dictionaries"-Gegend.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Brauche den Namen dieses Algorithmusses

Beitrag von Krishty »

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)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
antisteo
Establishment
Beiträge: 854
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: Brauche den Namen dieses Algorithmusses

Beitrag von antisteo »

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

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.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Brauche den Namen dieses Algorithmusses

Beitrag von Krishty »

Off Topic:
antisteo hat geschrieben:Dann würdest du Strings ja mit Start+Länge identifizieren.
Klar … Pascal-Strings (Zeiger auf Anfang + Länge) ftw. C-Strings sind einfach nur zum Kotzen; in fast jedem Anwendungsbereich nichts als ein riesiges Ärgernis.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
antisteo
Establishment
Beiträge: 854
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: Brauche den Namen dieses Algorithmusses

Beitrag von antisteo »

Off Topic:
Krishty hat geschrieben:
antisteo hat geschrieben:Dann würdest du Strings ja mit Start+Länge identifizieren.
Klar … Pascal-Strings (Zeiger auf Anfang + Länge) ftw. C-Strings sind einfach nur zum Kotzen; in fast jedem Anwendungsbereich nichts als ein riesiges Ärgernis.
Pascal-Strings sind ein Zeiger auf das erste Zeichen des Strings, der mit 0 terminiert wird. Links vom ersten Zeichen sind dann noch Referenzzähler und Länge.
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
Jörg
Establishment
Beiträge: 296
Registriert: 03.12.2005, 13:06
Wohnort: Trondheim
Kontaktdaten:

Re: Brauche den Namen dieses Algorithmusses

Beitrag von Jörg »

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 ;)
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Brauche den Namen dieses Algorithmusses

Beitrag von Krishty »

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:
Urks; stimmt. Sagen wir, Pascal-ish Strings :)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: Brauche den Namen dieses Algorithmusses

Beitrag von dot »

Jörg
Establishment
Beiträge: 296
Registriert: 03.12.2005, 13:06
Wohnort: Trondheim
Kontaktdaten:

Re: Brauche den Namen dieses Algorithmusses

Beitrag von Jörg »

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?
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Brauche den Namen dieses Algorithmusses

Beitrag von Krishty »

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
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Jörg
Establishment
Beiträge: 296
Registriert: 03.12.2005, 13:06
Wohnort: Trondheim
Kontaktdaten:

Re: Brauche den Namen dieses Algorithmusses

Beitrag von Jörg »

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 .
Benutzeravatar
BeRsErKeR
Establishment
Beiträge: 689
Registriert: 27.04.2002, 22:01

Re: Brauche den Namen dieses Algorithmusses

Beitrag von BeRsErKeR »

Ohne Input kein Output.
Eisflamme
Establishment
Beiträge: 412
Registriert: 26.05.2002, 17:42
Wohnort: Köln

Re: Brauche den Namen dieses Algorithmusses

Beitrag von Eisflamme »

Kommt der hier nicht recht nah dran? http://de.wikipedia.org/wiki/LZ78
kaiserludi
Establishment
Beiträge: 467
Registriert: 18.04.2002, 15:31

Re: Brauche den Namen dieses Algorithmusses

Beitrag von kaiserludi »

Krishty hat geschrieben:Aber leider ist es auch nicht ineffizient.
Wieso leider?
"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]
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Brauche den Namen dieses Algorithmusses

Beitrag von Krishty »

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!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Jörg
Establishment
Beiträge: 296
Registriert: 03.12.2005, 13:06
Wohnort: Trondheim
Kontaktdaten:

Re: Brauche den Namen dieses Algorithmusses

Beitrag von Jörg »

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?
Benutzeravatar
BeRsErKeR
Establishment
Beiträge: 689
Registriert: 27.04.2002, 22:01

Re: Brauche den Namen dieses Algorithmusses

Beitrag von BeRsErKeR »

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?
Ohne Input kein Output.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Brauche den Namen dieses Algorithmusses

Beitrag von Krishty »

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.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Antworten