Stellen Sie sich vor, wir haben einen Algorithmus, der einen hypothetisch langen Schlüsselstrom erhält. Es erzeugt dann einen Wert zwischen 0 und 1 für jeden Schlüssel, wie wir ihn verarbeiten, für den späteren Abruf. Der Eingabesatz ist groß genug, dass wir es uns nicht leisten können, für jeden Schlüssel einen Wert zu speichern. Die werterzeugende Regel ist über Schlüssel hinweg unabhängig.
Nehmen wir nun an, dass wir Fehler bei der posterioren Suche tolerieren können, aber den Unterschied zwischen abgerufenen und ursprünglichen Werten immer noch minimieren möchten (dh asymptotisch über viele zufällige Abfragen).
Wenn der ursprüngliche Wert für einen bestimmten Schlüssel beispielsweise 0,008 war, ist das Abrufen von 0,06 viel besser als das Abrufen von 0,6.
Mit welchen Datenstrukturen oder Algorithmen können wir dieses Problem angehen?
Bloom-Filter sind die nächste Datenstruktur, die ich mir vorstellen kann. Man könnte den Ausgabebereich quantisieren, einen Bloom-Filter für jeden Bucket verwenden und irgendwie ihre Ausgabe zum Abrufzeitpunkt kombinieren, um den wahrscheinlichsten Wert zu schätzen. Bevor ich mit diesem Pfad fortfahre und das Rad neu erfinde, gibt es bekannte Datenstrukturen, Algorithmen, theoretische oder praktische Ansätze, um dieses Problem anzugehen?
Ich suche idealerweise nach einer Lösung, mit der der Kompromiss zwischen Platz- und Fehlerraten parametrisiert werden kann.
Vielleicht eine Variante des Bloom-Filters namens Kompakt Approximator : Wie ein bloßer Filter, aber verallgemeinert also sind die Einträge Werte aus einem Gitter. Dieses Gitter schwebt hier einfach zwischen 0 und 1 (es hat mehr Struktur als nur ein Gitter zu sein, aber es genügt den Anforderungen) oder wie auch immer Sie diese Zahlen speichern.
Ein Update ersetzt die relevanten Einträge durch das Maximum zwischen dem Wert und dem Wert, der gespeichert wird. Eine Abfrage berechnet das Minimum aller relevanten Einträge (Beispiele unten). Die Ergebnisse können den wahren Wert nur überschätzen. Indem Sie die Reihenfolge umkehren (min und max tauschen und auf 1 statt auf 0 initialisieren), können Sie eine Unterschätzung erhalten, indem Sie ein Intervall angeben, das den wahren Wert enthält.
Wenn Sie zum Beispiel die ersten approximierten (Überschätzungen) verwenden, sieht das Eingeben einer Zahl folgendermaßen aus:
%Vor%Und die Überschätzung sieht so aus:
%Vor%Tags und Links algorithm java probability data-structures bloom-filter