🎒 🌼 🤵🏾 Katzen in Kisten oder kompakte Datenstrukturen 📶 🏳️ ↕️

Bild

Was kann ich tun, wenn der Suchbaum auf den gesamten Arbeitsspeicher angewachsen ist und benachbarte Racks im Serverraum verwurzelt werden sollen? Was tun mit einem invertierten ressourcenhungrigen Index? Sollte ich mich mit der Android-Entwicklung verbinden, wenn der Benutzer "Telefonspeicher voll" erhält und die Anwendung nur die Hälfte der Ladung eines wichtigen Containers enthält?

Ist es generell möglich, die Datenstruktur so zu komprimieren, dass sie deutlich weniger Platz beansprucht, aber nicht ihre inhärenten Vorteile verliert? Damit bleibt der Zugriff auf die Hash-Tabelle schnell und der ausgeglichene Baum behält seine Eigenschaften. Ja das kannst du Hierzu erschien die Richtung der Informatik "Prägnante Datenstrukturen", die die kompakte Darstellung von Datenstrukturen erforschte. Es hat sich seit Ende der 80er Jahre weiterentwickelt und befindet sich derzeit in der Blüte von Big Data und Highload.

In der Zwischenzeit wird es einen Helden auf Habr geben, der dreimal hintereinander sprechen kann
[səkəsˈkt]?

Tür zur Welt der Kompaktheit

Eine Datenstruktur wird daher als kompakt (prägnant) betrachtet, wenn sie:

Es belegt eine Anzahl von Bits in der Nähe der informationstheoretischen Untergrenze.
Es ist kein vorheriges Auspacken für den vollen Gebrauch erforderlich.

Dies bedeutet, dass verlustfreie Komprimierungsalgorithmen nichts mit kompakten Datenstrukturen zu tun haben. Schließlich geht es darum, Daten aus einem komprimierten Zustand zur Verarbeitung wiederherzustellen.

Bekannte Mainstream-Implementierungen von Diagrammen, Hash-Tabellen und anderen Dingen sind ebenfalls nicht gut. Nehmen Sie mindestens Zeiger auf untergeordnete Elemente im Suchbaum. Sie essen anständige Orte auf: $O (MN)$ wo $M$ - die Länge des Zeigers und $N$ - die Anzahl der Knoten im Baum. Aber die prägnante Baumimplementierung ermöglicht es uns, das asymptotische Verhalten zu verbessern $2N + o (N)$ was nahe an der theoretischen Untergrenze liegt $2N - Θ (log N)$ für Holz aus $N$ Knoten. Mit Zeigerlänge $M = 8$ Byte bedeutet dies, sich von zu bewegen $O (8N)$ zu einer ganz anderen Ordnung der Asymptotik - nur $2N$ in Anbetracht dessen $o (N)$ - vernachlässigbarer Wert in Bezug auf $N$ .

Kompakte (prägnante) Datenstrukturen sind komprimierte Darstellungen für Bitvektoren, Multisets, planare Graphen und andere klassische Lieblingsstrukturen. Oft sind sie statisch, einmal gebaut und ändern sich während des Gebrauchs nicht. Es gibt Ausnahmen - prägnante Strukturen mit schnellen Operationen zum Hinzufügen und Entfernen von Elementen.

Die meisten kompakten Strukturen basieren auf dem Konzept des sogenannten kompakten indexierbaren Wörterbuchs. Dies ist ein Sonderfall einer Bitmap (Bitmap, Bitset). Die Bitmap selbst ist ideal, um zu überprüfen, ob sich Elemente in einer bestimmten Menge befinden. Wenn ein Element in einer Menge enthalten ist, wird der Bitwert an einem bestimmten Index auf 1 gesetzt. Andernfalls wird er auf 0 zurückgesetzt. Ein wichtiges Beispiel ist die Inode-Bitmap ext4, UFS und andere Unix-Dateisysteme. Es speichert Daten darüber, welche Einträge in der Inode-Tabelle belegt und welche frei sind.

