Speichern einer Trie auf die Festplatte

Question

Das klingt wie eine einfache Frage, aber ich weiß nicht, wie für ihre Antwort zu suchen.

Ich habe eine Trie-Implementierung in C #, die über 80K Wörter aus einem Wörterbuch-Datei gespeichert werden. Es dauert eine ganze Weile, alle diese Worte laden (mehr als 5 Minuten). Ich frage mich, was ist der beste Weg, um „anhalten“, diese Daten also muss ich alle Worte nicht neu geladen, jedesmal wenn ich die Anwendung zu starten?

Danke.

Answer 1

Wie alle anderen Performance-Probleme, die ideale Lösung aus Profilierungs Ihre aktuelle Lösung und anderen Kandidatenlösungen folgen, dass Sie kommen mit. Wo ist der Engpass? Die I / O? Lexing den Text? Bilden Sie die Links in der Trie? Wird schwer sein, ein zu konkretisieren Vorschlag ohne Ihre Leistungsziele zu wissen, die Art der Trie-Nutzung und Engpässe derzeit vorhanden ist.

Issues zu beachten:

1. Speicherformat: Text? Binary?
2. persistente Daten: Die gesamte Struktur des Trie (beispielsweise als XML) oder nur eine Liste von Worten, die sich auf Laufzeitcode sie in die richtige Position in der Datenstruktur zu drücken? Was ist das Markup Daten Verhältnis? Wie schwer ist es zu analysieren?
3. Lagerort: DB / flat-file / ...
4. Incremental Laden: Mögliche

Eine mögliche Strategie: Erstellen und eine ‚am häufigsten verwendeten Wörter‘ Wörterbuch bestehen mit dem 1000 (oder so) der am häufigsten verwendeten Wörter. Legen Sie diese Worte in die Trie auf Start-up, und laichen die Belastung des Full-Wörterbuch auf einem anderen Thread; schrittweise Zugabe zu dem erzeugten Trie als neue Wörter gelesen werden.

• Pros:. Benutzer werden sehen, schnelle Startzeit
• Nachteile: Könnte erfordern verkanten Synchronisation, Benutzer sieht ein unvollständige Trie bis Beladung vollständig abgeschlossen. Dies kann oder kann nicht ein Hemmschuh sein, je nachdem, was die Trie für verwendet wird.

Answer 2

I Refactoring vor kurzem eine ähnliche Datenstruktur, aufgrund zu geringer Leistung und langsame Serialisierung / Deserialisierung mal.

war meine Lösung die Trie ganz und ging mit nativen .NET-Sammlungen verschrotten - Wörterbücher und Lookups.

Ich arbeite über 400k Wörter mit. Aus dem Gedächtnis dauert es etwa 5 Sekunden, um die Datenstruktur aufzubauen, die durch eine Reihe von Wörterbüchern und Lookups indiziert eine Liste von Objekten ist.

• Die oberste Ebene der Struktur ist ein Dictionary<int, var>, wo der Schlüssel n - die Anzahl der Buchstaben in der Suchbegriff.
• Jeder Wert in der Wörterbuch ist ein Lookup<string, string>, wo der Schlüssel ist eine Zeichenfolge mit n Buchstaben, und der Wert wird alle Zeichenfolgen, die mit dieser Zeichenkette beginnen. z für Schlüssel ‚st‘ Werte sein könnten 'Start', 'Stop' und 'String'.

Um die Datenstruktur erstelle ich einfach Iterierte über die gesamte Liste von Wörtern für i = 1 bis maxlength für jedes i einen Lookup aller verschiedenen ‚beginnt mit‘ Strings zu erstellen. Stecken Sie diese in den Top-Level-Wörterbuch und du bist fertig.

Dies beseitigt die Notwendigkeit für eine maßgeschneiderte trie. Ich fand die Leistungsdifferenz (Suchzeit) vernachlässigbare zu sein, aber die Geschwindigkeit des Ladens zu enorm begünstigt mein Design (nicht zu erwähnen, Einfachheit und Wartbarkeit mit einfachen .NET-Typen).

Answer 3

würde ich serialisiert es nur in der alten MFC binär. Grundsätzlich ist das Lesen / Schreiben über so schnell wie möglich sein sollte, und das einzige, was ich ist links mit zuteilt und die Struktur bei der Eingabe der Initialisierung, die Sie müssen auf jeden Fall tun.

Das heißt, ein Knoten des Trie-Serialisierung, Sie dies tun:

Read/Write number N of subnodes
For each subnode
  If reading, allocate a subnode in this node
  Read/Write the character for the subnode
  Serialize the subnode
End

Edit: Gerade wieder lesen Ihre Frage, und Sie möchten die Trie von Grund auf aus der Wortliste bauen? Wie bereits gesagt, Profil, aber nicht nur mit jedem alten Profiler. Sie haben nicht alle Ihr Problem finden. Hier ist, was ich tue. die Zeit, soll es die Datei und die Zeit, um die Struktur zu schaffen nimmt zu lesen braucht nicht viel mehr als die Zeit in Anspruch nimmt.