Hi

Aeh, ja, das hat ja keiner bestritten. Aber ich brauche in jedem Loch 8
Byte statt 4 (wenn man von 4-Byte-Pointern ausgeht), wenn ich in einer
Zelle zwei Werte speichern muss (naemlich den neuen Hash zweiter Ordnung
und den alten Wert). Das macht bei einer Tabelle mit 2^16 = 65536
Elementen dann 256KB mehr. Packe ich jedoch auch das alte Element in die
Tabelle zweiter Ordnung, mit einer _anderen_ Hashfunktion oder einer
genaueren Hash-Funktion, dann kann ich mir das sparen.

Ihr habt Probleme ... das Verfahren soll Laufzeit _und_ Speichereffizient sein, da H per Definition ins RAM passt (soll heißen wird entsprechend klein gewählt, 2^16 war nur ne Hausnummer). Die Idee ist das H im RAM die teuren Zugriffe auf die K_i möglichst reduzieren hilft, mit so großen Zellen wie vertretbar. Man kann auch ganz auf H verzichten und immer auf die Platte zugreifen (s.u.)

Die Zelle i enthalten neben den Verweis aufs K_i-Hash auf der Platte tatsächlich noch einen Wert aus K_i, um Zugriffe auf die Platte zu minimieren und funktioniert somit quasi als Cache.

Das könnte z.B. der letzte abgefragte Wert aus K_i sein, oder der häufigste. Oder beides, das hängt von der günstigsten Cachingstrategie ab, die sich nur nach empirischen Untersuchungen des Nutzerverhaltens
spekulationsfrei angeben läßt.

Verzichte ich auf Laufzeitoptimierung, kann die Zelle auch nur die Referenz auf K_i enthalten.

Wähle ich die K_i alle gleich groß (k' Bits), kann ich auch ganz auf H (h' Bits) verzichten, wenn ich sie entsprechen auf der Platte als Tabelle mit p'=h'+k' Bits organisiere. Die resultierend  Tabelle P ist dann effektiv ein Hash p' Bits und die zugehörige Fkt wäre p(w)=h(w)*2^q+k(w).

Algebraisch ist das ein sogenanntes "direktes Produkt" P = H x K.

Das h und k unabhängig sein müssen, kann man gut mit einer Analogie zu Vektorräumen motivieren. Mutipliziere ich diese, müssen die Basen auch unabhängig sein, damit die maximale Dimension erreicht wird. Sind die Basen identisch, dann ist die Dimension minimal.

Deswegen kann ich auch den umgekehrten Weg gehen und und von einer "zufälligen" Fkt p ausgehend, h und k generieren (sogenannte "direkte Zerlegung").

Wähle ich die K_i nicht immer gleich groß, spare ich zum einen Platz auf der Platte und zum anderen Reorganisationen der k-Hashes.

Algebraisch ist P dann ein "subdirektes Produkt", umgekehrt ließe
sich auch eine "subdirekte Zerlegung" einer einzigen großen Fkt p organisieren (das war mein Vorschlag, bei dem k_i mit maskierten Bits gewonnen wird)

Wozu nun der ganze Sermon:

Ich wollte zeigen das man die Ganzwortsuche sehr wohl in Hashes effektiv organsisieren kann, die auf Platte und RAM verteilt sind.

Ich denke das ist mir gelungen, PoC braucht es nicht weil logisch, meine einzige Unbekannte in diesem Spiel ist der Aufwand für geeignete Funktionen.

Sollte man es realisieren? Für die Selfsuche würde sich IMHO der Zeitgewinn zur DB nur messen aber nicht mehr wahrnehmen lassen, da alleine der HTTP/HTML Overhead die Antwortzeit dominieren wird.

mathematische Grüße
 Rolf