Hi,

mit etwas Verspätung mir fesselt grad ein Virus in der horizontalen.

Ähm ... Deine sexuellen Präferenzen interessieren mich jetzt eher weni... achso, krank isser, dann mal Gesundheit!

Aber da ich mich da jetzt eh durchwühlen mußte:

das wollte ich nicht! :(

Na, waren gerade mal 150 Seiten, das halbe Stündchen habe ich denn auch noch ;-)

hat mit unserem Problem und Deinem Vorschlag nur sehr am Rande etwas zu tun.

Stimmt. Ich versuche auch den möglichen Background zum ct-Artikel zu finden (den ich wg Bettruhe auch noch nicht lesen konnte).

Macht nix, ich habe es noch nicht einmal geschafft mir eine ct zu besorgen.

Ich hatte auch nen sehr interessanten Link zu dem Thema den ich jetzt nicht mehr finde ... ahh wozu gibts CTRL-H ... moment ... et voila ... http://blog.csdn.net/jiangtao/archive/2004/04/08/270.aspx

Mir fehlen für xpdf die richtigen Fonts (nein, ich habe nur Freefont nicht richtig eingebunden bekommen oder das ist zu alt) aber ich werde das dumme Gefühl nicht los, das das einer seiner Studenten ist?
Aber ist ja auch egal, tut hier nix zur Sache.

Die untersuchte Materie ist der Umstand, das sich alle Kompressions- und Suchalgorithmen auf ein Sortierproblem zurückführen lassen. Das ist hochinteresant aber leider nur noch theoretisch von Belang, da es nicht mehr wichtig ist, die Leistung eines Einzelnen optimal einzusetzen, sondern die Aufgabe optimal zu verteilen.
Es ist zwar durchaus von Belang für den Selfserver hier - ist ja im Grunde nur eine einzelne Maschine und Verteilungoptimierung lohnt nur für Knotenmengen >> eine Handvoll - aber der Vorgang ist sehr komplex und müßte von Grund auf gebastelt werden. Lohnt das?

Ich denke der Zusammenhang zu unserem Problem ist, dass im Allgemeinen keine ganzen Wörter gesucht werden, sondern auch submatches!

Ja, das ergibt sich natürlich schon zwingend.

Der Gag ist, die BWT sortiert die Buchstaben eines Textes so um dass bestimmte Ordnungstrukturen erhalten bleiben, die eine sehr schnelle Suche von Teilstrings erlaubt. Und nebenbei läßt sich BWTransformierter Text bis fast ans theoretische Optimum komprimieren.

Dabei geht aber, und das macht die Zusammenfassung auf Deinem Link oben nochmal besonders deutlich, der Ort verloren.
Mmh ... Heisenberg in der Informationstheorie? ;-)

Ist der wichtig? Wenn nicht, wäre es ein relativ bequemer Ansatz, wenn doch wird die Komplexität stark erhöht bzw der Speicherbedarf.

In wie weit das aber zu meiner Hash-in-Hash-Lösung kombinierbar ist, die IMHO die beste Performance bei Ganzwörtern liefern sollte, weiß ich noch nicht.

Da Hashtables (die in den USA übrigens patentiert sind) in O(1) was finden, kann das vorgeschaltet werden.
Oben vorgestellte Methode hat zwar eine gute Speichereffiziens für "vorgesuchte" Volltextsuche dürfte aber auch noch zu groß sein und das Budget sprengen.
Gut, _sowas_ ist natürlich kein Argument, klar ;-)

Das ist aufgrund des riesigen Alphabets der Silbenschrift nötig sowie günstiger bei DNA-Sequenzen (da gibt es keine Wörter im eigentlichem Sinne wenn auch das Alphabet dafür recht kurz ist.)

Gings in dem Artikel nur um ostasiatische Texte? :(

Nein, aber er entstand aus dem Problem, das genau für diese beiden Anwendungen (Silbenschrift/DNA) die gängigen Methoden zur Textsuche kläglich versagen. Alle Tests zielten deshalb auch daraufhin, bei aller Optimierung keine andere Anwendungsmöglichkeit schlechter werden zu lassen. Das die dabei auch eien Farbauffrischung bekamen war zwar nicht beabsichtigt, wurde aber durchaus und lautstark begrüßt.

Selbst wenn wir den Aufwand nicht scheuten kämen wir im Deutschen wohl nicht unter rund 1,7 Bit/Zeichen (sieht man auch bei Übersetzungen vom Englischem in's Deutsche: die sind in der Regel runde 10% länger.)

naja dass ist kein Argument gegen eine bessere Kompression im Deutschen insbesondere weil die englische Orthographie viel unregelmäßiger ist als unsere und das größte Vokabular nach dem Chinesischen beinhaltet.

Meines Wissens ist das Vokabular der Chinesen nicht überdurchschnittlich groß? Die englische Orthographie ist auch nicht sonderlich unregelmäßig. Sie enstand aus zwei unterschiedlichen Stämmen, deshalb sieht das mitunter merkwürdig aus, ist aber recht logisch geblieben. Das kann man vom Deutschen nicht gerade behaupten, das ist ein aus allen Ecken und Enden zusammengewürfelter Mischmasch. Das war auch ein Grund zur Erfindung des Hochdeutschen gewesen. Und wenn sich damals nicht mal zwei Leute verkracht hätten würden wir heute französisch quasseln ;-)

so short

Christoph Zurnieden