Umfrage zu prägnanten Datenstrukturen?

17

Fischers Artikel in diesem Monat erinnerte mich daran, wie wenig ich über die Kunst prägnanter Datenstrukturen und Algorithmen zu ihrer Verwendung weiß.

Für diejenigen, die sich mit prägnanten Datenstrukturen nicht auskennen:

Vorausgesetzt, eine kombinatorische Struktur mit einer (n) unterschiedlichen Konfiguration und einer bekannten "nützlichen" Darstellung . Gibt es eine "prägnante" Datenstruktur, in der ungefähr lg ( a ( n ) ) Bits gespeichert werden, die es uns jedoch ermöglicht, Operationen so schnell wie möglich mit der normalen Darstellung R durchzuführen ?R(n)lg(a(n))R

Die Besten, die mich interessieren, wenn jemand eine Diskussion führen möchte

  1. Suffix-Arrays. Sie sind eine Teilmenge aller Permutationen.

  2. Bestellte Bäume. Sie sind eine Teilmenge aller binären "Klammern" (die übereinstimmende Sorte).

  3. Alle nächstkleineren Werte wie im Artikel ( 1 ). Sie können nicht nur in beiden Dimensionen komprimieren. die zulässige „kleinerer Wert“ Arrays in eine Richtung ist eine kleine Untergruppe von Listen , und daher müssen Sie weniger als n lg ( n ) Bits speichern .{0,...,n1}nnlg(n)

Chad Brewbaker
quelle

Antworten: