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.
Die Methode entwickelten in den 1970er Jahren Peter Elias und Robert Fano unabhängig voneinander. Ihre Nützlichkeit wurde im 21. Jahrhundert wiederentdeckt. Sie dient meistens als eine Indexstruktur von beispielsweise invertierten Dateien.
Im Allgemeinen ist der Einsatz einer Elias-Fano-Kodierung überlegenswert, falls der Platzbedarf wichtig ist und ein Problem eine große Menge an sortierten Daten besitzt.
Grundlagen Die Elias-Fano-Kodierung unterstützt auf der Kodierung einer -elementigen sortierten Liste aus dem Universum mit im Wesentlichen vier verschiedene Operationen.
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 gerahmt|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
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 sind 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-Anfrage 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
Partitionierte 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.
Einzelnachweise
Kategorie:Kompressionsalgorithmus Kategorie:Kodierungstheorie