Saltar a contenido

Variable Length Quantity

Descripción

Variable Length Quantity (VLQ) es un método de codificación que convierte secuencias de valores enteros positivos (de tamaño fijo) a secuencias de bytes (de tamaño variable). Es conocido por varios nombres, entre ellos: Base-128 compression, VB (Variable Byte), VByte, Varint, VInt, EncInt, entre otros.

Funcionamiento

Para hacer más amena la comprensión de este método, se procederá a explicar paso a paso de manera simplificada cómo funciona la codificación y la decodificación (Se usarán unsigned int de 4 bytes):

Codificación

Arreglo Inicial
1 ; 139 ; 1239 ; 23 ; 89

Paso 1: Tomaremos cada entero de manera individual y veremos su representación binaria.

Antes ➜ Después
1 ➜ 00000000 00000000 00000000 00000001
139 ➜ 00000000 00000000 00000000 10001011
1239 ➜ 00000000 00000000 00000100 11010111
23 ➜ 00000000 00000000 00000000 00010111
89 ➜ 00000000 00000000 00000000 01011001

Paso 2 : Separaremos nuestras secuencias en grupos de 7 bits, de la siguiente forma.

Antes ➜ Después
1 ➜ 0000000 0000000 0000000 0000000 0000001
139 ➜ 0000000 0000000 0000000 0000001 0001011
1239 ➜ 0000000 0000000 0000000 0001001 1010111
23 ➜ 0000000 0000000 0000000 0000000 0010111
89 ➜ 0000000 0000000 0000000 0000000 1011001

Paso 3: Rellenaremos con 3 bits a la izquierda de las secuencias.

Antes ➜ Después
1 ➜ 0000000 0000000 0000000 0000000 0000001
139 ➜ 0000000 0000000 0000000 0000001 0001011
1239 ➜ 0000000 0000000 0000000 0001001 1010111
23 ➜ 0000000 0000000 0000000 0000000 0010111
89 ➜ 0000000 0000000 0000000 0000000 1011001

Paso 4: Eliminaremos aquellas subsecuencias de 7 bits iguales a 0.

Antes ➜ Despues
1 ➜ 0000001
139 ➜ 0000001 0001011
1239 ➜ 0001001 1010111
23 ➜ 0010111
89 ➜ 1011001

Paso 5: Al inicio de cada subsecuencia de 7 bits, pondremos un 1 si existe una subsecuencia que le sigue y 0 en caso de ser la última.

Antes ➜ Despues
1 ➜ 00000001
139 ➜ 10000001 00001011
1239 ➜ 10001001 01010111
23 ➜ 00010111
89 ➜ 01011001

¡Nuestra codificación ya está lista! Pasamos de tener 20 bytes a 7 bytes.

Codificación
00000001 10000001 00001011 10001001 01010111 00010111 01011001

Decodificación

Secuencia Inicial
00000001 10000001 00001011 10001001 01010111 00010111 01011001

Paso 1: Sabemos que cuando el byte comienza por 0, este será la última subsecuencia perteneciente a la representación del número, y cuando es 1, aun no acaba. De esta forma, separaremos por números individuales.

Enteros codificados
00000001
10000001 00001011
10001001 01010111
00010111
01011001

Paso 2: Eliminaremos el primer bit a la izquierda de cada byte.

Enteros codificados
0000001
0000001 0001011
0001001 1010111
0010111
1011001

Paso 3: Rellenaremos con los 0 correspondientes a la izquierda (Para tener los enteros de 4 bytes).

Antes ➜ Despues
00000000 00000000 00000000 00000001 ➜ 1
00000000 00000000 00000000 10001011 ➜ 139
00000000 00000000 00000100 11010111 ➜ 1239
00000000 00000000 00000000 00010111 ➜ 23
00000000 00000000 00000000 01011001 ➜ 89

¡Nuestra decodificación ya está lista! Ya tenemos de vuelta nuestro arreglo de enteros.

Resultados:

Arreglo Inicial
00000000 00000000 00000000 00000001 00000000 00000000 00000000 10001011 00000000 00000000 00000100 11010111 00000000 00000000 00000000 00010111 00000000 00000000 00000000 01011001
Arreglo Codificado
00000001 10000001 00001011 10001001 01010111 00010111 01011001
Arreglo Decodificado
00000000 00000000 00000000 00000001 00000000 00000000 00000000 10001011 00000000 00000000 00000100 11010111 00000000 00000000 00000000 00010111 00000000 00000000 00000000 01011001

Estructura de la Codificación

Teniendo en cuenta la explicación anterior, podemos observar que cada byte tendrá su primer bit de la izquierda dedicado a guardar 0 en caso de ser última subsecuencia y 1 en caso contrario, ademas cada byte tendrá los siguientes valores:

Cota inferior ≤ Byte N° < Cota Superior
20 ≤ Byte 1 < 27
27 ≤ Byte 2 < 214
214 ≤ Byte 3 < 221
221 ≤ Byte 4 < 228
228 ≤ Byte 5 < 232

Un Poco de Análisis Teórico

Análisis de espacio

Observando lo anterior, el peor de los casos es cuando todos los números del arreglo original son iguales o mayores que 228, de tal modo que tendríamos complejidad de espacio \(\frac{5}{4}n\) equivalente a \(O(n)\). De la misma forma, cuando los números son menores a \(2^7\) tendremos que la complejidad de espacio es \(\frac{1}{4}n\) , equivalente a \(\Omega(n)\).

Análisis de tiempo

En cuanto a la complejidad temporal, tenemos que la codificación y la decodificación del arreglo serán \(O(n)\), puesto que ambos deben recorrer toda la secuencia.

Implementación

A continuación, presentaremos una implementación de la página web “Rosetta Code”.

Código:

#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;

ostream &operator<<(ostream &os, const vector<uint8_t> &v) {
    auto it = v.cbegin();
    auto end = v.cend();
    os << "[ ";
    if (it != end) {
        os << setfill('0') << setw(2) << (uint32_t)*it;
        it = next(it);
    }
    while (it != end) {
        os << ' ' << setfill('0') << setw(2) << (uint32_t)*it;
        it = next(it);
    }
    return os << " ]";
}

// Codificador individual de unsigned int de 32 bits.
vector<uint8_t> to_seq(uint32_t x) {
    int i;
    for (i = 4; i > 0; i--) {
        if (x & 127U << i * 7) {
            break;
        }
    }
    vector<uint8_t> out;
    for (int j = 0; j <= i; j++) {
        out.push_back(((x >> ((i - j) * 7)) & 127) | 128);
    }
    out[i] ^= 128;
    return out;
}

// Decodificador individual de unsigned int de 32 bits.
uint32_t from_seq(const vector<uint8_t> &seq) {
    uint32_t r = 0;
    for (auto b : seq) {
        r = (r << 7) | (b & 127);
    }
    return r;
}


int main() {
    vector<uint64_t> src{1, 139, 1239, 23, 89};
    for (auto x : src) {
        auto s = to_seq(x);
        cout << hex;
        cout << "seq from " << x << ' ' << s << " back: " << from_seq(s) << '\n';
        cout << dec;
    }
    return 0;
}

Output:

seq from 1   [ 01 ]    back: 1
seq from 8b  [ 81 0b ] back: 8b
seq from 4d7 [ 89 57 ] back: 4d7
seq from 17  [ 17 ]    back: 17
seq from 59  [ 59 ]    back: 59

Análisis Experimental

Con la misma implementación, haremos algunas pruebas experimentales de tiempo y espacio. Hay que considerar que cada resultado es el promedio de treintas veces el mismo experimento, además, los arreglos son aleatorizados, con la misma probabilidad de números en los rangos vistos en “Estructura de la Codificación”. A continuación, los datos y gráficos obtenidos,

Tabla de resultados:

Tamaño del array Espacio array (bytes) Espacio codificado (bytes) Espacio decodificado (bytes) Tiempo codificado (microsegundos) Tiempo decodificado (microsegundos)
1000 4000 2975 4000 738 44
2000 8000 6035 8000 1364 83
3000 12000 8997 12000 2027 117
4000 16000 11952 16000 2653 160
5000 20000 14893 20000 3232 206
6000 24000 17936 24000 3916 243
7000 28000 20877 28000 4593 281
8000 32000 23910 32000 5407 333
9000 36000 26956 36000 6018 378
10000 40000 30024 40000 6602 402
... ... ... ... ... ...
91000 364000 272496 364000 65987 3919
92000 368000 275750 368000 67667 4025
93000 372000 279113 372000 66348 3901
94000 376000 281312 376000 68412 4025
95000 380000 284929 380000 65792 3891
96000 384000 287578 384000 64503 3815
97000 388000 290599 388000 65408 4061
98000 392000 293908 392000 66702 3985
99000 396000 296492 396000 67397 3980
100000 400000 299799 400000 67482 4043

Gráfico de espacio de la codificación:

Gráfico espacio

Gráfico de tiempo de codificación:

Gráfico espacio tiempo 1

Gráfico de tiempo de decodificación:

Gráfico espacio tiempo 2

Variantes

Variable Length Quantity es un método de codificación que posee múltiples variantes, a continuación, mostraremos algunas:

Variable Length Quantity para números menores que un byte

En caso de tener un arreglo de números enteros sin signo menores a \(2^7\), mediante un análisis a nuestro arreglo, podemos buscar el menor de estos números y de esta forma trabajar con subsecuencias de bits de tamaño menor a 8.

Unreal Signed Variable Length Quantity

Cada byte tendrá su primer bit de la izquierda dedicado a guardar 0 en caso de ser última subsecuencia y 1 en caso contrario, pero a diferencia de la implementación básica, el segundo bit de la izquierda en el número total, será reservado para guardar 0 en caso positivo y 1 en caso negativo.

Variable Length Quantity (VLQ) con Zigzag Encoding

Antes de usar nuestra codificación VQL haremos un Zigzag Encoding, que consiste en asignar números de modo que 0 codificado corresponde a 0, 1 a −1, 2 a 1, 3 a −2, 4 a 2, y así sucesivamente, de modo que números pares corresponden a positivos e impares a negativos.

LEB128

Es similar a Variable Length Quantity, pero LEB128 esta enfocado en codificar números en formato Little-endian, mientras que VQL no está definido para little-endian o big-endian.

Aplicaciones

  1. Formato Estándar de Archivos MIDI y Extensible Music Format (XMF): Ahorro de espacio en sistemas con recursos limitados.

  2. ASN.1 BER y Entorno WAP: Codificación de números de etiquetas e identificadores de objetos.

  3. Formato de Depuración DWARF: Variante LEB128 para representación eficiente de números en depuración.

  4. Google Protocol Buffers: Representación compacta de valores enteros.

  5. Oracle Portable Object Format (POF) y .NET Framework: Codificación de enteros con el formato de "entero codificado de 7 bits".

  6. Navegadores Web para Mapeo de Fuentes: Reducción del tamaño de mapas que contienen asignaciones de números de línea y columna.

  7. Enteros de Ancho Variable en LLVM: Principio similar con fragmentos de codificación little-endian de longitud no necesariamente 8 bits.

  8. Unreal Engine - Compact Indices: Variable-Length Quantity Scheme llamado Compact Indices en Unreal Packages.

Referencias

[1] University Stanford, Variable byte codes. Disponible en: https://nlp.stanford.edu/IR-book/html/htmledition/variable-byte-codes-1.html#fig:vbalgorithm

[2] Cornell University, Vectorized VByte Decoding. Disponible en: https://arxiv.org/abs/1503.07387

[3] Rosetta Code, Variable-length quantity. Disponible en: https://rosettacode.org/wiki/Variable-length_quantity#C++

[4] Wikipedia, Variable-length quantity. Disponible en: https://en.wikipedia.org/wiki/Variable-length_quantity

[5] Carl Mastrangelo, Let’s Make a Varint. Disponible en: https://carlmastrangelo.com/blog/lets-make-a-varint

[6] TechOverflow, Efficiently encoding variable-length integers in C/C++. Disponible en: https://techoverflow.net/2013/01/25/efficiently-encoding-variable-length-integers-in-cc/