Knapp kodierte (Succinct) Datenstrukturen

• Beim Lesen von Fachartikeln zur Performance-Optimierung bin ich zum ersten Mal auf das Konzept der Succinct Data Structures (knapp kodierte Datenstrukturen) gestoßen
• Auf der Suche nach verwandten Arbeiten habe ich sogar direkt mit dem renommierten Forscher Professor Gonzalo Navarro Kontakt aufgenommen
• Im Unterschied zu klassischen Arrays, Hash-Maps oder Bäumen stellte sich mir die Frage, warum solche Datenstrukturen nicht häufiger eingesetzt werden
• Dazu möchte ich eine kurze Erklärung geben

Überblick über Succinct Data Structures

• Ähnlich wie bei gewöhnlicher Datenkompression werden Daten komprimiert gespeichert, können aber auch im komprimierten Zustand direkt verwendet werden
• Unterschied zu herkömmlichen Kompressionsverfahren: Auf Daten kann ohne Dekomprimierung zugegriffen und sie können bearbeitet werden
• Ein Forschungsgebiet, das in den letzten 25 Jahren intensiv untersucht wurde

Einsatz in Rust

• In der Systemprogrammierung sind Performance und Speicherverbrauch wichtig, daher haben solche Datenstrukturen großes Potenzial
• Bisherige Forschung fand überwiegend in C++ statt, aber inzwischen gibt es auch Implementierungen in Rust
• Vorgestellt werden Bibliotheken, die für Rust-Entwickler nützlich sein können

Bit Vectors (Bitvektoren)

• Beispiel für ein Bit-Array: [0, 1, 0, 1, 1, 0, 1, 0]
• Auf einem 64-Bit-System lassen sich 64 Bits in einer einzigen Ganzzahl speichern, was Speicher spart
• Ein Bitvektor an sich ist noch keine succinct Struktur, aber es gibt effiziente Methoden zu seiner Nutzung

Rank/Select Bit Vector

• Rank-Operation: Berechnet, wie oft eine 1 vor einem bestimmten Index vorkommt
  • Beispiel: rank(3) → 2
• Select-Operation: Gibt die Position zurück, an der die n-te 1 erscheint
  • Beispiel: select(2) → 3
• Ausführbar mit O(1)-Zeitkomplexität
• Geringer Speicher-Overhead und nützlich beim Umgang mit großen Strings
• Anwendungsfälle
  • Nützlich, wenn große Strings in kleinere Teilstrings zerlegt und gespeichert werden
  • Es lässt sich effizient bestimmen, zu welchem Teilstring ein bestimmter Index gehört
  • Durch komprimierte Speicherung ist schneller Zugriff bei geringerem Speicherverbrauch möglich
• Rust-Bibliotheken
  • vers: Hohe Performance bei minimalem Overhead
  • sucds: Unterstützt spärliche (Sparse) Implementierungen wie SArray
  • vers ist besonders stark bei der effizienten Erzeugung von Datenstrukturen und soll künftig auch spärliche Implementierungen unterstützen

Wavelet Matrix (Wavelet-Matrix)

• Erweitert das Rank/Select-Konzept auf Daten mit größerem Alphabet
• Zum Beispiel DNA-Sequenzanalyse (A, C, G, T) oder Textsuche (UTF-8-Zeichen, 256 Symbole)
• Arbeitet auf Basis von Rank/Select-Bitvektoren
• Rust-Bibliotheken
  • vers enthält eine Implementierung der Wavelet-Matrix

FM-Index (komprimierter String-Index)

• Unterstützt Suchfunktionen, während große Textmengen komprimiert gespeichert werden
• Kernfunktionen:
  • count(pattern): Berechnet, wie oft ein bestimmtes Muster (String) vorkommt
  • locate(pattern): Gibt alle Indizes zurück, an denen das Muster vorkommt
• Nützlich für DNA-Sequenzsuche und Suche in großen Textmengen
• Rust-Bibliotheken
  • Die Bibliothek fm-index kann verwendet werden
  • Früher wurde fid verwendet, nach der Migration zu vers verbesserte sich die Performance

Balanced Parentheses (balancierte Klammerdarstellung)

• Speichert Baumstrukturen komprimiert auf dem Niveau von 2 Bit pro Knoten
• Beispielbaum:

   a  
 /   \\  
b     c  

