Hundefutter[1]

[Christoph Zurnieden]

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>

[Reiner]

Hallo Christoph,

das muß ich mir (natürlich) ansehen.
Ich habe (wenig) Ahnung von Windows. Welchen C-Compiler nutzt Du dafür? Gäbe es Deiner Meinung nach etwas schlankes, so daß man daraus eine CD basteln könnte, die den Compiler direkt mitliefert? Oder besser schon fertig als exe (für Win)?

Ich spiele gerade mit dem Gedanken, sowas mittels SQLight zu machen.
Der Vorteil wäre, daß man eine komplette Datenbank hätte - zwar nicht Vergleichbar mit MySQL oder MSSQL, aber für ein paar selects reicht das.

Gruß
Reiner

[Christoph Zurnieden]

Oh, doch noch einer? ;-)

Hi,

das muß ich mir (natürlich) ansehen.

Nunja, viel zu sehen gibt's da noch nicht.

Ich habe (wenig) Ahnung von Windows.

Ich auch nicht, macht aber nix, Google weiß da meist Bescheid ;-)

Welchen C-Compiler nutzt Du dafür?

Ich pflege meinen C-Code normalerweise (hier nicht so ganz) nach aktuellem Standard zu schreiben, da sollte die Auswahl ziemlich frei sein. Wenn Du den GCC nicht magst, kannst Du auch den LCC-Win32 nehmen.

Gäbe es Deiner Meinung nach etwas schlankes, so daß man daraus eine CD basteln könnte, die den Compiler direkt mitliefert? Oder besser schon fertig als exe (für Win)?

Diese Nachfrage verstehe ich nicht so ganz. Das ganze soll ja dazu dienen, das man eine CD durchsuchen kann, _ohne_ zusätzliche Software, nur mit einem Browser mit eingeschaltetem Javascript.

Wenn Du das Programm selber meinst: klar kann man das als Binary vertreiben, aber Indexer gibt's wie Sand am Meer, da würde ich mir im Ernstfall einen von greifen und entspr umbauen.

Ich spiele gerade mit dem Gedanken, sowas mittels SQLight zu machen.

Dann benötigst Du aber wieder ein zusätzliches Programm!

Der Vorteil wäre, daß man eine komplette Datenbank hätte - zwar nicht Vergleichbar mit MySQL oder MSSQL, aber für ein paar selects reicht das.

Und für so ein paar SELECTs gleich eine proprietäre Lösung? Wenn es komplizierte Abfragen sind, kann man das machen, aber dann auch gleich richtig. Ansonsten ist das mit Kanonen auf Spatzen geschossen.

Wenn Du sowas brauchst solltest Du mal bei Sourceforge und Freshmeat vorbeischauen.

Z.B. auf Java-Basis:
Sehr simpel:
http://druidedb.sourceforge.net/
Weniger simpel:
http://www.sleepycat.com/products/je.shtml
Auch noch 'was:
http://sourceforge.net/projects/daffodildb/

so short

Christoph Zurnieden

[Ashura]

Hallo Christoph Zurnieden.

Wenn Du sowas brauchst solltest Du mal bei Sourceforge und Freshmeat vorbeischauen.

Hm? Warum wird die erste URL nicht verlinkt, obwohl sie der Syntax zur Verlinkung entspricht..?

Gruß, Ashura

[Christian Kruse]

你好 Ashura,

Wenn Du sowas brauchst solltest Du mal bei Sourceforge und Freshmeat vorbeischauen.

Hm? Warum wird die erste URL nicht verlinkt, obwohl sie der Syntax zur
Verlinkung entspricht..?

http// != http:// :)

再见,
CK

[Christoph Zurnieden]

Hi,

Hm? Warum wird die erste URL nicht verlinkt, obwohl sie der Syntax zur
Verlinkung entspricht..?

http// != http:// :)

Bin ich es jetzt also Schuld, das das Feld "Vorschau generieren" vorselektiert ist?
Wäre es nicht stattdessen besser gewesen, ein Feld "Darüber benachrichtigen, das irgendjemand schneller war" einzubauen?

so short

Christoph Zurnieden

PS:
Ich sehe da eine Möglichkeit "Mail bei Antwort". Wenn ihr zuviel Bandbreite habt und wisst nicht wohin damit: ich nehm' euch gerne 'was ab!
CZ

[Christoph Zurnieden]

Hi,

Hm? Warum wird die erste URL nicht verlinkt, obwohl sie der Syntax zur Verlinkung entspricht..?

Weil ich Schussel da einen Doppelpunkt vergessen habe und der Mechanismus keinerlei Fehlertoleranz aufweist ;-)

so short

Christoph Zurnieden

[Reiner]

Hi,

hast Du Bloomfilter.c mal durch gcc gejagt?
Erst meckert er wegen openssl/md5.h
Wenn ich mir das aus dem System in einen entspr. Unterordner kopiere, funktioniert es dennoch nicht. (Hinter der Zeile ist ein Kommentarende '*/', hatte das eine Bewandnis? Vergessen?).
Wenn ich es komplett auskommentiere, gehts aber auch nicht.

Kannst Du generell mal die einzelnen Funktionen erklären, d.h. ich weiß nicht, was ein Bloomfilter sind und wie das genau ineinandergreift. D.h. wenn ich Dich verstehe, sind die Programme nur dafür da, den Suchindex (also diese Hashes) zu erzeugen. Aber wie funktioniert das genauer?

Ich habe mich bemüht dahinterzusteigen, aber ich glaube, so einfach ist das nicht, oder?

Gruß
Reiner

P.S.: Das Bloomfilter.html funktioniert aber!

[Christoph Zurnieden]

»» Hi,

Hi,

hast Du Bloomfilter.c mal durch gcc gejagt?

Ja, durch 2.95.4 und 3.4.1, keinerlei Warnungen.

Erst meckert er wegen openssl/md5.h
Wenn ich mir das aus dem System in einen entspr. Unterordner kopiere, funktioniert es dennoch nicht.

Du kannst die Include-Verzeichnisse per '-I/usr/include/openssl' (nur ein Beispiel, aber da ist wirklich _kein_ Leerzeichen zwischen dem großem 'i' und dem Pfad!) einbinden. Das Gleiche funktioneirt bei Bibliotheken, nur da statt des großen 'i' ein großes 'L' (ell).

(Hinter der Zeile ist ein Kommentarende '*/', hatte das eine Bewandnis? Vergessen?).

Nein, das ist egal, da vorher der Kommentar auch geöffnet wurde.
Achso, noch 'was: Du mußt auch (unter Linux zumindest) die Math-Bibliothek und die Openssl-Bibliothek einbinden. Wie oben beim Beispiel (der GCC-3.4.1 heißt bei mir gcc3, nicht irritieren lassen) hinten das "-lm -lssl"

Wenn ich es komplett auskommentiere, gehts aber auch nicht.

Nein, denn ich benutze die MD5-Funktion aus OpenSSL.

Kannst Du generell mal die einzelnen Funktionen erklären, d.h. ich weiß nicht, was ein Bloomfilter sind und wie das genau ineinandergreift. D.h. wenn ich Dich verstehe, sind die Programme nur dafür da, den Suchindex (also diese Hashes) zu erzeugen. Aber wie funktioniert das genauer?

Der Orginalartikel ist leider nur kostenpflichtig bei ACM zu bekommen http://portal.acm.org/citation.cfm?id=362692&dl=ACM&coll=portal (Ist jetzt nicht so doll, aber nur für den einen Artikel etwas übertrieben). Was im netz so rumflirrt ist recht technisch bezieht sich alles nur auf eine Veröffentlichung. Der eine Link im meinem Code (http://www.cs.wisc.edu/~cao/papers/summary-cache/node8.html#tab:bf-config-1)führt dahin, aber die Mathematik da ist noch nicht einmal korrekt.
Ich habe das aber irgendwo einmal sehr schön beschrieben gesehen, nur wo ...
Hier bei http://www.perl.com/pub/a/2004/04/08/bloom_filters.html ist auch eine hübsche Beschreibung, aber ich hatte doch nocheine besser gefunden. Na, schau Dir erstmal die an, bei Fragen dann nochmal ... äh ... fragen halt ;-)

Ich habe mich bemüht dahinterzusteigen, aber ich glaube, so einfach ist das nicht, oder?

Doch eigentlich sehr. Ist eine der Sachen bei denen man sich mit der flachen Hand vor die Stirne haut und fragt, warum man _da_ nicht selber drauf gekommen ist. Aber man kommt da eben nicht drauf und das ist der kleine aber feine Unterschied zwischen unsereinem und Leuten wie Burton Bloom ;-)

P.S.: Das Bloomfilter.html funktioniert aber!

Die _Funktion_ ist ja auch geprüft. Wenn auch nur auf exakt diese Eingabe, wie das bei anderen Eingaben aussieht weiß ich  nicht. Auf _Fehler_ habe ich jedoch noch gar nichts getestet.

so short

Christoph Zurnieden