Speichern/abrufen eine Datenstruktur

Question

Ich habe a implementiert Suffixbaum In Python, um Volltext-Suchanschlüsse zu machen, und es funktioniert wirklich gut. Aber es gibt ein Problem: Der indizierte Text kann sehr groß sein, sodass wir nicht die gesamte Struktur im RAM haben können.

BILD: Suffixbaum für das Wort BANANAS (Stellen Sie sich in meinem Szenario einen 100000 -mal größeren Baum vor).

Also ein wenig darüber nachforschen, fand ich das pickle Modul, ein großartiges Python -Modul zum "Laden" und "Dumping" -Objekten aus/in Dateien, und raten Sie mal, was? Es funktioniert wunderbar mit meiner Datenstruktur.

Also, die lange Geschichte kürzer machen: Was wäre die beste Strategie, um diese Struktur auf/aus der Festplatte zu speichern und abzurufen? Ich meine, eine Lösung könnte darin bestehen, jeden Knoten in einer Datei zu speichern und zu laden, wann immer erforderlich ist, aber dies ist nicht die beste, die zu tun sind (zu viele Festplattenzugriffe).

---

Fußnote: Obwohl ich diese Frage als mit einem Tag gekündigt habe Python, Die Programmiersprache ist nicht der wichtige Teil der Frage, die Strategie zur Speicherung/Abruf von Festplatten ist wirklich der Hauptpunkt.

Answer 1

Wenn pickle arbeitet bereits für Sie, Sie möchten sich vielleicht ansehen Zodb was über eine gewisse Funktionalität hinweg hinzufügt pickle. Als ich mich die Dokumentation ansah, sah ich diesen Absatz, der die Größenbedenken, die Sie haben, ausgehen:

Die Datenbank verschiebt Objekte frei zwischen Speicher und Speicher. Wenn ein Objekt seit einiger Zeit nicht verwendet wurde, kann es freigegeben und sein Inhalt beim nächsten Mal aus dem Speicher geladen.

Answer 2

Eine effektive Möglichkeit, eine solche Struktur zu verwalten, besteht darin, a zu verwenden Speicher-abgebildete Datei. In der Datei speichern Sie anstatt Referenzen für die Knotenzeiger zu speichern Offsets in die Datei. Sie können immer noch verwenden pickle Um die Knotendaten in einen Stream zu serialisieren, der für die Speicherung auf der Festplatte geeignet ist, möchten Sie jedoch vermeiden, Referenzen zu speichern, da die pickle Das Modul möchte Ihren gesamten Baum auf einmal einbetten (wie Sie gesehen haben).

Verwendung der mmap Modul können Sie die Datei in den Adressraum zuordnen und sie wie eine riesige Abfolge von Bytes lesen. Das Betriebssystem kümmert sich darum, tatsächlich aus der Datei zu lesen und Dateipuffer und alle Details zu verwalten.

Sie können den ersten Knoten zu Beginn der Datei speichern und Offsets haben, die auf den nächsten Knoten (en) hinweisen. Das Lesen des nächsten Knotens ist nur eine Frage des Lesens aus dem richtigen Offset in der Datei.

Der Vorteil von Dateien mit Speichermorddateien besteht darin, dass sie nicht Auf einmal in den Speicher geladen, aber nur bei Bedarf von der Festplatte gelesen. Ich habe dies (auf einem 64-Bit-Betriebssystem) mit einer 30-GB-Datei auf einem Computer mit nur 4 GB RAM gemacht, und es hat gut funktioniert.

Answer 3

Wie wäre es mit speichern es in sqlite?

Sqlite:

• hat Unterstützung für bis zu 2 Terabyte Daten,
• Unterstützt SQL -Abfragen,
• ist ein großartiger Ersatz für die Speicherung von In-App-Daten,
• Kann ~ 100.000 Besuche pro Tag unterstützen (falls sie für die durchschnittliche Webanwendung verwendet werden),

Es kann also gut sein, diese Lösung genauer zu betrachten, da sie sich als effiziente Möglichkeit erwiesen hat, Daten in Anwendungen zu speichern.

Answer 4

Vielleicht könnten Sie Cpickle und a kombinieren bsddb Datenbank, mit denen Sie Ihre eingelegten Knoten in einem von der DictionNary-ähnlichen Objekt speichern können, das auf dem Dateisystem gespeichert wird. So können Sie die Datenbank später laden und mit wirklich guten Leistungen von den Knoten erhalten, die Sie benötigen.

Auf sehr einfache Weise:

import bsddb
import cPickle

db = bsddb.btopen('/tmp/nodes.db', 'c')
def store_node(node, key, db):
    db[key] = cPickle.dumps(node)

def get_node(key, db):
    return cPickle.loads(db[key])

Answer 5

Versuche a komprimiert Suffix Baum stattdessen.

Die Hauptidee ist, dass Sie anstatt viele Knoten mit 1 Zeichen zu haben, sie in 1 Knoten mehrerer Zeichen verdichten können, wodurch zusätzliche Knoten gespeichert werden.

Dieser Link hier (http://www.cs.sunysb.edu/~algorith/implement/suds/implement.shtml) sagt, Sie können einen 160 -MB -Suffixbaum in 33 MB komprimierte Suffixbaum umwandeln. Ein ziemlicher Gewinn.

Diese komprimierten Bäume werden für genetische Substring -Matching an riesigen Saiten verwendet. Früher habe ich mit einem Suffixbaum keinen Gedächtnis mehr ausgelöst, aber nachdem ich ihn komprimiert hatte, verschwand der Auslöser.

Ich wünschte, ich könnte einen unbezahlten Artikel finden, der die Implementierung besser erklärt. (http://dl.acm.org/citation.cfm?id=1768593)