nicht angemeldet
Hallo zusammen,
nachdem ich nun schon mehrfach ungefragt meinen Senf zum Thema "Suche auf CDROM ohne extra Software" abgelassen hatte, wollte ich doch mal schauen, ob das denn überhaupt praktikabel ist, was ich da von mir gab.
Die Vorgaben:
- Standardkonformer Browser mit Javascript, dito.
- CDROM
- keine Plugins, zumindest nicht für die Suche.
Künstliche Beschränkungen für das PoC (Proof of Concept):
- Funktionstest nur auf Mozilla (1.7a)/Unix (GNU/Linux)
- 1 Byte Zeichensatz (Latin-1 um genau zu sein)
- keine Regex, kein Teilstring, keine Phrasensuche, kein Stemming
Künstliche Beschränkungen für das Endergebnis:
- maximal 2^32 Dateien auf dem Medium
- maximale Pfadlänge; 260 Zeichen
- maximale Anzahl Dateien/Verzeichnis: ca 1.000
- maximaler Load[2]: 100-150 kib
- mindest Support: IE/NN 4 auf Win-95 (also doch nix mit o.a. Standardkonformität ;-)
Insbesondere die Beschränkung auf den Load ist wichtig, der Rest sind nur Sicherheitsmargen für verschiedene Windows- und Browserversionen und ältere Macs.
Um die ganze Sache so einfach wie möglich zu halten ist wohl ein simpler "Inverted Index" (im weiteren mit InvI. abgekürzt) die günstigste Indexvariante. Der wird aber naturgemäß groß. Sehr groß. Viel zu groß für einen einfachen Browser um das Dingen komplett zu laden. Der InvI. kann aber natürlich sortiert und in kleinere Happen aufgeteilt werden. Nimmt man noch das Dateisystem als binären Baum kann man das entsprechende Teil schnell finden und damit die einzelnen Dateien klein halten. Da auch der Inhalt der Dateien sortiert ist, ist der Eintrag dort ebenfalls schnell in O(log(n)) gefunden.
Nur: das versagt natürlich kläglich bei Teilstringsuche, Regexen oder Phrasensuche. Eine lineare Suche durch alle Teildateien wäre aber zu aufwendig und würde recht lange dauern wenn der InvI. in sehr viele Teildateien gesplittet wurde. Jede Teildatei müßte schließlich erst von der CDROM/DVD geholt werden und I/O ist nunmal sehr teuer.
Um vollständige Worte auf Vorhandensein zu überprüfen wäre ein schlichter Bloomfilter einsetzbar. Da es dort keine falschen Negative gibt wäre das Ergebnis "not found" schonmal stark abkürzend. Je nach Menge der Suchworte kann der Bloomfilter aber sehr lang sein[3]. Ihn aufzuteilen ginge zwar, aber das würde dann mindestens einen I/O Zugriff erfordern und den Vorteil damit zunichte machen. Da kann man besser das CDROM einmal vergeblich aufjaulen lassen. Durch dieses Geräusch ist ja sogar ein Userfeedback gegeben und das Programm bekommt ein wenig mehr Zeit zugesprochen -- eine akustische Sanduhr sozusagen.
Setzen wir den Preis eines I/Os einmal ganz willkürlich höher als Regex oder Teilstringsuche, dann würde es sich in diesen beiden Fällen bezahlt machen.
Für die Teilstringsuche gibt es die bekannte Methode der Suffixtrees [McCreight], die allerdings sehr viel Zuwendung beansprucht [Richard]. Eine direkte Implementation für jeden einzelnen Eintrag fällt also flach.
Wenn nun aber jeder einzelne Eintrag eines Teil-InvI derart seziert wird, kommt zwar viel zusammen, jedoch sind darunter viele Doubletten. Als etwas unverschämte Vermutung: ein fertig sortierter und gereinigter Suffixbaum ist erheblich kleiner. Für die einfache Antwort auf die Frage: "Ist Teilstring in Teil-InvI enthalten, ja oder nein?" kann wieder ein Bloomfilter eingesetzt werden. Je nach Genauigkeit des Bloomfilters können die Filter mehrerer Teil-InvI zusammengefaßt werden -- es werden so vergebliche Teilstringsuchen und damit I/Os gespart.
Regexe werden etwas schwieriger, aber zumindest läßt sich bei einfachen Regexen wie z.B. "exampl*", "*foo*bar?" u.ä. die Methode der Teilstringsuche auf die zusammenhängenden Buchstabenfolgen aus dem Regex anwenden[4]. Bei Filtern ohne solche Buchstabenfolgen wie z.B. "\b[acgt].+\b" wird das naturgemäß schwieriger. Ich glaube nicht, das sich dafür effektive Methoden der Laufzeitoptimierung finden werden, das geht wohl tatsächlich nur durch lineares "Abklappern".
Da aber wohl die Wahrscheinlichkeit recht gering ist, das ein Benutzer die höheren Weihen der "Regular Expressions" bekommen hat _und_ auch noch erwartet, das das genauso schnell ist wie eine direkte Suche kann man das getrost für die kommenden kalten Wintertage aufheben.
Hier nun ein kurz und schmerzhaft zusammengepappter PoC für ein paar der oben beschriebenen Sächelchen, hauptsächlich der Versuch einer Implementation eines Bloomfilters in JS. Nein, eigentlich _nur_ der Versuch einer Implementation eines Bloomfilters in JS, aber wie heißt es so schön:"Release early and often!". Ähem ... ja ...
http://mzurnieden.bei.t-online.de/Bloomfilter-js-0.0.0.tar.bz2
(Der Server soll wohl zum Ende des Monats geschlossen werden, wollte für sowas aber nun wirklich kein Projekt bei SF aufmachen. Da liegen schon genug "Leichen" ;-)
Alles schön und gut, aber was nun meine Frage ist?
Nun, der ganze erforderliche Rest ist ja schon vorhanden, die "einzige" Arbeit wäre es daraus ein Paket zu schnüren, in das der Benutzer einfach nur vorne seine Daten reinwirft und dann hinten eine CDROM/DVD-ISO rauskommt. Würden sich dafür Abnehmer finden? Etwas platformunabhängigeres _und_ auch noch direkt ausführbares dürfte sich ja kaum finden.
Oh, diese Begeisterung! *sigh* ;-)
Zudem ist das auch noch ein Hinweis darauf, wie einfach ein "Cache der Top 500 Suchbegriffe" in das Frontend der Forumssuche einzubauen wäre >;->
so short
Christoph Zurnieden
[1] aus dem amerikanischem "to eat your own dogfood" - "das eigene Produkt selber benutzen".
"So, why didn't Sun eat it's own dogfood and used Java instead of Cobol?"
[2] Die Gesamtsumme aller Dateien, die der Browser auf einmal laden muß. Z.B. ein Javascript von 25kib + noch eines von 35kib + das Suchfenster von 20kib + das Ergebnisfenster von 15kib macht schon 95kib, da bleibt nicht mehr viel Platz für die externe Suche.
[3] für die 45378 Einträge aus /usr/dict/words, einer Fehlerrate von 0.01 und einer großzügigen Aufrundung wird der Bloomfilter gerade mal 52244 Oktets lang. Da er nochmal durch base64 o.ä. Umformung vergrößert wird, kommt die Angelegenheit insgesamt dann aber wieder hart an die Grenze der Vorgaben.
[4] Bei "exampl*" also "exampl" und bei "*foo*bar?" "foo" und "bar".
Bib:
[McCreight] E. M. McCreight. A space-economical suffix tree construction algorithm. Journal of the ACM, 23:262--272, 1976.
[Richard] Sandeep Tata Richard. Practical Suffix Tree Construction. <citeseer.ist.psu.edu/709824.html>