Hi,

Auf der Suche nach Material zu einer Suchmaschine mit Burrows-Wheeler-Transformation (so wirds richtig geschrieben, hat auch keienr bemerkt)

Es sah merkwürdig aus, ich konnte aber auch nicht sagen warum ;-)

http://citeseer.ist.psu.edu/cache/papers/cs/20661/http:zSzzSzmasamune.dais.is.tohoku.ac.jpzSz~sadazSzpaperszSzsadakane.pdf/sadakane00unifying.pdf#page=56

Interessanterweise benutzt er auch einen einfach verschachtelten Hash, die Idee ist also gar nicht sooo exotisch.

Hat ja auch keiner behauptet und es war auch sehr wahrscheinlich, das das schonmal jemand untersucht hatte.
Aber ohen willige Assis, die man losschicken kann nach Literatur zu suchen ist so eine Suche ein müßiges Unterfangen.
Aber da ich mich da jetzt eh durchwühlen mußte: hat mit unserem Problem und Deinem Vorschlag nur sehr am Rande etwas zu tun. Es geht darum den längsten passenden String zu finden, dafür müssen natürlich alle Fundstücke miteinander verglichen werden. Da ist so eine zweistufige Hashtabelle natürlich nicht verkehrt. Aber nutzt das auch für unseren Zweck?

Soweit ich sehe ist der Unterschied hier, dass er keine unabhängigen Funktionen braucht sondern unterschiedliche Wortbestandteile einfüttert.

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

Er spaötet dazu die Suffizes der Wörter ab, macht sich also die Struktur der Sprache zu nutze.

Äh, nein, so ein Suffix-Tree hat mit Silben im grammatikalischem Sinne nichts zu tun und wurde in diesem Fall sogar benutzt eben _weil_ die Sprache _nicht_ so einfach geparsed werden kann. Und bei DNA hast Du ja erst gar keine Worttrenner, da wird's dann doch recht heftig, vor allem da unterschiedliceh Abstände auftreten. Um Verwandschaften zu erkennen muß man nach "longest common substrings" suchen. So ein LCB ist z.B. bei "aaawbbbommrjjjjtlll" und "w4o1r1t11" "wort". Ja, genau: so wie bei CSI beschrieben funktioniert es nicht und dauert vor allem nicht bloß ein paar Minuten sondern eher ein paar Tage ;-)

BTW: Habe im Netz gelesen dass bei einer Codierung bei der Wörter im ersten Schritt in Prefix, Stamm, Suffix zerlegt werden, und anschließend die n-gramme des Stammes Huffmancodiert werden, eine Kompresionsrate von gigantischen 1.5 Bits/Character der englischen Sprache erzielt werden können. WOW!

Ja, die englische Sprache läßt sich wunderbar zerlegen. Ist eine Besonderheit der englischen Sprache, das funktioniert so nirgendwo anders, höchstens noch im lateinischem o.ä. Sprachen. Zudem ist sie auch noch recht redundant auf Bitebene, da das Alphabet ein klein bisschen weniger als als 6-Bit benötigt, das japanische aber z.B. mehr als 15-Bit (soviele Zeichen werden natürlich nicht im täglichem Umgang benutzt, aber es sind wirklich einige zehntausend). Auch werden Großbuchstaben sehr selten benutzt, die Worte sind recht kurz usw. Das grammtikalische Regelwerk basiert im Englischem zum Hauptteil auf zwei Sprachen, im Deutschen sind es da schon erheblich mehr.
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.)

so short

Christoph Zurnieden