Datenbank bei der Überprüfung auf vorhandene Werte vermeiden

Question

Gibt es einen Weg durch Hashes oder bitweise Operatoren oder einen anderen Algorithmus, um die Verwendung der Datenbank zu vermeiden, wenn einfach nach vorher erschienenen Zeichenfolgen oder Werten gesucht wird? Angenommen, es gibt keine Möglichkeit, den gesamten Verlauf der zuvor angezeigten Strings zu speichern, es können nur wenige Informationen gespeichert werden.

Answer 1

Sie könnten BLoom-Filter interessiert sein. Sie lassen Sie nicht autoritativ sagen: "Ja, dieser Wert ist in der Menge von Interesse", aber sie lassen Sie sagen "Ja, dieser Wert ist wahrscheinlich in der Menge" vs. "nein, dieser Wert ist definitiv nicht im Set ". Für viele Situationen reicht das aus, um nützlich zu sein.

Die Funktionsweise ist:

• Sie ein Array von Booleschen Werten erstellen (das heißt von Bits). Je größer Sie sich leisten können, dieses Array zu machen, desto besser.
• Sie erstellen eine Reihe verschiedener Hash-Funktionen, die jeweils eine Eingabezeichenfolge aufnehmen und sie einem Element des Arrays zuordnen. Sie möchten, dass diese Hash-Funktionen unabhängig sind, so dass selbst wenn eine Hash-Funktion zwei Strings demselben Element zuordnet, eine andere Hash-Funktion sie wahrscheinlich anderen Elementen zuordnen wird.
• Um aufzuzeichnen, dass eine Zeichenfolge in der Gruppe ist, wenden Sie jede Ihrer Hash-Funktionen der Reihe nach an —, geben Sie eine Reihe von Elementen im Array — und Sie setzen alle zugeordneten Elemente auf TRUE.
• Um zu überprüfen, ob eine Zeichenfolge (wahrscheinlich) in der Menge ist, tun Sie das Gleiche, außer dass Sie jetzt nur die zugeordneten Elemente überprüfen, um zu sehen, ob sie TRUE sind. Wenn alle TRUE sind, dann ist die Zeichenfolge wahrscheinlich im Satz; Ansonsten ist es definitiv nicht.

Wenn Sie in diesem Ansatz interessiert sind, sehen https://en.wikipedia.org/wiki/Bloom_filter für eine detaillierte Analyse, die Sie tune in geeigneter Weise den Filter helfen kann (die Wahl der richtigen Array-Größe und Anzahl der Hash-Funktionen) nützliche Wahrscheinlichkeiten zu erhalten.