Ein kompaktes indexierbares Wörterbuch ist dasselbe Bitmap, wird jedoch durch zwei Operationen ergänzt: Rang und Auswahl. Diese Operationen sind die Elefanten, auf denen die prägnante Welt ruht. Grob gesagt, Rang ist eine Zählung der Anzahl der Elemente, und Auswahl ist eine Suche nach einem Element:

$rank_x (i)$ Gibt die Anzahl der Bits zurück, die gleich sind $x$ deren Indizes liegen auf einem Segment $[0; i]$ . Als $x$ - der Wert des Bits, dann kann er ausschließlich gleich 0 oder 1 sein.
$select_x (j)$ Gibt den Index zurück $j$ bisschen gleich $x$ . Der gesunde Menschenverstand sagt, dass es keine Null gibt, es gibt nur die erste. Deshalb $ inline $ j> 0 $ inline $ : Berechnung erfolgt von eins. Außerdem, $j$ darf die Gesamtzahl der Bits im Wörterbuch nicht überschreiten $x$ .

Angenommen, wir haben ein indexierbares Wörterbuch, in dem 4 der 7 Bits gesetzt sind. Dann $rank_1$ und $select_1$ nimmt die folgenden Werte an:

Ein Beispiel für ein indexierbares Wörterbuch und eine Berechnung dafür $rank_1$ , $select_1$ .

Ein aufmerksamer Leser wird feststellen, dass select die Umkehrung des Ranges ist. Wenn $rank_1 (5) = 4$ dann $select_1 (4) = 5$ .

Jemand hatte Deja Vu beim Anblick von $rank_1 (i)$ ? Und das alles, weil diese Operation das Hamming-Gewicht verallgemeinert - die Anzahl der Zeichen ungleich Null in der Sequenz. Bei binären Sequenzen wird Hammings Gewicht auch als Popcount (Populationszahl) bezeichnet.

Rang / Auswahl gilt auch für verworfene Bits. Hier ist ein Berechnungsbeispiel $rank_0$ und $select_0$ für Bits gleich 0:

Ein Beispiel für ein kompaktes indexierbares Wörterbuch und dessen Berechnung $rank_0$ , $select_0$ .

Sah einen Baum in Bitiks

Mit diesem Wissen bauen wir einen kompakten Präfixbaum! Präfixbäume eignen sich zum Auffinden von Zeichenfolgen nach Präfix. Mit ihrer Hilfe wird häufig eine Dropdown-Liste mit Suchtipps (sjest) implementiert. Der Ansatz zur Succinctisierung des Präfixbaums ist extrem verallgemeinert und zeigt maximal alle Rosinen kompakter Strukturen. Im Gegensatz zu einem binären Baum, für den bestimmte Formeln abgeleitet werden, die das Gesamtbild stören.

Drei Methoden zur kompakten Darstellung von Bäumen sind am beliebtesten:

BP (ausgeglichene Klammern) - ausgeglichene Klammerfolgen.
DFUDS (Depth-First-Unary-Degree-Sequenz) - eine Sequenz von einheitencodierten Knoten sortiert nach Tiefensuche.
LOUDS (Level-Ordered Unary Degree Sequences) - Sequenzen von nach Level sortierten, in Einheiten kodierten Knoten.

Was ist die verdächtige logische Kette der Übersetzung von "unärem Grad" zu "einfach codiertem Knoten"? Na dann. Ein einheitlicher Grad in diesen Namen bedeutet, dass Baumknoten mit einer Folge von Einheiten nach der Anzahl der untergeordneten Knoten codiert werden, wobei im Trailer immer eine Null angegeben ist.

Diese drei Methoden zur Darstellung von Bäumen werden durch die Anwesenheit schneller Operationen vereint: Finde einen Elternteil; finde den ersten Nachkommen; finde den letzten Nachkommen; Suchen Sie den linken und rechten benachbarten Knoten. Die grundsätzliche Möglichkeit und Wirksamkeit anderer Operationen unterscheidet sich von Methode zu Methode.

