Hallo Daniela,

ich hab jetzt die Ruhe mitzurechnen ...

Nein, das würde einen zusätzlichen Join bedeuten, zudem müsste eine Referenz bei uns wohl 8 Byte gross sein. Es bedeutet also speicherplatzmässig kaum Gewinn.

verstehe ich nicht, verstehe wohl auch zu wenig von DBs ...

Du willst eine Matrix aus Schlüsselwörtern und Postings aufbauen. Das bedeutet 3 Tabellen, eine mit den Schlüsselwörtern, eine mit den Postings und eine die verlinkt.

verstehe wohl auch zu wenig von DBs, eine verlinkende Struktur der Form

Schlüsselwort -> (*posting1, *posting2, *posting3, ...)

wäre m.E. speichereffizient und ausreichend.

Wir haben aber sehr viele Postings und sehr viele Schlüsselwörter, das bedeutet auch entsprechend grosse IDs um die beiden zu verlinken. Nehmen wir jetzt doch mal 4 Byte grosse IDs wobei ich denke das es eng werden könnte. Du hast jetzt 4 Byte in der Schlüsselworttabelle und nochmal 2 * 4 in der für die Postings. Macht allermindestens 8 Byte pro Zelle in deiner Matrix.

Zusätzlich noch jeweils die erste Spalte und die erste Zeile mit den Postings resp den Schlüsselwörtern drin.

In der Betrachtung kann man IMHO diese ruhig Unterschlagen (linear statt quadratisch).

Du legst also lauter Paare (wort,posting) ab???

Paare ja, aber (wort, link auf posting). 8 Byte würden nur für Links draufgehen, sicherheitshalber bei grösseren IDs 16, das wären 8 resp 16 Buchstaben.

verstehe ich nicht, aktuell reichen 32bit locker aus um die Postings (zumindest eines Jahres) zu nummerieren.

Das ist nicht wirklich viel unter der durchschnittlichen Wortlänge. Dafür dann noch einen zusätzlichen Join... Ich denke nicht dass das ein guter Tausch wäre die ID zu benutzen anstelle dem Wort direkt.

Ein Hasharray kann erst recht nicht zwischen Gross- und Kleinschreibung unterscheiden.

Deswegen ja Stichwörter nur in klein und casesensitiv in der 2. Stufe abklären. (hei ich soll deine sourcen lesen und du ließt nicht meine Postings? ;)

Damit sparst du zwar Speicherplatz in deiner Version mit Links, nicht aber wenn du direkt das Wort benutzt. Die zweite Stufe der Suche hinzuschalten ist aber sehr teuer, vorallem da du die Datenbank auch einfach einen zusätzlichen Index auf UPPER(wort) legen lassen könntest. Ok, das braucht wieder Speicherplatz.

Natürlich ist die 2 Stufe teuer, die Frage ist wie man am effizientesten die 2 Stufe abkürzt. Effizient hieße dabei am besten i m Schritt 1 nur im  RAM zu suchen und möglichst wenig unötige Treffer in der 2. Stufe zu haben.

Ich gehe von der Annahme aus das:
1. Die allermeisten sowieso kaum casesensitive suchen.
2. Die meisten eine ausführliche Anzeige wollen, also sowieso auf die Platte zugegriffen wird.
3. Zuviele Leute in den Posts eine unsaubere Klein/Großschreibung haben.

Also lieber die Anzahl der Schlüsselwörter halbieren um damit möglichst viele ins RAM zu bekommen.

Das zurückführen eines Wortes auf seine lower()-Variante kann man übrigens auch als primitive und effiziente Hashfunktion interpretieren.

Dazu kommt noch, das eine Hashtabelle um effizient zu sein eigentlich komplett im Speicher gehalten werden muss.

IMHO machbar.

IMHO unmöglich. In der Hashtabelle brauchst du alle Worte. Mein Duden hat 120000 Worte drin, nehmen wir mal  an, so viele Worte haben wir auch (wir haben ja auch noch falsch geschriebene Worte, Dialekte und Fremdsprachige).

