- Se incorporó
- 16 Noviembre 2021
- Mensajes
- 473
En verdad no sabía como ponerle al título, pero hace un tiempo que vengo estudiando algoritmos de compresión, y fuera de maravillarme por la simpleza de algunos algoritmos creo que di con uno bien cutre. Dudo complementamente que sea eficiente, pero es interesante, lo suficiente como para dejarlo acá para algún inspirado en el futuro que se interese y gusta de leer.
Primero voy a explicar un preámbulo, todo para dummies (como yo) que pueden entender los unos y los ceros en arreglos y matrices, nada muy complejo.
Supongamos un vector de bits denominado V. Para visualizarlos mejor, están separados en grupos de 4 bits, nibbles o 1/2 octeto, en concreto hay 22 nibbles, 88 bits u 11 bytes. La tira entera como un vector único no nos dice nada, pero si se realiza una agrupación como la de arriba, y se lee todo secuencialmente, en un diccionario se puede empezar a contar cada grupo. Por lo que se terminaría por tener para cada grupo del diccionario cuantas repeticiones de éste existen en el vector que se está analizando a n-bits.
Voy a asumir que no se entendió así que vamos por lo mas básico.
Diccionario
Es una estructura, que almacena claves y valores, es como el json, salvo que aquí las claves no se repiten, y para el ejemplo de arriba, los valores son enteros y las claves son tiras de bits no repetidas.
La gracia del diccionario es que las posiciones de memoria son accesibles vía "posición", evitando así la búsqueda mediante un bucle, disminuyendo enormemente el consumo en tiempo de ejecución del algoritmo que lo usa.
Lo que se ve arriba, sin ordenar son todas las apariciones de los grupos de 4 bits en el vector. Si se realiza la suma de todos los valores de aparición de las claves, se obtendrá el total de nibbles que es 22.
Hasta acá me imagino que me siguen.
Acá a lo mejor ya se estarán preguntando si de alguna forma se pudieran remover dichas repeticiones, y la respuesta es sí, pero no es tan simple como meter directamente los índices del diccionario en binario al vector.
Problemática 1
La primera problemática que se visualiza acá es que para representar el rango de las posiciones del diccionario, es decir que si extraemos todas las claves tal cual están ahora en un vector K y a partir de dicho vector usaramos los índices del mismo para reemplazar las apariciones terminaríamos con una especie de cifrado, mas no ahorrando espacio. Lo cual es el fin de un algoritmo de compresión. Y ésto viene dado por log₂(12) = 3,58... redondeado al techo, osea 4 (2^4-1 = 15). Lo que dice que para representar 12 elementos (0-12) se necesitan 4 bits, así que ahora si que se entenderá que sustituir 4 bits por 4 bits no tiene sentido en compresión, pero si en cifrado, lo cual no es el caso.
Problemática 2
Bien, pudiéramos pensar que a simple vista bastaría con meter un identificador de menos cantidad de bits, y hasta cierto punto es cierto, pero que pasaría si elegimos mal dicho identificador y resulta que dicho elemento ya estaba siendo ocupado por el cuerpo del vector V, pues no tendríamos como reconstruír la data.
Tambien se habrán fijado que el espacio de 4 bits en el rango que mencioné no está del todo completo, porque (2^4-1 = 15) - 11 = 4, lo que en español dice que al espacio de 4 bits le están sobrando 4 elementos.
Ahora se preguntarán, de que me sirven esos 4 elementos, pues bien, ahora entran al juego las apariciones de bits en rango n-bits.
Se sabe que n-bits sin signo pueden representar x cantidad de enteros, pero no necesariamente todo el rango representable debe estar presente al interior de un archivo binario. Por lo que como se vió arriba, perfectamente podríamos tener elementos inexistentes.
Éste sería el rango 0-15 completo para 4 bits indicando cuales valores existen y cuales quedarían libres.
Ésto se repite para cualquier archivo, independiente del formato, del tipo, etc, cualquier archivo binario tiene para un espacio dado de bits x cantidad de huecos en el rango que quedarán libres. Es al azár mirado por encima, pero dentro de los contenedores (formatos) deberían existir patrones en dichos huecos, cosa que no voy a tratar acá.
Compresión
Para ésto debemos movernos a un espacio de 5 bits.
Como se aprecia, moverse a un espacio mas grande hace que al final falten bits para tener grupos del mismo tamaño, es algo que pasará al moverse hacia arriba o hacia abajo en el número de bits de los grupos leídos dentro de V. No es algo que importe en éstos momentos. Ahora tocaría repetir el diccionario para examinar como se repiten los elementos, mientras mas arriba se sube en el espacio de n-bits, menos repeticiones para los elementos se deberían encontrar, por ende al llegar a grupos de +128 bits, dado que las representaciones enteras se vuelven mas grandes, se requerirá mas data para encontrar mas representaciones en archivos pequeños.
Si se fijaron, ahora ordené distinto el diciconario, las repeticiones con mas apariciones quedaron arriba, y las con menos repeticiones quedaron abajo, (como si fuera un árbol de Huffman).
Ahora si volvemos a la problemática 2 de mas arriba, volveríamos a un camino sin salida dado que no podemos reemplazar un elemento de 5 bits con otro de 5 bits, pero si se recuerdan, en el espacio de 4 bits nos quedaron 4 elementos libres, así que aquí si es donde podríamos por cada elemento repetido ahorrarnos 1 bit usando los 4 identificadores faltantes. Por lo que nuestro diccionario se recortaría por orden de repeticiones descendente de la siguiente forma, salvo que ahora en vez de posiciones, usaríamos como claves dichos identificadores de 4 bits.
Con lo que el vector V quedaría de la siguiente manera:
Como se darán cuenta, con 8 reemplazos ahorrando 1 bit por reemplazo, la cuenta queda en 8 bits menos (1 byte), bastante impráctico teniendo en cuenta que el diccionario debe ser agregado al final de V como una estructura compacta, legible, quizá con un marcador diferenciable dentro de un espacio de 1~2-bits, y además el archivo debe ser barrido numerosas veces, lo que nos llevaría a implementaciones en C, Rust, Go, D, etc. Algo que en Python aunque factible, es bien lento de realizar, pero para estudiar y soltar la mano, sirve.
Primero voy a explicar un preámbulo, todo para dummies (como yo) que pueden entender los unos y los ceros en arreglos y matrices, nada muy complejo.
Código:
V = [1111 1101 0011 1111 0010 0111 1010 0100 0011 0011 0010 0001 0001 1001 1100 0111 0101 0001 1110 1100 0100 0101]Supongamos un vector de bits denominado V. Para visualizarlos mejor, están separados en grupos de 4 bits, nibbles o 1/2 octeto, en concreto hay 22 nibbles, 88 bits u 11 bytes. La tira entera como un vector único no nos dice nada, pero si se realiza una agrupación como la de arriba, y se lee todo secuencialmente, en un diccionario se puede empezar a contar cada grupo. Por lo que se terminaría por tener para cada grupo del diccionario cuantas repeticiones de éste existen en el vector que se está analizando a n-bits.
Voy a asumir que no se entendió así que vamos por lo mas básico.
Diccionario
Es una estructura, que almacena claves y valores, es como el json, salvo que aquí las claves no se repiten, y para el ejemplo de arriba, los valores son enteros y las claves son tiras de bits no repetidas.
La gracia del diccionario es que las posiciones de memoria son accesibles vía "posición", evitando así la búsqueda mediante un bucle, disminuyendo enormemente el consumo en tiempo de ejecución del algoritmo que lo usa.
Código:
// diccionario
// posición. clave: valor
d = {
0. 1111: 2,
1. 1101: 1,
2. 0011: 3,
3. 0010: 2,
4. 0111: 2,
5. 1010: 1,
6. 0100: 2,
7. 0001: 3,
8. 1001: 1,
9. 1100: 2,
10. 0101: 2,
11. 1110: 1,
}Lo que se ve arriba, sin ordenar son todas las apariciones de los grupos de 4 bits en el vector. Si se realiza la suma de todos los valores de aparición de las claves, se obtendrá el total de nibbles que es 22.
Hasta acá me imagino que me siguen.
Acá a lo mejor ya se estarán preguntando si de alguna forma se pudieran remover dichas repeticiones, y la respuesta es sí, pero no es tan simple como meter directamente los índices del diccionario en binario al vector.
Problemática 1
La primera problemática que se visualiza acá es que para representar el rango de las posiciones del diccionario, es decir que si extraemos todas las claves tal cual están ahora en un vector K y a partir de dicho vector usaramos los índices del mismo para reemplazar las apariciones terminaríamos con una especie de cifrado, mas no ahorrando espacio. Lo cual es el fin de un algoritmo de compresión. Y ésto viene dado por log₂(12) = 3,58... redondeado al techo, osea 4 (2^4-1 = 15). Lo que dice que para representar 12 elementos (0-12) se necesitan 4 bits, así que ahora si que se entenderá que sustituir 4 bits por 4 bits no tiene sentido en compresión, pero si en cifrado, lo cual no es el caso.
Problemática 2
Bien, pudiéramos pensar que a simple vista bastaría con meter un identificador de menos cantidad de bits, y hasta cierto punto es cierto, pero que pasaría si elegimos mal dicho identificador y resulta que dicho elemento ya estaba siendo ocupado por el cuerpo del vector V, pues no tendríamos como reconstruír la data.
Tambien se habrán fijado que el espacio de 4 bits en el rango que mencioné no está del todo completo, porque (2^4-1 = 15) - 11 = 4, lo que en español dice que al espacio de 4 bits le están sobrando 4 elementos.
Ahora se preguntarán, de que me sirven esos 4 elementos, pues bien, ahora entran al juego las apariciones de bits en rango n-bits.
Se sabe que n-bits sin signo pueden representar x cantidad de enteros, pero no necesariamente todo el rango representable debe estar presente al interior de un archivo binario. Por lo que como se vió arriba, perfectamente podríamos tener elementos inexistentes.
Éste sería el rango 0-15 completo para 4 bits indicando cuales valores existen y cuales quedarían libres.
Código:
0000: 0 [LIBRE]
0001: 1 [EXISTE]
0010: 2 [EXISTE]
0011: 3 [EXISTE]
0100: 4 [EXISTE]
0101: 5 [EXISTE]
0110: 6 [LIBRE]
0111: 7 [EXISTE]
1000: 8 [LIBRE]
1001: 9 [EXISTE]
1010: 10 [EXISTE]
1011: 11 [LIBRE]
1100: 12 [EXISTE]
1101: 13 [EXISTE]
1110: 14 [EXISTE]
1111: 15 [EXISTE]Ésto se repite para cualquier archivo, independiente del formato, del tipo, etc, cualquier archivo binario tiene para un espacio dado de bits x cantidad de huecos en el rango que quedarán libres. Es al azár mirado por encima, pero dentro de los contenedores (formatos) deberían existir patrones en dichos huecos, cosa que no voy a tratar acá.
Compresión
Para ésto debemos movernos a un espacio de 5 bits.
Código:
V = [11111 10100 11111 10010 01111 01001 00001 10011 00100 00100 01100 11100 01110 10100 01111 01100 01000 101]Como se aprecia, moverse a un espacio mas grande hace que al final falten bits para tener grupos del mismo tamaño, es algo que pasará al moverse hacia arriba o hacia abajo en el número de bits de los grupos leídos dentro de V. No es algo que importe en éstos momentos. Ahora tocaría repetir el diccionario para examinar como se repiten los elementos, mientras mas arriba se sube en el espacio de n-bits, menos repeticiones para los elementos se deberían encontrar, por ende al llegar a grupos de +128 bits, dado que las representaciones enteras se vuelven mas grandes, se requerirá mas data para encontrar mas representaciones en archivos pequeños.
Código:
// diccionario
// posición. clave: valor
d = {
0. 11111: 2,
1. 10100: 2,
2. 01111: 2,
3. 00100: 2,
4. 01100: 2,
5. 10010: 1,
6: 01001: 1,
7. 00001: 1,
8: 10011: 1,
9. 11100: 1,
10. 01110: 1,
11. 01000: 1,
12. 101: 1
}Si se fijaron, ahora ordené distinto el diciconario, las repeticiones con mas apariciones quedaron arriba, y las con menos repeticiones quedaron abajo, (como si fuera un árbol de Huffman).
Ahora si volvemos a la problemática 2 de mas arriba, volveríamos a un camino sin salida dado que no podemos reemplazar un elemento de 5 bits con otro de 5 bits, pero si se recuerdan, en el espacio de 4 bits nos quedaron 4 elementos libres, así que aquí si es donde podríamos por cada elemento repetido ahorrarnos 1 bit usando los 4 identificadores faltantes. Por lo que nuestro diccionario se recortaría por orden de repeticiones descendente de la siguiente forma, salvo que ahora en vez de posiciones, usaríamos como claves dichos identificadores de 4 bits.
Código:
// diccionario
// posición. clave: valor
d = {
0. 0000: 11111, // repetido 2 veces
1. 0110: 10100, // repetido 2 veces
2. 1000: 01111, // repetido 2 veces
3. 1011: 00100, // repetido 2 veces
}Con lo que el vector V quedaría de la siguiente manera:
Código:
V = [|0000| |0110| |0000| 10010 |1000| 01001 00001 10011 |1011| |1011| 01100 11100 01110 |0110| |1000| 01100 01000 101]Como se darán cuenta, con 8 reemplazos ahorrando 1 bit por reemplazo, la cuenta queda en 8 bits menos (1 byte), bastante impráctico teniendo en cuenta que el diccionario debe ser agregado al final de V como una estructura compacta, legible, quizá con un marcador diferenciable dentro de un espacio de 1~2-bits, y además el archivo debe ser barrido numerosas veces, lo que nos llevaría a implementaciones en C, Rust, Go, D, etc. Algo que en Python aunque factible, es bien lento de realizar, pero para estudiar y soltar la mano, sirve.