Kommen wir zur Methode LOUDS. Wenn Sie es verstanden haben, wird es nicht schwierig sein, mit den beiden anderen umzugehen. Darüber hinaus feierten die LOUDS-Bäume im vergangenen Jahr ihren 30. Geburtstag! Zusätzliche nützliche Operationen für LOUDS-Bäume sind in implementiert $O (1)$ : finde die Anzahl der Nachkommen des Knotens; Berechnen Sie die Anzahl der Nachkommen des Knotens unter allen Nachkommen (erster Nachkomme, zweiter Nachkomme, $i$ th usw.); zu finden $i$ der Nachwuchs. Der Nachteil von LOUDS ist das Fehlen eines effektiven Algorithmus zum Zählen der Anzahl der Teilbaumknoten.

Das Wesentliche der Methode ist einfach: Speichern Sie die Schlüssel der Baumknoten und alle wertvollen Informationen in einem regulären Array und stellen Sie die Baumstruktur als Folge von Bits dar. Insgesamt haben wir zwei statische Strukturen. Es ist jedoch nicht erforderlich, den Baumknoten Speicher für Zeiger zuzuweisen: Die Übergänge zwischen ihnen werden mithilfe von Formeln unter aktiver Verwendung von rank / select implementiert.

Warnung, Präfixbaum:

Präfixbaum bereit zur Komprimierung mit der LOUDS-Methode.

Bereiten Sie den Baum für die Darstellung in binärer Form vor:

Befestigen Sie den Baum an der falschen Wurzel. Er wird sehr bald seine Rolle spielen.
Wir nummerieren alle Knoten des Baums, Ebene für Ebene, von links nach rechts, wie in BFS (Breitensuche). Die gefälschte Wurzel wird ignoriert und die reale Wurzel wird durch Null indiziert.
Kodieren Sie die Knoten. Der Baumknoten wird durch eine Folge von Einheiten kodiert, die direkten Nachkommen plus Null entsprechen. Wenn der Knoten vier Kinder hat, wird er als 11110 codiert, und wenn keiner - als 0. Die falsche Wurzel wird zuerst codiert. Es hat einen einzelnen Nachkommen, der Code lautet also 10.

Ein Präfixbaum mit nummerierten Knoten. Knoten sind codiert.

Beim Durchlaufen eines Baums auf Ebene wird ein kompaktes indexierbares Wörterbuch gebildet - eine Folge von Bits von codierten Knoten, die von oben nach unten und von links nach rechts geklebt werden. Wir haben eine 21-Bit-Sequenz. Übrigens heißt es LBS (LOUDS Bit String).

Kompaktes indexierbares Wörterbuch für Präfixbaum.

Der kompakte LOUDS-Präfixbaum wird erstellt. LBS für Holz mit $N$ Knoten (Fake zählt nicht) nimmt $2N + 1$ bisschen. Das Interessanteste bleibt: Formeln zum Überqueren eines Baumes werden zu einer Bitmap.

Suche nach dem ersten Kind . Übergang von einem Knoten $i$ zu seinem ersten Kindknoten wird nach der Formel ausgeführt:

$firstChild (i) = select_0 (i + 1) - i$

$i$ - Dies ist die Knotennummer auf der vorherigen Platte, die violett markiert ist.

Suchen Sie den ersten Nachkommen des Knotens mit Index 3 (den Buchstaben "a"):

$firsthild (3) = select_0 (3 + 1) - 3 = select_0 (4) - 3 = 9 - 3 = 6$

Der erste untergeordnete Knoten befindet sich am Index 6, und dies ist der Buchstabe "k". Wir wenden die Formel für die Wurzel des Baumes an:

$firstChild (0) = select_0 (0 + 1) - 0 = select_0 (1) = 1$

