Elias-Fano-Kodierung

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.

Diese wurden vor kurzem wiederentdeckt und dienen meistens als eine Indexstruktur 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

Die Elias-Fano Kodierung unterstützt auf der Kodierung einer $n$-elementigen sortierten Liste $[x_1,x_2,x_3,...,x_n]$ aus dem Universum $U:=[0,u)$ mit $x_n<u=2^w$ im Wesentlichen vier verschiedene Operationen.

• Eine Dekomprimierung, die die ursprüngliche sortierte Liste erzeugt.
• Zugriff auf das $i$-te Element $\mathsf{\text{access}}(i):=x_i$.

• Die Anzahl an Elementen, die kleiner als $k$ sind. Dies ist analog zu der Binären Suche auf einer sortierten Liste $\mathsf{\text{lowerbound}}(k):=|\{i\in [1,n]|x_i<k\}|$.
  • Analog hierzu ist es üblich, eine predecessor und successor Anfrage bereitzustellen, die für ein $k$ das größte $x_i\le k$ bzw. das kleinste $x_i\ge k$ ausgibt, $\mathsf{\text{pred}}(k):=\underset{i\le n}{\max }\{x_i\le k\}$ und $\mathsf{\text{succ}}(k):=\underset{i\le n}{\min }\{x_i\ge k\}$.

• Die Transformation in das Komplement der sortierten Liste (d. h. für jedes mögliche $k$ die Anzahl an Elementen, die kleiner als $k$ sind) $\mathsf{\text{comp}}:=[\mathsf{\text{lowerbound}}(0),\mathsf{\text{lowerbound}}(1),...,\mathsf{\text{lowerbound}}(u)]$.

Die Elias-Fano Kodierung benötigt $n*\lceil \frac{u}{n}\rceil +\mathrm{\Theta }(n)$ bits Speicherplatz . Falls man dies mit der Delta-Kodierung vergleicht, benötigt diese erwartet $n*\lceil \frac{u}{n}\rceil$bits, ohne dass diese fortgeschrittenen Operationen unterstützt. D. h. man kann in nur $\mathrm{\Theta }(n)$ Speichermehrbedarf sinnvolle zusätzliche Operationen hinzufügen.

Um eine Elias-Fano Kodierung zu implementieren, benötigt man ein Bitvektor welcher ${\mathsf{\text{rank}}}_i(x)$ und ${\mathsf{\text{select}}}_i(x)$ Anfragen in konstanter Laufzeit unterstützt und einen höchstens konstanten Platzmehrbedarf pro Bit aufweist. Die ${\mathsf{\text{rank}}}_1(x)$ Anfrage gibt die Anzahl an gesetzten Bits vor dem Index $x$ zurück und ${\mathsf{\text{rank}}}_0(x):=x-{\mathsf{\text{rank}}}_1(x)$ gibt die Anzahl an nicht gesetzten Bits zurück. Die ${\mathsf{\text{select}}}_1(x)$ Anfrage gibt den Index des $x$-ten gesetzten Bits zurück, wobei ${\mathsf{\text{select}}}_1(0)=0$ ist.

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

Algorithmus

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 $n$-elementige sortierte Liste $[x_1,x_2,x_3,...,x_n]$ an Zahlen aus dem Universum $U:=[0,u)$ mit $x_n<u=2^w$gegeben.

Hierdurch kann ein Bitvektor der Länge $n+2^{\lceil {\log }_2(n)\rceil }\in \mathrm{\Theta }(n)$ und ein Vektor der Länge $n$, dessen Zellen $\lceil {\log }_2\left(\frac{u}{n}\right)\rceil =\lceil {\log }_2(u)-{\log }_2(n)\rceil$ bits breit sind, erzeugt werden.

Jedes $x_i$ wird in die vorderen $\lceil {\log }_2(n)\rceil$ und in die hinteren $\lceil {\log }_2(u)-{\log }_2(n)\rceil$ Bits aufgeteilt. Hierbei entsprechen die vorderen Bits der Zahl $u_i$und die hinteren Bits der Zahl $l_i$.

Nun wird die $u_i$-te Null des Bitvektors auf Eins gesetzt, bzw. der $(u_i+i)$-te Index auf Eins gesetzt und $l_i$in dem Vektor an Index $i$ gespeichert.

Der Bitvektor wird nicht überlaufen, da $u_n+n\le 2^{\lceil {\log }_2(n)\rceil }+n$.

Implementation

Generierung eines Elias-Fano Kodierung

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

Hier ist eine access und eine predecessor Anfrage beschrieben. Die predecessor Anfrage sucht sich zunächst mithilfe des Bitvektors den Index $\hat{i}$, der höchstens $\lceil {\log }_2\left(\frac{u}{n}\right)\rceil$ größer als der Zielindex $i$ ist. Deshalb ist es hinreichend, auf die Indizes im Intervall $[\hat{i}-\lceil {\log }_2\left(\frac{u}{n}\right)\rceil ,\hat{i}]$ 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 $O(1)$ und die predecessor eine Laufzeit von $O\left(\lceil {\log }_2\left(\frac{u}{n}\right)\rceil \right)$ 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

Partitoned Elias-Fano Kodierung

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.