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.

Ganz deiner Meinung, höchstwahrscheinlich die alte 10% zu 90%
Regel. (da gabs auch so ne empirische Untersuchung von Linguisten (?), das Sprachen allgemein dieser Regel genügen)

2^16 war nur ne Hausnummer mit der sich gut rechen läßt...

Aber wahrscheinlich macht alleine schon ein Cache der letzten Abfragen einer Session auch sehr viel sinn, weil die Querys eines Nutzers oft sukzessive wachsen.

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.

Wieso, es reicht doch die Referenz auf die Liste der Postings eines Begriffes zu cachen, schließlich müssen diese wowieso ständig geupdatet werden...

Vermutlich denke ich mal wieder zu sehr in meinem Modell, da Daniela keine Listen von Referenzen baut.

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.

Ja aber man muss für eine Zukunftsprognose den Postinganstieg in Relation mit dem Mooreschem Gesetz sehen. Und ich sehe mittlerweile eine Abflachung der Archivkurve.

Das sie überhaupt so lange durchgehalten hat, läßt einen den Hut vor dem Programmierer ziehen!

Dito :) BTW auch an die Programmierer der RegExp die als hocheffektive Automaten realisiert wurden.

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 halte es aus Projektsicht nicht für sinnvoll Technologien zu mischen, der Ansatz über eine DB zu gehen ist schon vom Total Cost of Ownership her korrekt, insbesondere bei der Wartung hochspezialisierter Algorithmen.

Alleine was mir zu denken gibt, sind die Probleme aus den Hardwareanforderungen. Mein Credo ist es das der Algo der Maschine anzupassen sein muss und nicht umgekehrt...

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

Letzteres, hatte auch bereits den Fachbegriff "Offenes Hashing" dafür refrenziert http://de.wikipedia.org/wiki/Hash-Funktion#Offenes_Hashing
aber das geht in diesem Thread auch schon mal verloren.

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?

weil ich zum sekundären Hash die Information zur Hashfkt mit ablegen muss, das kann mitunter teuer werden.

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.

Ahhh, toucher, dann hast du wenigstens deine "Gigabit-Schlappe " gerächt. ;)

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.

ach gottchen, das bisschen shift und maskieren krieg ich hin.

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.

wieso ist die Tabelle im RAM doppelt so groß wie vermutet?
Im übrigen ist 16 nur ne Hausnummer die korrigiert werden kann.

Noch ein Problem: die Hashfunktion müßte bijektiv sein bzw Du müßtest den Suchbegriff mitgeben.

Hä? Für einen Hash brauche ich den Suchbegriff doch immer, um auf Kollision zu checken, oder?

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.

Was meinst du mit vollständig? Wenn ich erst einen extra Cache
durchsuche ist das eine Suche mehr, die jedesmal zu buche
schlägt. Bei dieser Methode fällt der Cachewert während der einen Suche selbst quasi als Abfallprodukt an.

"Obere" und "untere" Bits heißen auch "most signifcant bit(s)" respektive "least significant bit(s)" und das nicht ohne Grund.

Grummel, letztendlich ist es egal wieviele und welche Bits ich für die eine  RAM-Tabelle nehme. Wir haben einen 32 dimensionalen Würfel den wir beliebig drehen und projezieren können.

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

Die Hashfkt soll es aber erlauben. Jetzt mal ein theoretischer Ansatz, hätte ich einen idealen Zufallsgenerator (z.B. Schrödingers Katze ;) mit dem ich die Werte der Hashfkt einmal ermittle und in eine Tabelle schriebe -ohne Duplikate-, dann hätte diese Fkt so ziemlich die gewünschte Eigenschaft über alle Bits zufälig zu sein.

OK, theoretisch, aber über ne rekursive Definition muss sich doch sowas basteln lassen, oder !?!

Sieht man am besten mit einem LKG-Zufallsgenerator.

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

och bitte, die Source einer ungeeigneten Hashfkt schließt aber nicht die Existenz einer geigneten aus. (Sorry, bis ich den Code durchgearbeit habe, inklusive Theorie, ist der Thread im Archiv, deswegen später mehr ...)

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.

OK allgemein nicht ...

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.

Perfekt ist wohl zuviel verlangt, eine die die Eigenschaften der Sprache nutzt wäre schon nett.

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.

Ok jetzt mal wieder ne Idee ins blaue: Man zerlegt ein Wort in seine ersten 2 Silben und den Rest. Für den Anfangsteil berechnet man einen möglichst kompakten Code C wie bei Huffman
über die Silbenwahrscheinlichkeit, sodass möglichst viele Bits für die Codierung des Restes verbleiben (wäre bikjektiv). Den Rest codiert man mittels einer adequaten Hashfkt H1.

Das hätte den Vorteil das je wahrscheinlicher Wörter mit 2 bestimmten Anfangssilben sind, umso mehr Bits für die Hashfkt zur Verfügung stehen, sodass möglichst wenige Kollisionen entstehen können.

Wir erhalten also eine Hashfkt H2=C(S1S2)+ H1(Sn).

... ahh essen ruft ...

Tschau
 rolf