你好 LanX!,

Wir reden aneinander vorbei, anders gefragt:

Stell dir vor wir lassen die Hashes der nten Stufe weg (die
diesbezüglichen Schlüssel bleiben z.B. in der DB), und wir bauen
nur einen  "perfekten" Hash der 2^16 häufigsten Suchbegriffe auf (z.B.
mit dem Tool das Christoph erwähnte). Ist der Suchbegriff nicht im
Hash wird er dann klassisch über binärbaum in der DB gesucht.

Wäre es dann von der Gesamtperformance nicht besser, wenn in über 95%
der Fälle nur auf diesen Hash zugegriffen werden müßte?

Das war ja gar nicht die Frage, die sich entwickelt hat ;-) Die Frage,
die sich entwickelt hat, war, ob Hashes dazu geeignet sind, sehr grosse
Datenmengen zu speichern.

Natürlich hast du unter deinen Annahmen recht. Wenn das Vokabular
ähnlich stark wachsen würde wie die Zahl der Postings würde mein
Ansatz keinen Sinn machen. Dieses tut es aber IMHO nicht, weil
keine Randomfunktionen posten sondern Deutschsprecher.²

Du vergisst, dass hier viel Quelltext gepostet wird, dass hier jeden Tag
sich Leute verschreiben, etc, pp. -- ich halte die Wachstumsrate “neuer
Woerter” fuer groesser, ehrlich gesagt.

weitere Diskussion duerfte nicht viel bringen. «Du glaubst mir ja eh
nicht!»

doch ich weiß zwar ad hoc nicht wieso der Exponent des Schlüssels in
2er Schritten wachsen muß, außer das Chips so organisiert sind, aber
ich glaube dir unter deinen Annahmen.

Er muss nicht in Zweier-Potenzen wachsen, aber es ist sinnvoll, weil dann
die Genauigkeit des Schluessels sehr einfach eingestellt werden
kann (Grosser-Key & (1<<Genauigkeit)).

Wieso brauche ich für 256 Einträge 32-Bit Schlüssel???

Der hoeheren Genauigkeit wegen. Die Genauigkeit muss doch hoeher
sein als in der ersten Stufe.

Allerdings wieso könnte ich - theoretisch - nicht mit diesem
Perfekte-Hashfkt-Bastel-Tool nicht einen neuen Hash für 256
Einträge basteln??? (ausser das der overhead für die Funktion
eventuell größer ist als die Tabelle?)

1. Sind es ja keine 256 Werte, 2) duerfte es dir schwerfallen, es sei
   denn, du kannst alle Kollisionen vorhersagen.

Ehrlich gesagt ich hätte sowieso ein Problem damit für 256 Werte
einen Hash zu nehmen, deswegen sagte ich "geeignet Datenstruktur".
Diese geeignete Datenstruktur kann auch teuer sein, weil sie selten
gebraucht wird.

Das sagst du ;-) Ich denke etwas anderes. Wie gesagt, ich wette, ich habe allein in diesem Posting schon midnestens einen Recktschriebfaehlah.

再见,
 CK

Hi,

Ich meinte die häufigsten 65000 Suchbegriffe, das sind ja die Fachbegriffe.

Soviele werden das insgesamt kaum sein, vemutlich nur ein paar Tausend, wenn überhaupt, die signifikant oft nachgefragt wurden. Aber das ist ja auch nicht das Problem, das Ärgernis liegt darin, das da täglich verschieden drauf geantwortet werden muß, denn täglich wird das Archiv geupdated. Wenn die Postingfrequenz weiter in die Höhe schnellt vielleicht sogar noch öfter am Tag. Auf die gleiche Frage bekommst Du also am Montag eine andere Antwort als am Dienstag; oder am Mittwoch oder am Donnerstag oder ...

eher nicht, ich finde die alte Suche aktuell schon performant genug.

Wenn wirklich jeder vorher erstmal suchen würde, der hier eine Frage stellt, wäre sie schon jetzt am Ende. Sie war überhaupt nicht für solch einen Andrang vorgesehen. Das sie überhaupt so lange durchgehalten hat, läßt einen den Hut vor dem Programmierer ziehen!

(Der wäre dann aber getrennt von DB und Frontend, könnte also ein Drittanbieter einbauen. Du vielleicht?)

Ähm könnte ich, aber ich bin sicher die DB hat selbst konfigurierbare cachingfeatures die aus Projektsicht favorisiert würden.

Nicht rausreden, machen. Wenn's dann nach sorgfältiger Prüfung für zu leicht befunden wurde - tja, dann hast Du eben im schlimmstem Fall eine schöne Fingerübung hinter Dir. Und das ist schließlich nichts Schlechtes!

Ich glaube Christian hat Dich einfach mißverstanden. Du meintest die normale Kollisionsbehandlung durch Mehrfachhashing, oder?

wenn Mehrfachhashing genestete Hashes sind, ja!

Als "genestet" kann man die eigentlich nicht unbedingt beschreiben? Aber gut, ich erklär's einfach mal in groben Zügen und Du sagst dann, ob Du genau das gemeint hast oder nicht:

Wenn beim Hashing eine Kollision stattfindet kann man da grundsätzlich auf zwei verschiedene Arten drangehen:

1. ein anderes unbelegtes Loch suchen
2. alles in ein Loch quetschen

Um ein anderes unbelegtes Loch zu finden kann ich verschiedene Algorithmen anwenden: mehr oder weniger willkürlich nach links und rechts schauen, ob es da 'was Leeres gibt, oder völlig zufällig ein Loch auswählen. Mehrfachhashing nutzt die letztgenannte Methode, in dem sie einfach einen zweiten Hash ansetzt. Wird von der ersten Hashfunktion für die Eingabe "foo" das Loch 22 ausgewählt, wird von der zweiten Hashfunktion vielleicht das Loch 44 ausgegeben.

Die unmengen an Hashfkt habe ich schon als Bottleneck erkannt, bin davon ausgegangen dass sie einfach nur selten gebraucht werden.

Warum gehst Du davon aus?

OK, angenommen ich nehme eine für die deutsche Sprache gute Hashfkt die 32 Bit zB \xABCD liefert.

Das sind nur 16 Bit. Aber egal, ich weiß, was Du meinst.

Wenn ich die oberen 16 bits \xAB nehme könnte ich locker eine Tabelle im RAM adressieren.

Kommt auf die Architektur und das OS an. Normalerweise sind aber 32 bzw 64 Bit dazu nötig. Aber auch hier: egal, ich weiß, was Du meinst.

Von dort könnte ich nun eine weitere Tabelle die auf der Platte liegt referenzieren die ich mit den unteren 16 bit  \xCD ansprechen ohne eine neue Hashfkt zu nehmen.

Damit hättest Du dann rein theoretisch 2^16*2^16 = 2^(16+16) = 2^32 Eintragsmöglichkeiten. Nix gewonnen. Eher etwas verloren, denn die Tabelle im Ram ist doppelt so groß, wie Du vermutest, also bleiben am Ende nur noch 2^31 Eintragsmöglichkeiten mit nutzbaren Daten über. Noch ein Problem: die Hashfunktion müßte bijektiv sein bzw Du müßtest den Suchbegriff mitgeben.

In der RAM-Tabelle könnte dann auch in jeder Zelle, - quasi als Caching - die wichtigsten/häufigsten Schlüssel aus der Platten-Tabelle liegen, um einen teuren Zugriff zu vermeiden.

Nein, das bringt nur 0,0000irgendwas% plus oder minus Gewinn. Ein Caching müßte schon vollständig sein.

Gut jetzt sage ich, was hindert mich daran die untere Tabelle zu verkleinern um Speichereffizient zu sein. Angenommen es sind nur y Einträge enthalten, mit 2^(x-1)< y <2^x", dann kann ich auch eine Tabelle mit 2^x Einträgen nehmen wobei die oberen x Bits von \xCD der Schlüssel wären, und die Werte der "unteren" Bits auf die oberen Zellen projeziert werden. Ohne zu viele uneffektive Kollisionen da die ursprüngliche Hashfkt ja bereits gut war.

"Obere" und "untere" Bits heißen auch "most signifcant bit(s)" respektive "least significant bit(s)" und das nicht ohne Grund. Du kannst so einen Hash nicht einfach in der Mitte teilen, das haut einfach nicht hin. Die Entropie des Hashwertes steckt im gesammtem Hashwert, Teile davon sind höchst unterschiedlich "zufällig". Sieht man am besten mit einem LKG-Zufallsgenerator.

---snip--- #ifndef _ISOC99_SOURCE #define _ISOC99_SOURCE #endif

#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <string.h> #include <limits.h> #include <time.h>

static uint32_t seed;

/* linearer Kongruenzgenerator. Marke: Standard */ static uint32_t lkg( uint32_t a, uint32_t b, uint32_t  N){   uint32_t result=0;   result = (seed * a + b) % N;   seed = result;   return result; }