Wir fanden ein Blatt mit dem Index 1, dem Buchstaben „und“. Konvergiert! Es wurde klar, warum eine falsche Wurzel benötigt wurde: für die Magie der Indizierung von Knoten. Um seltsame Fehler zu vermeiden, bevor Sie zu den Nachkommen des Knotens übergehen $i$ Es wäre schön, die Anzahl dieser Nachkommen herauszufinden. Tatsächlich liefert die Formel für die Blätter des Baumes, was nicht überraschend ist, ein unzureichendes Ergebnis. Um den nächsten Nachkommen nach dem ersten zu finden, müssen Sie 1 hinzufügen. Dies ist logisch, da die Nachkommen eines Knotens immer in der Nähe sind, ohne Lücken. Wenn Sie sie durchlaufen, müssen Sie jedoch rechtzeitig anhalten und feststellen, welcher Nachkomme als letzter gilt.

Suchen Sie nach dem letzten Nachkommen eines Knotens $i$ Der Durchlauf erfolgt in zwei Schritten: Bestimmen des Index der letzten Einheit im Knotencode - es ist das, was den angegebenen Nachkommen bezeichnet; und dann den Index des Kindes selbst bestimmen:

$lastChildPos (i) = select_0 (i + 2) -1$

Nachdem der Index der letzten Einheit im Knotencode empfangen wurde, muss überprüft werden, ob das Bit an diesem Index tatsächlich gesetzt ist. Wenn nicht, dann bietet sich die Schlussfolgerung an: Dies ist ein Knoten ohne Nachkommen, ein Blatt. Wenn das Bit gesetzt ist, fahren Sie fort:

$lastChild (i) = rank_1 (lastChildPos (i) -1)$

Suchen Sie den letzten Nachkommen von Knoten 2 (den Buchstaben "k").

$lastChildPos (2) = select_0 (2 + 2) -1 = select_0 (4) -1 = 9-1 = $$

Das Bit bei Index 8 ist 1, daher ist Knoten 2 kein Blatt, und wir können den Index seines letzten untergeordneten Elements finden:

$lastChild (i) = Rang_1 (8-1) = 5$

Die Anzahl der Nachkommen. Der einfachste Weg, die Anzahl der Nachkommen zu bestimmen, besteht darin, den Index seines ersten Nachkommen vom Index des letzten Nachkommen des Knotens zu subtrahieren und 1 hinzuzufügen:

$childrenCount (i) = letztes Kind (i) - erstes Kind (i) + 1$

Angenommen, der Knoten $i$ Es gibt einen benachbarten Knoten $i + 1$ befindet sich auf der gleichen Baumebene wie $i$ . Dann die Anzahl der Nachkommen $i$ kann als Differenz zwischen den Indizes der ersten Nachkommen von Knoten definiert werden $i + 1$ und $i$ :

$childrenCount (i) = firsthild (i + 1) - firsthild (i)$

Die Nachkommen des Knotens werden ebenfalls fortlaufend nummeriert. Wenn der erste Nachkomme $i$ - Das $j$ dann der zweite - $j + 1$ und so weiter bis zum Nachkommen eines auf dieser Ebene benachbarten Knotens $i + 1$ (falls vorhanden).

Die Anzahl der Nachkommen des Blattes "und" mit Index 1 ist voraussichtlich Null:

$childrenCount (1) = (select_0 (2 + 1) - 2) - (select_0 (1 + 1) - 1) = 3 - 3 = 0$

Übergeordnete Suche nach einem Knoten $i$ organisiert durch die Formel:

$parent (i) = rank_0 (select_1 (i + 1) - 1) -1$

Wir werden es verwenden, um nach dem Elternteil von Knoten 6 (dem Buchstaben "k") zu suchen:

$parent (6) = rank_0 (select_1 (7) - 1) -1 = rank_0 (9) -1 = 3$

Dies ist Knoten 3, der Buchstabe "a".

Mit Kenntnis der Formeln für die untergeordneten und übergeordneten Indizes ist es nicht schwierig, den gesamten Baum zu durchlaufen. Das Wichtigste ist, die Verarbeitung der Randbedingungen für Wurzel und Blätter nicht zu vergessen.

Ein paar Kopeken über BP- und DFUDS-Methoden. Beide Methoden haben räumliche Asymptotik - $2N + o (N)$ Stück für Holz aus $N$ Knoten, und beide sind in der Darstellung eines Baumknotens in Form von öffnenden und schließenden Klammern ähnlich.

BP (ausgeglichene Klammern) konvertiert einen Baum in eine Folge von Klammern, ein Paar für jeden Knoten. Dazu geht der Baum in die Tiefe; Jeder Knoten wird zweimal besucht. Beim ersten Besuch wird die öffnende Klammer aufgezeichnet, beim zweiten Besuch die schließende Klammer. Dazwischen stehen Klammern von Kindern.

Es ist praktisch, die Reihenfolge der Klammern in Form einer Bitmap darzustellen, wobei 1 die öffnende Klammer und 0 die schließende Klammer ist. Alle Formeln für die Arbeit mit BP sind für eine schnelle Suche geschärft. Im Gegensatz zu LOUDS können Sie mit BP die Größe eines Teilbaums schnell berechnen und den nächsten gemeinsamen Vorfahren von zwei Knoten bestimmen. Aber finde $i$ -th Nachkomme ist viel komplizierter als in LOUDS.

DFUDS (Depth-First Unary Degree Sequence) ähnelt sowohl BP als auch LOUDS. Mit BP kombiniert es einen Baumgang in der Tiefe und seine Klammerdarstellung. Das Prinzip der Klammern ist dasselbe wie das Prinzip der Kodierung von Knoten in LOUDS. Bevor wir den Baum durchlaufen, fügen wir der Klammerfolge vorab eine öffnende Klammer hinzu. Beim Überqueren von Knoten schreiben wir dann offene Klammern entsprechend der Anzahl der Nachkommen plus eine schließende. Es stellt sich heraus, dass der Ort, an dem Nachkommen in DFUDS gespeichert werden, höher ist als der von BP. Die Berechnung der Größe des Teilbaums und die Suche nach dem nächsten gemeinsamen Vorfahren werden für ausgeführt $O (1)$ . Bestimmen Sie jedoch die Höhe des Teilbaums und suchen Sie nach dem übergeordneten Baum $j$ Levellastige Operationen für DFUDS.

Zur Verdeutlichung vergleichen wir die LOUDS-, BP- und DFUDS-Methoden am Beispiel des Minibaums.

Die Knoten des Baumes sind orange nummeriert, als ob sie in der Breite (für LOUDS) laufen, in blau - als ob sie in der Tiefe laufen (für BP und DFUDS).

LOUDS-, BP- und DFUDS-Baumansichten.

Seien Sie nicht überrascht, wenn Sie Unterschiede in Formeln in englischsprachigen Werken sehen. Unter Mathematikern gibt es Liebhaber der Indexierung ab einem. Und einige Entwickler betrachten die Wörter rank und range consonant, so dass sie den Rang halbieren. $[0; i)$ . Aufgrund der Notwendigkeit, die Symmetrie von Rang / Auswahl beizubehalten, berechnen sie $select (i)$ wie $select (i + 1)$ . Einige Formeln in dieser Form sehen jedoch kürzer aus.

Sparse Array: schütteln, aber nicht mischen

Ein spärliches Array ist eine andere Struktur, die buchstäblich für die Komprimierung erstellt wurde. Die Größe eines solchen Arrays ist manchmal um Größenordnungen größer als die Anzahl der gefüllten Elemente. Und leere Elemente nehmen entweder einen Standardwert an oder sind mit so etwas wie null markiert. Ein spärliches Array zeichnet sich am Horizont ab, wann immer dies erforderlich ist, um viele Objekte und die Beziehungen zwischen ihnen zu speichern. Die Graphen von Freunden in sozialen Netzwerken, Suchmaschinen-Ranking-Algorithmen, Excel-ähnlichen Tabellen, elektrischen Schaltungssimulatoren mit Milliarden von Transistoren in einem Chip fallen einem sofort ein.

Oft sind solche Arrays zyklopisch im Lovecraft-Stil, mit einer naiven Implementierung passen sie nicht in den Arbeitsspeicher und bleiben praktisch leer. Je nach Speicher- und Geschwindigkeitsanforderungen werden spärliche Arrays zu viel kompakteren Hash-Tabellen, Adjazenzlisten, Binärbäumen ... oder prägnanten Arrays.

Nehmen wir an, wir haben eine spärliche Reihe von Zeichenfolgen. Fügen Sie ein kompaktes indexierbares Wörterbuch hinzu. Was wird es geben?

Sparse Array mit einer Bitmap.

Ohne direkten Zugriff auf das ursprüngliche Array ist es jetzt einfach zu überprüfen, ob ein Element im gewünschten Index vorhanden ist. Nichts verhindert das Verkleinern des ursprünglichen Arrays, indem alle ungefüllten Elemente weggeworfen werden:

Ein Array ohne leere Elemente.

Berechnen eines Index in einem komprimierten Array. Nach der Überprüfung auf das Vorhandensein eines Elements wäre es hilfreich, auf dessen Wert im ursprünglichen Array zuzugreifen, d. H. Den Index abzubilden $i$ im indexierten Wörterbuchindex $j$ in einem komprimierten Array. Kein Wunder, dass Rang dafür verwendet wird:

$j = Rang_1 (i) -1$

Lassen Sie uns überprüfen, wie es mit dem 8. Element aussieht: $bitmap [8] = 0$ . Im ursprünglichen Array gibt es also kein solches Element. Was ist mit Element 7? $bitmap [7] = 1$ . Holen Sie sich seinen Wert: $rank_1 (7) - 1 = 3-1 = 2$ . Bei Index 2 ist "go".

Berechnung des Index im Quell-Array. Sicherlich müssen Sie im Array nach Elementen nach Wert suchen! Wenn die Daten nicht sortiert sind, beschränkt sich die Suche auf die Suche nach $O (N)$ wo $N$ - die Anzahl der nicht leeren Elemente. Für gefundenes Objekt $j$ Möglicherweise muss der Index abgerufen werden $i$ als ob das Array nicht geschrumpft wäre. Verwenden Sie dazu select, das Gegenteil von rank:

$i = select_1 (j + 1)$

Suchen Sie zum Beispiel die Zeile „C ++“. In einem kompakten Array befindet es sich am Index 0. Und sein Index im ursprünglichen Array ist $select_1 (0 + 1) = 3$ .

Schon an einem Beispiel mit Zeilen spürbare Speichereinsparungen. Wenn das Array Klassen mit vielen Feldern speichern soll, werden die Einsparungen erheblich größer. Darüber hinaus ist die Suche in einem kompakten Array schneller als in einem großen und spärlichen Array: Es wird vom Prozessor besser zwischengespeichert. Ein bitindexiertes Wörterbuch passt eher in eine Cache-Zeile als ein reguläres Array von Zahlen, Zeichenfolgen oder ausgefallenen benutzerdefinierten Typen.

Natürlich zur Aufbewahrung $2 ^ {30}$ Elemente beschriebene Methode ist nicht geeignet. Ihre Anwendbarkeit endet dort, wo Probleme mit dem Wachstum des Index auftreten. Aber natürlich hat diese Methode zum Komprimieren von Arrays und ihren Variationen eine eigene Nische. Ein alltägliches Beispiel ist die Implementierung des BitTorrent-Protokolls. Die Bitmap enthält Informationen zu den heruntergeladenen Dateisegmenten, und Peers tauschen die Indizes ihrer Segmente aus. Ein Weltraumbeispiel sind die segmentierten Datenübertragungsoptionen, die von Rovern, Voyagern und der New Horizons-Station verwendet werden, um trans-Neptune-Freiflächen zu pflügen.

