Benötigen Sie einen guten Überblick über prägnante Datenstrukturalgorithmen

(schon auf der Hauptseite nachgefragt , aber auch hier nach einer besseren Berichterstattung gefragt, sorry)

Da ich über prägnante Datenstrukturen Bescheid wusste, brauche ich dringend einen guten Überblick über die neuesten Entwicklungen in diesem Bereich.

Ich habe viele Artikel gegoogelt und gelesen, die ich in den Google-Ergebnissen auf Anfragen von oben gesehen habe. Ich vermute immer noch, dass ich hier etwas Wichtiges verpasst habe.

Hier sind Themen von besonderem Interesse für mich:

1. Prägnante Codierung von Binärbäumen mit effizienten Operationen zum Abrufen von Eltern, linkem / rechtem Kind und Anzahl der Elemente in einem Unterbaum.

   Die Hauptfrage lautet hier: Alle mir bekannten Ansätze setzen die in atemberaubender Reihenfolge aufgezählten Baumknoten voraus (wie in der Pionierarbeit auf diesem Gebiet Jacobson, G. J. (1988). Prägnante statische Datenstrukturen), was nicht der Fall ist für meine aufgabe geeignet erscheinen. Ich habe es mit riesigen Binärbäumen zu tun, die im Tiefenzuerst-Layout angegeben sind, und die Tiefenzuerst-Knotenindizes sind Schlüssel zu anderen Knoteneigenschaften. Das Ändern des Baum-Layouts ist also mit Kosten verbunden, die ich gerne minimieren möchte. Daher das Interesse, Verweise auf Werke zu erhalten, die andere als BF-Baumlayouts berücksichtigen.

2. Große Felder mit variabler Länge im externen Speicher. Die Arrays sind unveränderlich: Ich muss die Elemente nicht hinzufügen / löschen / bearbeiten. Die einzige Anforderung ist die Zugriffszeit für O (1) -Elemente und ein möglichst geringer Overhead, besser als ein einfacher Ansatz für Offset und Größe. Hier sind einige Statistiken zu typischen Daten für meine Aufgabe:

   typische Stückzahl - Hunderte von Millionen, bis zu Dutzenden von Milliarden;

   Etwa 30% der Artikel haben eine Länge von höchstens 1 Bit .

   40% -60% Elemente haben eine Länge von weniger als 8 Bit.

   Nur wenige Prozent der Elemente haben eine Länge zwischen 32 und 255 Bit (255 Bit sind das Limit).

   Durchschnittliche Elementlänge ~ 4 Bit +/- 1 Bit.

   Jede andere Verteilung der Artikellängen ist theoretisch möglich, aber alle praktisch interessanten Fälle weisen Statistiken auf, die den oben beschriebenen nahe kommen.

Links zu Artikeln jeglicher Komplexität, Tutorials jeglicher Unklarheit, mehr oder weniger dokumentierte C / C ++ - Bibliotheken - alles, was für Sie bei ähnlichen Aufgaben nützlich war oder was nach Ihrer Einschätzung so aussieht - all diese Dinge werden dankbar geschätzt.

Update : Ich habe vergessen, die Frage 1 zu ergänzen: Binäre Bäume, mit denen ich zu tun habe, sind unveränderlich. Ich habe keine Anforderungen, um sie zu ändern, alles, was ich brauche, ist, sie auf verschiedene Weise zu durchlaufen, immer vom Knoten zum Kind oder zum Elternteil, so dass die durchschnittlichen Kosten solcher Operationen O (1) waren.

Außerdem hat ein typischer Baum Milliarden von Knoten und sollte nicht vollständig im RAM gespeichert werden.

Ich gehe davon aus, dass Sie an prägnanten externen Speicherdatenstrukturen interessiert sind, die in der Praxis effizient sind. In diesem Fall können Sie wahrscheinlich mit ein paar grundlegenden Techniken und etwas Engineering das bekommen, was Sie wollen.

Für Bäume würde ich mit dem Lesen von Arroyuelo et al. Beginnen: Prägnante Bäume in der Praxis . Der Artikel befasst sich mit Bäumen im Hauptspeicher, aber die meisten Techniken können im externen Speicher mit ähnlichen Auswahlmöglichkeiten wie unten verwendet werden.

$\gamma$$\delta$$B$$B$

$n$$S$$n$$S[i] = 1$$i$$j$$rank(j)$

Wenn Sie den Rangindex klein halten möchten, müssen Sie die Blockgröße ziemlich groß machen (wahrscheinlich Kilobyte oder Dutzende Kilobyte), was die obige Basislösung CPU-intensiv macht. Dies kann gelöst werden, indem den auf der Festplatte gespeicherten Blöcken ein wenig Overhead hinzugefügt wird. Grundsätzlich wenden Sie dieselbe Lösung rekursiv an, so dass jeder Plattenblock eine Anzahl kleiner Blöcke sowie einen anderen Rangindex speichert. Wenn Sie den richtigen Disc-Block abgerufen haben, verwenden Sie den darin enthaltenen Rangindex, um den richtigen kleinen Block zum Decodieren zu finden, anstatt den gesamten Block zu decodieren. Mit diesem sekundären Index werden zufällige Zugriffe wahrscheinlich auch mit den schnellsten verfügbaren Solid-State-Laufwerken an die E / A gebunden.