Die Elias-Fano-Kodierung (nicht zu verwechseln mit der Shannon-Fano-Elias-Kodierung) ist eine Kodierung, die eine sortierte Zahlenfolge so komprimiert, dass möglichst viele Operationen, die von sortierten Listen unterstützt werden, ähnlich effizient unterstützt werden.[1][2]

Diese wurden vor kurzem wiederentdeckt[3] und dienen meistens als eine Indexstruktur[4] von beispielsweise invertierten Dateien.

Im Allgemeinen ist es immer eine Überlegung wert, falls der Platzbedarf wichtig ist und ein Problem eine große Menge an sortierten Daten besitzt, eine Elias-Fano Kodierung zu testen.

Grundlagen

Bearbeiten

Die Elias-Fano Kodierung unterstützt auf der Kodierung einer  -elementigen sortierten Liste   aus dem Universum   mit   im Wesentlichen vier verschiedene Operationen.[2]

  • Eine Dekomprimierung, die die ursprüngliche sortierte Liste erzeugt.
  • Zugriff auf das  -te Element  .
  • Die Anzahl an Elementen, die kleiner als   sind. Dies ist analog zu der Binären Suche auf einer sortierten Liste  .
    • Analog hierzu ist es üblich, eine predecessor und successor Anfrage bereitzustellen, die für ein   das größte   bzw. das kleinste   ausgibt,   und  .
  • Die Transformation in das Komplement der sortierten Liste (d. h. für jedes mögliche   die Anzahl an Elementen, die kleiner als   sind)  .

Die Elias-Fano Kodierung benötigt   bits Speicherplatz . Falls man dies mit der Delta-Kodierung vergleicht, benötigt diese erwartet  bits, ohne dass diese fortgeschrittenen Operationen unterstützt. D. h. man kann in nur   Speichermehrbedarf sinnvolle zusätzliche Operationen hinzufügen.

Um eine Elias-Fano Kodierung zu implementieren, benötigt man ein Bitvektor welcher   und   Anfragen in konstanter Laufzeit unterstützt und einen höchstens konstanten Platzmehrbedarf pro Bit aufweist. Die   Anfrage gibt die Anzahl an gesetzten Bits vor dem Index   zurück und   gibt die Anzahl an nicht gesetzten Bits zurück. Die   Anfrage gibt den Index des  -ten gesetzten Bits zurück, wobei   ist.

Außerdem benötigt man noch einen Vektor, indem jede Zelle exakt   bits breit ist, wobei   zur Laufzeit bestimmt werden kann.

Algorithmus

Bearbeiten
 
Veranschaulichung der Elias-Fano Kodierung der sortierten Liste [21,24,25,29,31]. Dies zeigt die Generierung des Bitvektors mithilfe der dunkelgrünen Pfeile und die Generierung des Vektors mit dunkellila Pfeilen.

Zunächst ist eine  -elementige sortierte Liste   an Zahlen aus dem Universum   mit  gegeben.

Hierdurch kann ein Bitvektor der Länge   und ein Vektor der Länge  , dessen Zellen   bits breit sind, erzeugt werden.

Jedes   wird in die vorderen   und in die hinteren   Bits aufgeteilt. Hierbei entsprechen die vorderen Bits der Zahl  und die hinteren Bits der Zahl  .

Nun wird die  -te Null des Bitvektors auf Eins gesetzt, bzw. der  -te Index auf Eins gesetzt und  in dem Vektor an Index   gespeichert.

Der Bitvektor wird nicht überlaufen, da  .

Implementation

Bearbeiten

Generierung eines Elias-Fano Kodierung

Bearbeiten

Diese Elias-Fano Kodierung generiert eine Bitmaske, um die unteren Bits zu extrahieren, die oberen Bits werden extrahiert, indem die unteren Bits „rausgeschoben“ werden.

using Bitvec = /*die Klasse für einen Bitvektor mit rank und select anfragen*/
using FixedArr = /*das Array mit zur Laufzeit bestimmbaren Zell-längen*/

struct EliasFano{
  const Bitvec bv;
  const FixedArr arr;
  const size_t mask,shift;
};

template<std::unsigned_integral T>
EliasFano generateEliasFano(const std::vector<T> &input){
    assert(std::is_sorted(input.begin(),input.end()));
    const int log_n = std::ceil(std::log2(input.size()));
    const int log_universe = std::ceil(std::log2(input.back()));
    Bitvec bv{input.size()+std::pow(2,log_n)};
    FixedArr arr{input.size(),log_universe-log_n};
    const int mask = (static_cast<T>(1)<<(log_universe-log_n))-1;
    const int upper_shift= log_universe-log_n;

    for(size_t i=0;i<input.size();++i){
        const T lower = input[i]&mask, upper = input[i]>>upper_shift;
        arr[i]=lower;
        bv[i+upper]=true;
    }
    return EliasFano{std::move(bv),std::move(arr),mask,upper_shift};
}

Anfragen

Bearbeiten

Hier ist eine access und eine predecessor Anfrage beschrieben. Die predecessor Anfrage sucht sich zunächst mithilfe des Bitvektors den Index  , der höchstens   größer als der Zielindex   ist. Deshalb ist es hinreichend, auf die Indizes im Intervall   in der Kodierung zuzugreifen und davon den größtmöglichen (der kleiner als der gesuchte Wert ist) auszugeben. Die successor, predecessor und lowerbound Anfragen werden sehr ähnlich implementiert.

Man sieht, dass die access Anfrage eine Laufzeit von   und die predecessor eine Laufzeit von   aufweist.

size_t access(size_t index, const EliasFano & ef){
    return ((ef.bv.select_1(index)-index)<<ef.shift)|ef.arr[index];
}

size_t pred(size_t index, const EliasFano & ef){
    size_t upper = index >> ef.shift, lower=index&ef.mask;
    size_t upper_idx=ef.bv.select_0(upper+1)-upper+1;
    for(int i=1<<bf.shift-1;i>=0;--i,--upper_idx){//läuft exakt log(u/n) mal durch
        const size_t out = access(upper_idx);
        if(out<=index)return out;
        if(upper_idx==0)return -1;//ausserhalb der Grenze
    }
    assert(false);

}

Varianten

Bearbeiten

Partitoned Elias-Fano Kodierung

Bearbeiten

Häufig tritt der Fall ein, dass in der sortierten Liste Intervalle mit einer hohen oder niedrigen Elementdichte existieren. Deshalb ist es sinnvoll, diese Liste in mehrere Teillisten zu partitionieren, die unabhängig voneinander Elias-Fano kodiert werden.[4]

Einzelnachweise

Bearbeiten
  1. Robert Mario Fano: On the Number of Bits Required to Implement an Associative Memory. Hrsg.: MIT Project MAC Computer Structures Group. 1971.
  2. a b Peter Elias: Efficient Storage and Retrieval by Content and Address of Static Files. Association for Computing Machinery, 1. April 1974, abgerufen am 27. Februar 2024 (englisch).
  3. Antonio Mallia: Sorted integers compression with Elias-Fano encoding. 6. Januar 2018, abgerufen am 28. Februar 2024 (englisch).
  4. a b Giuseppe Ottaviano, Rossano Venturini: Partitioned Elias-Fano indexes. ACM, 2014, ISBN 978-1-4503-2257-7, S. 273–282, doi:10.1145/2600428.2609615 (acm.org [abgerufen am 28. Februar 2024]).