Hi,

Jaja, Diplomingenieur, gell!?! ;)

Nein, noch viel weiter weg, ganz andere Fakultät.

Grundschullehramt Deutsch/Heimatkunde oder vielleicht Körperpflege an der TU Darmstadt? *fg*

Komm Du mir mal unter die Faust^WFinger!
Meint der doch glatt, ich wär' Grundschullehrer!
Seh' ich etwa so aus?
Ts, ts, ts!
;-)

Ja, das ist mir auch aufgefallen. Mir ist sogar keine einzige bekannt, die tatsächlich berechnet wurde. Weder a priori noch a posteriori.

Algorithmisch bekommt man halt nur einen Pseudozufall hin...

Ja genau, und denn sollte man doch genau berechnen können, oder?

Hmm, nicht meine Baustelle ...

Schad'!
Da hat man mal eine Mathematiker an der Hand ... ;-)

aber man kann sicher berechnen, dass die Verteilung einigermaßen "gut" ist. Um z.B. im Falle von Hashes Kollisionen zu vermeiden, sollte sich die erzeugte Folge von Zufallszahlen aber nicht wiederholen, dass ist bei algorithmischen Generatoren IMHO kaum zu leisten. Selbst wenn man echte physikalische Zufallszahlen als Saat einbindet, bleibt das Problem, dass deren Menge in einem endlichen Speicher auch nur endlich sei kann, und man deswegen wiederholen muss.

Man kann sie aber erstaunlich stark verdünnen und so auch mit sehr wenig echtem Zufall (z.B. thermisches Rauschen der Soundkarteneingänge) erfolgreich füttern.
Denn es gilt ja die Entropie
E = -p(0) log(p(0)) - p(1) log(p1)
also kann man mit einer anderen unabhängigen(!) Folge und Modulko-2 Addition (XOR) eine andere Folge herstellen mit (der Übersichtlichkeit halber mit x=p(0) und 1-x=p(1))
E_1 - E_2 = -(x^2 + (1-x)^2) log(x^2 + (1-x)^2)
            -2x(1-x) log(2x(1-x))
            +x log(x) + (1-x) log(1-x)

(Au Mann, na hoffentlich stimmt da auch alles, bitte um evt Korrektur)

http://de.wikipedia.org/wiki/Zufallsgenerator

Wenn wir da weiterdenken, streifen wir aber schon Philosophie und Physik, und streiten bald über Einsteins "Gott würfelt nicht".

Würde ichmich nihct daruf einlassen, ich bin zum Schluß gekommen, das das nicht nur nicht entscheidbar ist sondern zudem auch völlig egal. Ist auch nur ein Ding vorherbestimmt gibt es eh keinen freien Willen, gibt es jedoch eine freien Willen ist auch nichts vorherbestimmt.

"A Bloom filter with 1% error and an optimal value of m, on the other hand, requires only about 9.6 bits per element" http://en.wikipedia.org/wiki/Bloom_filter#Space_and_time_advantages

Ich sag mal mit durchschnittlich 9.6 Bits kodiere ich die ganze Postingliste mit 0% Fehler. (diesmal bitte keine Bierkiste :)

1% ist aber recht viel, ein Promille ist da schon realistischer. Kostet aber natürlich auch nicht viel mehr pro Element, das ist wohl wahr. (0% ist sehr schwierig, da müßten nicht nur alle Hashfunktion minimal perfekt sein, sondern auch alle Permutationen.)
Ah, BTW: habe da 'was gefunden (zum Thema: "Was es nicht so alles im Netz zu finden gibt"): http://www.cc.gatech.edu/fac/Pete.Manolios/bloom-filters/calculator.html
Und ich Idiot fummel hier mit Stift, Papier und Taschenrechner rum ;-)

Und ob das bei deinem Caching hilft?

Schau mal 400 gecachte Begriffe a ~10 Buchstaben
=> 4 KB ~ gzipt 400 B , maximal 800 B.

400 *9.6 bits ~ 460 Bytes

Aber wie gesagt: 0% gibt's hier nur mit minimal perfektem Hash. Und dann kannst Du Dir die Mühe mit dem Bloomfilter eh sparen und gleich eine normale Hastabelle nehmen und als fertiges Javascript-Array mitgeben.
Mmh ...
Auch keine schlechte Idee.
Clientseitig ein Javascript-Array, das die Suchworte als Strings aufnimmt, das wären bei angenommen 10 Buchstaben (Oktets, bei Multibitzeichensätzen enstpr anpassen) rund 4.000 Oktets plus 400*Hashwert (2^16 reicht, das sind zwei Oktets, drei bei Base64, macht 1.200 Oktets) sind bei angenommen Oktets=Byte runde fünf Kilobyte. Da könnte man das sogar ganz einfach machen und den Server gar nicht mehr belasten und direkt auf Pfade mappen. Macht dann vielleicht 20 KiB und da es einfache Buchstaben sind, läßt es sich hervorragend zippen und wenn da nur nachgeladen wird, wenn Javascript eingeschaltet ist (die üblichen Tricks halt), dann könnte man einen wirtschaftlichen Nutzen erwarten.
Man könnte evt sogar ein paar Spielereien mit xmlHttpRequest() anstellen.

und zippen kann wg der Entropie auch nix helfen.

Nein, tut mir leid, _so_ leicht führst Du mich nicht auf's Glatteis, ich hab' schon bemerkt, das Du hier die Informationsbits _netto_ zugrunde gelegt hast ;-)

Bin verwirrt, willst du die Daten in JS nur in Base64 halten und die algorithmen daran anpassen, oder sollen die Daten jedesmal konvertiert werden?

Würden jedesmal konvertiert werden. "Jedesmal" ist auf dem Server "nach jedem Update des Archivs" und nur auf dem Client wirklich jedesmal. Dürfte aber deutlich billiger sein als mühseliges Anpassen der Hashfunktionen

also auf meinem P2/330 MHZ funktioniert MD5 so fix, dass es auch auf einem P1 kaum einen User stören sollte.

Und wer hat auch noch so ein altes Dingen ;-)

Das käme dann wieder auf eine statistische Auswertung der Suchbegriffe an.

tja ich bleib dabei eine "optimale" Lösung müßte mit n-grammen arbeiten.

Naja, wollen's wegen der Anführungstriche einmal so annehmen.

Weiß man eigentlich wie google es macht?

Das erfährts Du nur mit 50%+1 an stimmberechtigten Aktien ;-)
Aber im Ernst: da ist natürlich viel Gehrinschmalz reingesteckt worden, aber im Grunde kochen die auch nur mit Wasser: massivem Hardwareeinsatz.
Das Gebiet "Suche" ist derart gut bekannt, das es für weiter signifikante Fortschritte der hellsten Köpfe bedarf. Deren Auswahl unter den Bewerbern soll _extrem_ scharf sein, einige berichteten von über 20 Interviews und wurden dann doch nicht genommen. Einzige Alternative ist also massiver Hardwareeinsatz.

BTW: Würde google anbieten suchergebnisse nach Anchors zu gliedern, bräuchten wir hier keine eigene Suchmaschine...

Wenn man denen das bezahlt machen die das sicherlich gerne.

so short

Christoph Zurnieden