Simple9 / Simple16
Definición:
Simple9 y Simple16 son un método de codificación de palabras, el cual permite almacenar una cantidad determinada de enteros dentro de un elemento de 32 bits, donde se guardarán una cantidad \(x\) de elementos, cada uno con una cantidad \(y\) de bits a su disposición y \(z\) bits sobrantes. Este esquema funciona utilizando los primeros 4 bits para identificar la combinación de elementos a almacenar (este valor se denomina “selector”), bits usados para almacenar enteros y bits sobrantes, mientras que los otros 28 bits serán usados para almacenarlos (según la combinación entregada anteriormente).
En Simple9 existen nueve patrones diferentes, identificados desde el 0 (0000) hasta el 8 (1000), estos son:
| Selector | Número de enteros (x) | Tamaño de los enteros en bits (y = ⌊28/x⌋) | Bits sin usar |
|---|---|---|---|
| 0 (0000) | 28 | 1 | 0 |
| 1 (0001) | 14 | 2 | 0 |
| 2 (0010) | 9 | 3 | 1 |
| 3 (0011) | 7 | 4 | 0 |
| 4 (0100) | 5 | 5 | 3 |
| 5 (0101) | 4 | 7 | 0 |
| 6 (0110) | 3 | 9 | 1 |
| 7 (0111) | 2 | 14 | 0 |
| 8 (1000) | 1 | 28 | 0 |
En Simple16 existen 16 patrones diferentes, identificados desde el 0 (0000) hasta el 15 (1111), donde ninguno tiene bits sin usar, aprovechando cada bit posible. Estas combinaciones son:
| Selector | Número de enteros (x) | Tamaño de los enteros en bits |
|---|---|---|
| 0 (0000) | 28 | 28 × 1 bit |
| 1 (0001) | 21 | 7 × 2 bits, 14 × 1 bit |
| 2 (0010) | 21 | 7 × 1 bit, 7 × 2 bits, 7 × 1 bit |
| 3 (0011) | 21 | 14 × 1 bit, 7 × 2 bits |
| 4 (0100) | 14 | 14 × 2 bits |
| 5 (0101) | 9 | 1 × 4 bits, 8 × 3 bits |
| 6 (0110) | 8 | 1 × 3 bits, 4 × 4 bits, 3 × 3 bits |
| 7 (0111) | 7 | 7 × 4 bits |
| 8 (1000) | 6 | 4 × 5 bits, 2 × 4 bits |
| 9 (1001) | 6 | 2 × 4 bits, 4 × 5 bits |
| 10 (1010) | 5 | 2 × 5 bits, 3 × 6 bits |
| 11 (1011) | 5 | 3 × 6 bits, 2 × 5 bits |
| 12 (1100) | 4 | 4 × 7 bits |
| 13 (1101) | 3 | 1 × 10 bits, 2 × 9 bits |
| 14 (1110) | 2 | 2 × 14 bits |
| 15 (1111) | 1 | 1 × 28 bits |
Ejemplos
- Supongamos que tenemos el siguiente arreglo de enteros: 178 – 274 – 56. Tenemos que, respectivamente, sus formas en binario son: 10110010 – 100010010 – 111000 Como son 3 elementos y ninguno supera los 9 bits entonces se puede almacenar utilizando el patrón descrito en la el 6to selector de Simple9. Usando esto el arreglo anterior quedaría de la siguiente manera: 0110 010110010 100010010 000111000 0, donde los primeros 4 bits representan el selector, los siguientes tres grupos de 9 bits los valores y el último bit es el sobrante.
- Descrito en Simple16 la metodología es similar. Revisando la tabla correspondiente encontramos que el selector número 13 sirve para este caso, con un número de 10 bits y dos de 9 bits. Esto quedaría de la siguiente forma: 1101 0010110010 100010010 000111000 Si bien se ve bastante similar al caso anterior, hay que considerar que tiene un elemento con un bit más, lo que permite que el primer elemento sea más grande de lo que podría ser en Simple9.
- Si bien estos casos están dentro de los patrones, puede ocurrir que a veces no entra si es que son muchos o muy grandes. Usemos el siguiente arreglo como ejemplo: 275 – 14136 – 78 – 153 – 5, cuyas representaciones en binario son, respectivamente: 100010011 – 11011100111000 – 1001110 – 10011001 – 101. Como se puede apreciar 14136 supera la cantidad de bits para varios selectores, excepto 7 y 8, por lo que usaremos el primero al ser el primero en no es superado por la cantidad de bits del valor. Luego este se escribiría como: 0111 00000100010011 11011100111000. Sin embargo, esto deja 3 elementos afuera. Para poder también almacenarlos se repite el proceso con los elementos restantes, lo que generaría el siguiente patrón de bits: 0110 001001110 010011001 000000101 0. Finalmente, el resultado de la transformación del arreglo de valores a Simple9 sería lo que se obtiene tras concatenar el primero sobre el segundo, siendo así el valor final: 0111 00000100010011 11011100111000 0110 001001110 010011001 000000101 0
Aplicación del Código
Simple-9
#include <bits/stdc++.h>
using namespace std;
class Simple_9{
private:
vector<unsigned> val;
unsigned selector[9][3] ={
{28, 1, 0x0000001},
{14, 2, 0x0000003},
{9 , 3, 0x0000007},
{7 , 4, 0x000000f},
{5 , 5, 0x000001f},
{4 , 7, 0x000007f},
{3 , 9, 0x00001ff},
{2 ,14, 0x0003fff},
{1 ,28, 0xfffffff}
};
public:
Simple_9(vector<unsigned> arr){
unsigned sz = arr.size(), left = 0;
while(left < sz){
unsigned temp = 0;
int sel = 7;
bool selCorrect = true;
while(sel>=0 && selCorrect){
if(selector[sel][0] > sz-left){
selCorrect = false;
continue;
}
for (unsigned i = 0; i <= selector[sel][0]; ++i){
if(i == selector[sel][0]){
sel--;
break;
}
if(arr[left + i] > selector[sel][2]){
selCorrect = false;
break;
}
}
}
sel++;
temp += (sel<<28);
for (unsigned i = 0; i < selector[sel][0]; ++i){
temp += ((arr[left+i]) << (28 - (selector[sel][1])*(i+1)));
}
val.push_back(temp);
left += selector[sel][0];
}
}
vector<vector<bool>> return_32bits(){
vector<vector<bool>> vec;
for(unsigned v : val){
vector<bool> binaryNum(32);
unsigned n = v, i = 0;
while (n > 0) {
binaryNum[31-i] = n % 2;
n = n / 2;
i++;
}
vec.push_back(binaryNum);
}
return vec;
}
vector<unsigned> return_vals(){
vector<unsigned> vec;
for(unsigned v : val){
unsigned sel = ((v>>28) & 0x0F);
for (int i = 0; i < selector[sel][0]; ++i)
{
vec.push_back((v >> (28 - (selector[sel][1])*(i+1))) & selector[sel][2]);
}
}
return vec;
}
};
Simple-16
#include <bits/stdc++.h>
using namespace std;
class Simple_16 {
private:
vector<unsigned> val;
vector<pair<unsigned,vector<unsigned>>> selector =
{
{28,vector<unsigned>(28,1)},
{21,{ 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}},
{21,{ 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1}},
{21,{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2}},
{14,vector<unsigned>(14,2)},
{9 ,{ 4, 3, 3, 3, 3, 3 ,3, 3, 3}},
{8 ,{ 3, 4, 4, 4, 4, 3, 3, 3}},
{7 ,vector<unsigned>(7,4)},
{6 ,{ 5, 5, 5, 5, 4 ,4}},
{6 ,{ 4, 4, 5, 5, 5 ,5}},
{5 ,{ 6, 6, 6, 5 ,5}},
{5 ,{ 5, 5, 6, 6 ,6}},
{4 ,{ 7, 7, 7, 7}},
{3 ,{10, 9, 9 }},
{2 ,{14,14}},
{1 ,{28}}
};
public:
Simple_16(vector<unsigned> arr) {
unsigned sz = arr.size(), left = 0;
while(left < sz){
unsigned temp = 0;
int sel = 15, act_sel = 14;;
while(act_sel>=0){;
if(selector[act_sel].first > sz-left){
break;
}
for (unsigned i = 0; i <= selector[act_sel].first; ++i){
if(i == selector[act_sel].first){
sel = act_sel;
act_sel--;
break;
}
if(arr[left + i] > (1<<selector[act_sel].second[i])-1){
act_sel--;
break;
}
}
}
temp += (sel<<28);
unsigned right = 28;
for (unsigned i = 0; i < selector[sel].first; ++i){
right -= selector[sel].second[i];
temp += ((arr[left+i]) << right);
}
val.push_back(temp);
left += selector[sel].first;
}
}
vector<vector<bool>> return_32bits() {
vector<vector<bool>> vec;
for(unsigned v : val){
vector<bool> binaryNum(32);
unsigned n = v, i = 0;
while (n > 0) {
binaryNum[31-i] = n % 2;
n = n / 2;
i++;
}
vec.push_back(binaryNum);
}
return vec;
}
vector<unsigned> return_vals() {
vector<unsigned> vec;
for(unsigned v : val){
unsigned sel = ((v>>28) & 0x0F);
unsigned right = 28;
for (int i = 0; i < selector[sel].first; ++i)
{
right -= selector[sel].second[i];
vec.push_back((v >> right) & ((1<<selector[sel].second[i]) - 1));
}
}
return vec;
}
};
Referencias
- Chow, K., Tzamarias, D. E. O., Hernández-Cabronero, M., Blanes, I., & Serra-Sagristà, J. (2020). Analysis of Variable-Length codes for integer encoding in hyperspectral data compression with the K2-Raster Compact data structure. Remote Sensing, 12(12), 1983. https://doi.org/10.3390/rs12121983
- Buttcher S., L. A. Clarke C., V. Cormack G. (2010). Information Retrieval: Implementing and Evaluating Search Engines. Cambridge, Massachusetts, London, England: The Massachusetts Institute of Technology Press.