Elias Omega Code
Die Elias-Omega-Kodierung kodiert die Längenteile rekursiv und ist die kompakteste der drei Elias-Universalcodes für große Ganzzahlen, mit einer Codelänge log2(n)+log2(log2(n))+...+O(1).
Zweck
Sie liefert den optimalen Universalcode, wenn die obere Schranke der Ganzzahlen unbekannt ist und große Werte häufig vorkommen.
Mechanismus
Die Kodierung ist rekursiv: Ausgehend von n gibt man die Binärdarstellung von floor(log2(n)) aus und kodiert diese Länge rekursiv, mit einer einzelnen 0 als Terminierungsmarker. Die Dekodierung rekonstruiert den Wert durch umgekehrte Rekursion.
Anwendungsfälle
- Variabel lange Kodierung sehr großer Ganzzahlen
- Theorie universeller Kompression
- Lehre rekursiver Kodierung