static uint32_t zufall(){

uint32_t     ret1 = 0UL;   uint32_t     ret2 = 0UL;

uint32_t      ret = 0UL;

uint8_t        *p = NULL;

/* Da wir in eineme Durchlauf nur 16 Bit      erhalten, lassen wir das 2x laufen.      32 Bit pro Anfrage sollte eine Zufallsfunktion      schon mindestens liefern./   for(int i = 0; i < 2;i++){     / Zwei aufeinanderfolgende Zahlen der Folge erzeugen. /     ret1 = lkg((uint32_t)397204094UL,(uint32_t)0UL,(uint32_t)2147483647UL);     ret2 = lkg((uint32_t)397204094UL,(uint32_t)0UL,(uint32_t)2147483647UL);     / Alle umdrehen nützt nicht viel, da die beiden        mittleren Oktets auch nicht sonderlich "gut" sind.     p = (uint8_t*)&ret1;     for(int i = 0;i < (int)sizeof(uint32_t);i++){       tmp <<= 8;       tmp |= p;       p++;     }     ret1 = tmp;/     /* Also nur die äußeren Oktets bei        der ersten Zahl austauschen. /     p = (uint8_t)&ret1;     *p     ^= *(p+3);     *(p+3) ^= *p;     *p     ^= (p+3);     / Beide Zahlen exklusiv verodern.        Durch das Umdrehen oben ist das        Resultat Endianess unabhängig falls wir        nicht gerade auf einer PDP-11 sitzen.

Zahl          = 0x11223344          Little Endian = 0x11223344          Big Endian    = 0x44332211          PDP-11        = 0x22114433

Das Problem ist bei LKGs, das die erzeugten        Zahlen in Richtung LSB immer schlechter werden.        Durch das XOR und das Umdrehen sind aber zumindest        die beiden äußeren Oktets gleich "gut".*/     ret1 ^= ret2;

/* Füllen des Returnwertes von rechts nach links */     p     = (uint8_t *)&ret1;

ret <<= i*8;     ret  |= *p;     ret <<= 8;     ret  |= (p+3);   }   return ret; } static void seed_lkg( uint32_t i){   / normalerweise kommen hier ein paar Tests      die sind aber schon in main()  */   seed = i; }

int main(int argc, char **argv){

uint32_t       tmp  = 0UL;   unsigned long count = 0, i = 0;

unsigned char *p = NULL;

seed_lkg((uint32_t)time(NULL));   if(argc > 1){     if((count = strtol(argv[1], (char **)NULL, 10)) >= ULONG_MAX/2){       fprintf(stderr,"Bitte nicht mehr als %lu, danke.\n",ULONG_MAX/2-1);       exit(EXIT_FAILURE);     }   }   else       count = 1024;

for(;i<count;i++){     tmp = zufall();     p = (unsigned char )&tmp;     printf("%c%c%c%c",(p+3),(p+2),(p+1),*p );   }   exit(EXIT_SUCCESS); } ---snap--- (Bin jetzt zu faul, auch noch Optionsparsing einzubauen. Einfach oben einmal mit und einmal ohne Bitjuggling arbeiten (einfach auskomentieren)) Tests der Ausgabe (mit Ent bzw DIEHARD und eine LCG-crack, aber sowas gibt's tatsächlich online?) mit Bitjuggling ergaben gute Werte. Unerwarteterweise keine Wiederholung nach 2^32 Zyklen! (Ich hatte aber auch nicht mehr Platz auf der Platte als für 2^32+3 Zyklen, kann durchaus sein, das sich das einen später wiederholt hat) Wenn man nicht bloß die Bytes austauscht sondern die Bits selber gut durchschüttelt, sollte das Ergebniss noch etwas besser aussehen. Mit dem Standard-LKG entsprachen die Tests dann aber wieder voll und ganz den Erwartungen. Bevor irgendjemand Unsinn damit anstellt: das ist kein kryptographisch sicherer Pseudo-Zufallsgenerator! Auch wenn er äußerlich so aussieht.

Mit anderen Worten, wenn die ursprüngliche Hashfkt mit 32 Bit eine gute Verteilung hat, dann eigentlich auch eine abgeleitete Hashfkt mit weggestrichenen Bits.

Nein, eben nicht, siehe oben.

Knackpunkt wäre es also eine gute Hashfkt mit 32 Bit für  die Selfsprache zu finden. Oder irre ich mich?

Du suchst also die perfekte Welle^WHashfunktion? Glaube nicht, das Dir das viel nützt. Das meine ich wörtlich: ich glaube nicht, das es viel nützt. Der Aufwand steht in rein gar keinem Verhältnis zum Nutzen. Selbst so "Kleinigkeiten" wie eine Rechtschreibprfüng ("Meinten sie 'Rechtschreibprüfung'"?) ist schwierig zu implementieren, sehr schwierig. Hier haut dann wieder der extrem große Umfang der Eingabemenge in's Kontor. Du könntest natürlich auch mit n-grammen arbeiten. Dann arbeitest Du aber nicht nur mit riesigen Mengen, die Du erstmal mit ein paar Regeln (welchen Regeln?) kleiner bekommen mußt, dazu kommt noch, das die Worte jedesmal gesplittet werden müssen. Ein Cache, der die Ergebnisse der häufigst gesuchten Begriffe vorhält (die erste Seite vielleicht sogar komplett) wäre natürlich nicht schlecht. Aber es würde wahrscheinlich auch nix rausreißen. Deshalb erstmal die Suche sorgfältig und ohne große Spielereien aufbauen und stabil bekommen. Wer dann noch Lust und Zeit hat, kann sich ja daran versuchen.

so short

Christoph Zurnieden