• Kann in der Form (()()) dargestellt werden
• Auch als 1 (öffnende Klammer) und 0 (schließende Klammer) darstellbar: 110100
• Nutzt Rank/Select-Operationen zur Optimierung von Traversierungsoperationen im Baum
• Rust-Bibliotheken
  • Wird im dev-bp-Branch von vers implementiert

Anwendung: XML-Speicherung und -Verarbeitung

• XML kann mittels balancierter Klammerdarstellung gespeichert werden
• Zur effizienten Verarbeitung von XML-Tags (p, div usw.) werden Rank/Select-Bitvektoren verwendet
• Mit FM-Index lässt sich die Textsuch-Performance verbessern

Fazit

• Succinct-Datenstrukturen bieten zugleich geringen Speicherverbrauch und schnelle Operationen
• Es wurde viel in C++ geforscht, aber auch in Rust wird inzwischen aktiv implementiert
• In der Zusammenarbeit mit Forschern und Open-Source-Entwicklern zeigt sich viel Potenzial
• Künftig könnten sie in vielen Bereichen der Informatik deutlich breiter eingesetzt werden

[qwqwhs]

Durch die Nutzung von Wavelet werden komprimierte Strukturen in DjVu standardmäßig gut eingesetzt. Die Bildkomprimierung ist wirklich hervorragend.

[GN⁺]

Hacker-News-Kommentare

• Ich habe Gonzalo Navarro eine E-Mail mit einer Frage geschickt, und daraus ist schließlich eine gemeinsame Arbeit entstanden

  • Eine weitere seiner Arbeiten behandelt eine einfache Implementierung von Bitvektor-Rank/Select durch die Kombination einiger eleganter Ideen
  • In dieser Zeit begann ich mich sehr für succincte Datenstrukturen zu interessieren und schrieb eine Rust-Bibliothek, die verschiedene Bitvektor-Typen und Wavelet-Matrizen implementiert
  • Aus der Perspektive der Datenvisualisierung habe ich mich gefragt, ob platzsparende Datenstrukturen die interaktive Exploration großer Datensätze auf der Client-Seite grundlegend verbessern können

• Ich bin seit über 30 Jahren in diesem Bereich tätig, aber von „succincten Datenstrukturen“ habe ich zum ersten Mal gehört

  • Hätte ich diesen Beitrag nicht gesehen, hätte ich wahrscheinlich nie davon erfahren
  • Wenn diese Datenstruktur praktische Anwendungen in der Graphverarbeitung hat, könnte das eine wichtige Entdeckung sein
  • Dieses Thema wirkt sehr reizvoll

• Succincte Datenstrukturen sind möglicherweise nicht schneller als herkömmliche Strukturen, wenn der Datensatz in den Speicher passt

  • Bei großen Datensätzen dominiert jedoch die Speicherzugriffszeit, daher sind succincte Datenstrukturen im Vorteil
  • Succincte Bäume sind wie Kunstwerke

• Von Edward Kmett habe ich zum ersten Mal das Konzept succincter Datenstrukturen gehört

  • Er ist ein bekannter Entwickler von Haskell-Bibliotheken und hat vor langer Zeit einen Vortrag über succincte Datenstrukturen gehalten

• Succincte Datenstrukturen machen sehr viel Spaß

  • Ich habe sie in Zig implementiert; die wichtigste Implementierung ist eine minimale perfekte Hash-Funktion, die Elemente mit weniger als 4 Bit verwendet
  • Solche Algorithmen zu implementieren, ist wie Magie

• Navarros Buch ist eine hervorragende Übersicht

  • Auch Erik Demaines Vorlesung über succincte Datenstrukturen ist ausgezeichnet

• Ich habe den Morgen damit verbracht, mich mit succincten Datenstrukturen zu beschäftigen, und die Speichereffizienz ist erstaunlich

  • In einem Projekt zur Analyse großer XML-Dateien verbrauchen wir sehr viel RAM
  • Das Konzept der Wavelet-Matrix wirkt für textzentrierte Arbeiten vielversprechend

• Es gibt eine Möglichkeit, die In-Memory-Knotendarstellung großer Strukturen effizient zu gestalten

  • Man weist selten genutzten Feldern Offsets zu und verwendet eine Bitmaske, um das Vorhandensein eines Feldes anzuzeigen
  • Masking und popcount ermöglichen einen schnellen Zugriff

• Marisa trie ist eine sehr coole und nützliche succincte Datenstruktur

  • Sie wird auch im Buch High Performance Python erwähnt

• Meine Standardbibliothek für succincte Datenstrukturen ist SDSL-Lite