Platzsparende In-Memory-Struktur für sortierten Text, die Präfixsuchen unterstützt

StackOverflow https://stackoverflow.com/questions/1354893

Frage

Ich habe ein Problem:Ich benötige eine platzsparende Suche nach Dateisystemdaten basierend auf dem Dateipfadpräfix.Mit anderen Worten: Präfixsuche in sortiertem Text.Probieren Sie es aus, sagen Sie, und ich dachte das Gleiche.Das Problem ist, dass Versuche ohne andere Tricks nicht platzsparend genug sind.

Ich habe eine ganze Menge Daten:

  • etwa 450 MB in einer Klartext-Liste im Unix-Format auf der Festplatte
  • etwa 8 Millionen Zeilen
  • gzip komprimiert standardmäßig auf 31 MB
  • bzip2 komprimiert standardmäßig auf 21 MB

Ich möchte nicht annähernd 450 Millionen im Speicher essen.An dieser Stelle würde ich gerne etwa 100 MB verwenden, da es in Form von Präfixen viel Redundanz gibt.

Ich verwende C# für diesen Job und eine einfache Implementierung eines Versuchs erfordert immer noch einen Blattknoten für jede Zeile in der Datei.Angesichts der Tatsache, dass jeder Blattknoten eine Art Verweis auf den letzten Textblock benötigt (32 Bit, beispielsweise ein Index in ein Array von Zeichenfolgendaten, um die Zeichenfolgenduplizierung zu minimieren) und der CLR-Objekt-Overhead 8 Byte beträgt (überprüft mit windbg/SOS). , Ich werde >96.000.000 Bytes ausgeben im strukturellen Overhead ohne jegliche Textspeicherung.

Schauen wir uns einige der statistischen Attribute der Daten an.Wenn in einem Versuch gestopft:

  • insgesamt etwa 1,1 Millionen einzigartige Textblöcke
  • Insgesamt sind es etwa 16 Millionen einzelne Blöcke auf der Festplatte in einer Textdatei
  • Die durchschnittliche Blocklänge beträgt 5,5 Zeichen, maximal 136
  • Wenn Duplikate nicht berücksichtigt werden, sind es insgesamt etwa 52 Millionen Zeichen in Blöcken
  • Interne Trie-Knoten umfassen durchschnittlich etwa 6,5 ​​Kinder mit einem Maximum von 44
  • etwa 1,8 Mio. innere Knoten.

Die Überschussrate der Blatterstellung liegt bei etwa 15 %, die Überschusserstellung an inneren Knoten liegt bei 22 % – mit Überschusserstellung meine ich Blätter und innere Knoten, die während der Versuchskonstruktion, aber nicht im letzten Versuch, im Verhältnis zur endgültigen Anzahl der Knoten jedes Typs erstellt wurden .

Hier ist eine Heap-Analyse von SOS, die angibt, wo der meiste Speicher verwendet wird:

 [MT    ]--[Count]----[   Size]-[Class                                          ]
 03563150       11         1584 System.Collections.Hashtable+bucket[]
 03561630       24         4636 System.Char[]
 03563470        8         6000 System.Byte[]
 00193558      425        74788      Free
 00984ac8    14457       462624 MiniList`1+<GetEnumerator>d__0[[StringTrie+Node]]
 03562b9c        6     11573372 System.Int32[]
*009835a0  1456066     23297056 StringTrie+InteriorNode
 035576dc        1     46292000 Dictionary`2+Entry[[String],[Int32]][]
*035341d0  1456085     69730164 System.Object[]
*03560a00  1747257     80435032 System.String
*00983a54  8052746     96632952 StringTrie+LeafNode

Der Dictionary<string,int> wird verwendet, um String-Blöcke Indizes in einem zuzuordnen List<string>, und kann nach der Trie-Erstellung verworfen werden, obwohl GC es anscheinend nicht entfernt (vor diesem Dump wurden einige explizite Sammlungen durchgeführt) – !gcroot in SOS zeigt keine Wurzeln an, aber ich gehe davon aus, dass ein späterer GC es freigeben würde.