Das ist korrekt, auch stehen viele Wörter nicht im Duden. Es macht aber keinen Sinn jede Buchstabenkombination gleich zu behandeln, da auch viele Verschreiber auftauchen. Man optimiert doch auf den Normalfall und nicht auf den Worst-Case, den Aufwand des letzteren sollte man nur vernünftig beschränken, damit die Algo nicht im Nirwana verschwindet.

Mal ein pragmatischer Ansatz:

Das normale Vokabular eines Menschen liegt selten über 60000 Wörter,
wenn wir die häufigsten 65536 Wörter des Archivs (ohne Stoppwörter) in einen optimierten² RAM-Hash legen, wäre das bereits sehr effizient und würde auch bereits mit "normaler" Hardware funktionieren.

Nur in dem Fall, dass eine Dublette eines selteneren Wortes vorliegt müßte dann ein Plattenzugriff erfolgen. In den 65536 zugehörigen Files könnten dann die Dubletten wieder organisiert sein (eventuell wieder Hashes oder Binärbaum oder ne simple Liste).

Plattenzugrife müssen in der Suche sowieso erfolgen, die paar mehr die  nur im Falle seltener Wörter vorkämen fallen kaum ins Gewicht. Für die Belange der Archivsuche reicht das IMHO allemal, und man ist von Hardwareanbietern unabhängig.

Um diese Datenstruktur dann zu pflegen reicht es dann diese Files upzudaten.

Wenn man _noch_ effizienter arbeiten will, wäre es sinnvoll eine Statistik der am häufigsten gesuchten Wörter zu erstellen und diese zusätzlich im RAM vorzuhalten. (javascript, frame, ...)

Wo ich dir recht gebe ist, dass eine DB mir einige Kopfschmerzen über updateintervalle, konsistenz, transaktionssicherheit, usw. erspart.

PS: Kann man das Konzept (nicht die sourcen) irgendwo nachlesen,
... zum schlauer werden nicht zum meckern.

Aktuell gibt es nichts öffentlich verlinktes, nein. Ich werde es die Tage mal nachholen, kann aber noch dauern.

Lass dir wegen mir ruhig Zeit, ich will nur meine DB Dummheit veruntiefen...

Tschau
 rolf

²wobei ich nicht weiß wie Laufzeiteffektiv diese optimalen Hashes sind. Für die Bedürfnisse des Forums wären auch Hashfkten interessant die typische Tippfehler glätten. Neben der Großschreibung machen weggefallene und verdrehte Buchstaben (also Buhcstaben) das Gros aus.
Wenn also "simpel", "Simple", "simple", "simpl" auf den gleichen Hashwert abgebildet werden, wär das sogar ein Vorteil. Filtern könnte man noch sehr effizient im 2. Schritt und könnte zusätzlich noch eine Ähnlichkeitssuche wie bei google anbieten ("meinten sie etwa ...")

Habe so eine Fkt schon irgendwo gesehen, beruhte AFAIK darauf dass jeder Buchstabe mit seinem Vorgänger (und Nachfolger?) addiert wurde, oder so. Das würde auch zu dem Ansatz passen die Häufigkeit von Bi- und Trigrammen (2er und 3er Buchstabengruppen) im Archiv³ heranzuziehen, um einen möglichst gut balancierten Hash zu basteln.

Die Königsfrage bleibt dann: Wie suche ich effektiv Teilstrings in den Schlüsselwörtern? Denn viele Leute werden leider nicht die Option "eigenständige Worte[*]" aktivieren.

³wohlgemerkt nicht im Duden, weil wir hier sowieso eine eigene Subsprache haben.

³ ähm ich bin selbst kein Held der Rechtschreibung und diesbezüglich sehr liberal/ignorant, aber sollte das nicht "Begriffe als eigenständige _Wörter_ suchen" heißen? "Worte" sind sowas ähnliches wie Phrasen und Gedanken ("die Worte des großen Vorsitzenden" ...)und bestehen aus Wörtern.