Die beschriebenen Beispiele für die Succinctization eines Präfixbaums und eines spärlichen Arrays basieren auf einer gemeinsamen Grundlage. Es basiert auf einem unerschütterlichen Glauben an die Wirksamkeit von Rank / Select-Operationen. Ohne sie platzt die ganze Theorie der kompakten, aber ausreichend schnellen Strukturen aus allen Nähten. Die Angemessenheit der Verwendung kompakter Strukturen außerhalb von Dissertationen hängt vom Rang und der Auswahlgeschwindigkeit ab.

Tatsächlich können diese Operationen äußerst effizient implementiert werden: Rang für Rang $O (1)$ ; Wählen Sie - für $O (log (log N))$ , was auch fast konstant ist. Und natürlich ist es nicht ohne Tricks. Und da jede Arbeit mit einer komplizierten Handlung eine leichte Untertreibung enthalten muss, höre ich hier auf.

Interessante Fakten

Was ist die theoretische Untergrenze der belegten Ressourcen in Bezug auf die Informationstheorie? Angenommen, eine Datenstruktur speichert viel $N$ Elemente. Um sie ohne Kollisionen zu identifizieren, benötigen Sie eine Anzahl von Bits, nicht weniger als $X = log_2N$ . $X$ und es gibt diese sehr untere Grenze, die durch die Hartley-Formel bestimmt wird. In einigen speziellen Fällen kann die Struktur mit Informationen über die Art der gespeicherten Daten noch effizienter komprimiert werden.

Ist der prägnante String eine Datenstruktur? Es enthält $N$ Zeichen und endet mit einem Null-ASCII-Zeichen. Also dauert es $N + 1$ Orte, und daher ... sie ist prägnant und insbesondere implizit! Was uns zur nächsten Frage führt.

Sind alle prägnanten Strukturen gleich kompakt? Das prägnante Forschungsgebiet definiert bis zu drei Arten kompakter Strukturen mit unterschiedlicher räumlicher Komplexität:

kompakt - $O (N)$ . Lineare Komplexität von $N$ - die Anzahl der gespeicherten Artikel. Die meisten "frei" in Bezug auf die Anforderungen für die Komprimierung der Struktur.Sozusagen ein Warm-up vor einem echten Hardcore. Wenn es sich um Zeilen handelt, ist das folgende Beispiel geeignet: eine Folge von Zeilen variabler Länge. Zeichenfolgen werden nacheinander ohne Trennzeichen gespeichert. Um nach einzelnen Zeilen zu suchen, wird eine Bitmap gebildet, in der alle Bits mit Ausnahme von Bits mit Indizes, die dem Zeilenanfang entsprechen, auf 0 zurückgesetzt werden. Diese Struktur nimmt $O(2N)$ (Der Faktor 2 bei der Verwendung von Landau-Symbolen wird am besten weggelassen, ist aber klarer) und ermöglicht die Implementierung einer Schnellauswahl, um den Anfang jeder Zeile in der Sequenz zu bestimmen.
prägnant - $N + o(N)$ . — , succinct data structures . : (Pascal string), . $N + log(N)$ .
implicit — $N + O(1)$ . , . : (heap) . $N + 1$ .

? , , . succinct- . , -, FM-, RMQ (range minimum queries), LCP (longest common prefix), , succinct'. -.

Nachwort

, , . Und nicht nur. , , X, .

succinct — , «- ». Succinct — . , , succinct. , . (IME) Google, . MAPS.ME succinct- .

, . ., 97 % -: . 3 %.

Was weiter?

, succinct:

, :

Katzen in Kisten oder kompakte Datenstrukturen