Effiziente Möglichkeit, Existenz in einer großen Reihe von Zeichenfolgen zu überprüfen

Question

Ich habe eine Reihe von 100 + Millionen Strings, jeder bis zu 63 Zeichen lang. Ich habe viel Speicherplatz und wenig Speicher (512 MB). Ich muss die Existenz allein abfragen und keine zusätzlichen Metadaten speichern.

Meine De-facto-Lösung ist ein BDBreetree. Gibt es Alternativen? Ich kenne Leveldb und Kyoto Cabinet, aber nicht vertraut genug, um Vorteile zu identifizieren.

Answer 1

Wenn False Positives akzeptabel sind, dann wäre eine mögliche Lösung die Verwendung eines bloom filter. Bloom-Filter sind Hash-Tabellen ähnlich, aber anstatt einen Hash-Wert zum Indizieren einer Bucket-Tabelle zu verwenden, verwendet sie mehrere Hashes, um ein Bit-Array zu indizieren. Die diesen Indizes entsprechenden Bits sind gesetzt. Um zu testen, ob sich eine Zeichenfolge im Filter befindet, wird die Zeichenfolge erneut gehasht. Wenn die entsprechenden Indizes festgelegt sind, befindet sich die Zeichenfolge im Filter.

Es speichert keine Informationen über die Zeichenfolgen, so dass es sehr wenig Speicher verwendet - aber wenn es eine Kollision zwischen zwei Zeichenfolgen gibt, ist keine Kollisionsauflösung möglich. Dies bedeutet, dass es möglicherweise falsche positive Ergebnisse gibt (weil eine Zeichenfolge, die nicht im Filter enthalten ist, auf dieselben Indizes wie eine Zeichenfolge im Filter hasht). Es kann jedoch keine falschen Negative geben; Jede Zeichenfolge, die wirklich in der Menge enthalten ist, wird im Bloom-Filter gefunden.

Es gibt eine fewPythonimplementations. Es ist auch nicht schwer, dein eigenes zu rollen; Ich erinnere mich daran, dass ich selbst einen schnell verdammten Bloom-Filter programmiert habe, indem ich bitarray s verwendet habe, die ziemlich gut gelaufen sind.

Answer 2

Sie sagten, Sie haben eine Menge Festplatten, nicht wahr? Eine Option wäre, die Zeichenfolgen als Dateinamen in verschachtelten Unterverzeichnissen zu speichern. Sie könnte entweder die Saiten direkt verwenden:

• Store "zog verwelkt" in d/r/e/w/ sears

oder durch einen Hash der Zeichenfolge zu nehmen und nach einem ähnlichen Prozess:

• MD5 (‘ zeichnete Sears ') =' f010fe6e20d12ed895c10b93b2f81c6e '
• Erstellen Sie eine leere Datei mit dem Namen f0/10/fe/6e/20d12ed895c10b93b2f81c6e.

Betrachten Sie es als eine OS-optimierte, Hash-Tabelle basierte indizierte NoSQL-Datenbank.

Side Vorteile:

• Sie können Ihren Geist zu einem späteren Zeitpunkt und Speichern von Daten in der Datei ändern.
• Sie können Ihre Datenbank mit rsync auf ein anderes System replizieren.