MiniList<T> ist ein Ersatz für List<T> unter Verwendung eines genau dimensionierten (d. h.lineares Wachstum, O(n^2) Zusatzleistung) T[] um Platzverschwendung zu vermeiden;Es ist ein Werttyp und wird von verwendet InteriorNode um Kinder zu verfolgen.Das T[] wird hinzugefügt System.Object[] Haufen.

Wenn ich also die „interessanten“ Punkte (gekennzeichnet mit *), erhalte ich ungefähr 270 MB, was besser ist als Rohtext auf der Festplatte, aber immer noch nicht nahe genug an meinem Ziel.Ich dachte, dass der .NET-Objekt-Overhead zu hoch sei, und erstellte einen neuen „schlanken“ Versuch, bei dem nur Arrays vom Typ Wert zum Speichern von Daten verwendet wurden:

class SlimTrie
{
    byte[] _stringData; // UTF8-encoded, 7-bit-encoded-length prefixed string data

    // indexed by _interiorChildIndex[n].._interiorChildIndex[n]+_interiorChildCount[n]
    // Indexes interior_node_index if negative (bitwise complement),
    // leaf_node_group if positive.
    int[] _interiorChildren;

    // The interior_node_index group - all arrays use same index.
    byte[] _interiorChildCount;
    int[] _interiorChildIndex; // indexes _interiorChildren
    int[] _interiorChunk; // indexes _stringData

    // The leaf_node_index group.
    int[] _leafNodes; // indexes _stringData

    // ...
}

Diese Struktur hat die Datenmenge auf 139 Millionen reduziert und ist immer noch ein effizient durchquerbarer Versuch für schreibgeschützte Vorgänge.Und weil es so einfach ist, kann ich es ganz einfach auf der Festplatte speichern und wiederherstellen, um die Kosten für die jedesmalige Neuerstellung des Versuchs zu vermeiden.

Also, irgendwelche Vorschläge für effizientere Strukturen für die Präfixsuche als Trie?Alternative Ansätze, die ich in Betracht ziehen sollte?

War es hilfreich?

Lösung

Da es nur 1,1 Millionen Blöcke gibt, können Sie einen Block mit 24 Bit statt mit 32 Bit indizieren und dort Platz sparen.

Sie können die Stücke auch komprimieren.Vielleicht Huffman-Codierung ist eine gute Wahl.Ich würde auch die folgende Strategie ausprobieren:Anstatt ein Zeichen als Symbol zum Kodieren zu verwenden, sollten Sie Zeichenübergänge kodieren.Schauen Sie sich also nicht die Wahrscheinlichkeit an, mit der ein Zeichen auftritt, sondern die Wahrscheinlichkeit des Übergangs in a Markov-Kette wobei der Status das aktuelle Zeichen ist.

Andere Tipps

Sie können eine wissenschaftliche Arbeit zu Ihrem Problem finden Hier (Zitat der Autoren:"Experimente zeigen, dass unser Index schnelle Abfragen in einer Raumbelegung unterstützt, die nahe an dem einer erreicht wird, indem das String -Wörterbuch über GZIP, BZIP oder PPMDI komprimiert wird." - aber leider ist das Papier nur Zahlung).Ich bin mir nicht sicher, wie schwierig die Umsetzung dieser Ideen ist.Die Autoren dieses Papiers haben a Webseite Dort finden Sie auch Implementierungen (unter „Index Collection“) verschiedener komprimierte Indexalgorithmen.

Wenn Sie mit Ihrem Ansatz fortfahren möchten, schauen Sie sich unbedingt die entsprechenden Websites an Crit-Bit-Bäume Und Radixbaum.

Eine ungewöhnliche Idee:Anstatt eine Hash-Tabelle auszuprobieren.Sie hätten nur den Hash und die String-Daten im Speicher, möglicherweise komprimiert.

Oder können Sie es sich leisten, eine Seite zu lesen?Nur Hash und Dateiposition im Speicher, Rufen Sie die „Seite“ mit Zeilen ab, die mit diesem Hash übereinstimmen, vermutlich eine kleine Anzahl geordneter Zeilen, daher sehr schnelle Suche im Falle von Kollisionen.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top