Seleccionar página

Ahora todo es datos y compresión.

Videos e imágenes más grandes en menos espacio.

Como la TARDIS, básicamente.

Pero, ¿cómo se empieza a comprimir un archivo?

¿Dónde están las bases para ello?

En esta entrada veremos un ejemplo simple: compresión de cadenas.

Redundancia

La compresión se basa en reconocer la redundancia, para después erradicarla de la faz de la Tierra.

Porque, ¿para qué tener un dato repetido?

Es como comprar dos juguetes idénticos, dejando uno sin abrir para “colección”.

También debemos decir que la compresión se basa en dos operaciones: compresión y descompresión.

Queremos que lo que vamos a comprimir ocupe menos espacio, sí, pero también queremos volver a reconstruir esa información.

De lo contrario, es equivalente a tirar todo a la basura.

Así pues, imaginemos que tenemos un archivo como el siguiente:

2016-10-26 | Mie Oct 26, 2016 | 12:38 AM | 18.36
2016-10-27 | Jue Oct 27, 2016 | 02:22 PM | 18.44
2016-10-28 | Vie Oct 28, 2016 | 01:06 PM | 18.42
2016-10-29 | Sab Oct 29, 2016 | 11:59 AM | 18.4
2016-10-30 | Dom Oct 30, 2016 | 12:12 PM | 18.45

Si lo guardamos, descubrimos que ocupamos 243 bytes.

Pero, ¿es toda ésa información necesaria?

¿Qué se puede eliminar?

Por ejemplo, la primera columna y la segunda cuentan con la misma información: una fecha.

Una columna muestra una versión más utilizada por la computadora, mientras que la segunda columna muestra algo más fácilmente digerible para nosotros los humanos.

Como se incluye la misma información, o se puede inferir en base a otros datos, la información es redundante.

Es decir, podemos eliminar la segunda columna y el archivo seguiría conteniendo lo mismo.

Por lo tanto, nuestro archivo puede quedar como se muestra en el listado 2:

2016-10-26 | 12:38 AM | 18.36
2016-10-27 | 02:22 PM | 18.44
2016-10-28 | 01:06 PM | 18.42
2016-10-29 | 11:59 AM | 18.4
2016-10-30 | 12:12 PM | 18.45

Quedan 148 bytes.

Representación

Una vez que se ha eliminado la redundancia, nos preguntamos, ¿qué se puede modificar para ocupar menos espacio?

Por ejemplo, para nosotros es más o menos lo mismo decir “son las 02:22 PM” a “son las 14:22”.

Por supuesto, no es tan natural y algunas veces tenemos que hacer la resta en nuestra cabeza para saber qué hora es.

Empero, la información sigue siendo la misma (al menos, para una computadora).

Y, si cambiamos de “02:22 PM” a “14:22”, nos ahorramos 3 caracteres: un espacio y los dos dígitos de “AM” o “PM”.

Con ese cambio, tenemos el resultado como en el listado 3.

2016-10-26 | 12:38 | 18.36
2016-10-27 | 14:22 | 18.44
2016-10-28 | 13:06 | 18.42
2016-10-29 | 11:59 | 18.4
2016-10-30 | 12:12 | 18.45

Son 15 bytes menos, quedan 133.

Espacio innecesario

Ya que tocamos el tema del espacio entre la hora y el AM o PM, ¿para qué está realmente allí?

Muchas veces, el espacio es solamente para que nuestras mentes puedan procesar la información.

A la computadora no le importa, y tampoco a nosotros pues queremos empacar eficientemente.

Así que, eliminamos el espacio en blanco entre nuestros separadores (los “|”), y tenemos la tercer versión:

2016-10-26|12:38|18.36
2016-10-27|14:22|18.44
2016-10-28|13:06|18.42
2016-10-29|11:59|18.4
2016-10-30|12:12|18.45

Esto nos ahora cuatro caracteres más por línea (para un total de 20 bytes en el archivo).

Empezando lo esotérico

Una vez que se han hecho las cosas “más obvias”, lo que queda son operaciones extrañas con las representaciones de los datos.

Una de ellas es preguntarnos, ¿es una representación de ancho fijo o de ancho variable?

Por ejemplo, la fecha siempre viene en 10 caracteres: cuatro para el año, dos para el mes, y dos para el día.

Podría ser variable, por ejemplo, el primero de enero: 2016-1-1.

Éso rompería el patrón y nos haría buscar el separador “|”.

No obstante, para esos días lo rellenamos de ceros, como 2016-01-01.

¿Y éso qué?

Hay que saber si lidiamos con ancho fijo o ancho variable.

¿Por qué?

Porque si todo es fijo, no hay necesidad de separadores (pero se crea una necesidad de contar posiciones).

La tercera columna parece de ancho fijo, pero no lo es.

El último elemento jode todo, porque tiene sólo una posición decimal.

Aquí, como diseñadores de nuestro algoritmo, tenemos como opción dejarlo como está, con uno o dos decimales.

O podemos ajustar todos los número a dos decimales y tratarlo como ancho fijo.

En este caso, opto por tratar todo como ancho fijo, y convertir ese .4 en .40, como en el listado 4:

2016-10-26|12:38|18.36
2016-10-27|14:22|18.44
2016-10-28|13:06|18.42
2016-10-29|11:59|18.40
2016-10-30|12:12|18.45

¿Y éso de qué sirve si añadió información a mi archivo en lugar de eliminar?

Porque ahora que todo es ancho fijo, no hay necesidad de NINGÚN separador.

No guiones entre fechas, no dos puntos entre hora, no punto decimal en la última columna, y tampoco las barras separadoras de columnas.

Éso nos da lo siguiente:

2016102612381836
2016102714221844
2016102813061842
2016102911591840
2016103012121845

Hasta allí, hemos eliminado información redundante, espacios en blanco, y cambiado la codificación de unos datos.

Seis caracteres menos, un total de treinta más en el basurero :D.

Ya es lo suficientemente ininteligible si no sabemos de dónde viene.

Sin embargo, lo esotérico acaba de empezar…

Jugando con los bits

A partir de este punto, siguen transformaciones a nivel bit.

Todo surge de un mayor conocimiento de nuestra estructura de datos.

Mientras que nuestra fecha con dígitos que podemos entender sigue ocupando 8 bytes, hay un tipo de dato que ocupa únicamente tres bytes en MySQL.

¿Cómo lo logran?

Ni puta idea.

Pero, nosotros conocemos al menos unas cositas que podemos transformar.

Sabemos que los días no pasan de 31.

Y los meses no pasan de 12.

Por lo tanto, los días necesitan 5 bits (25 = 32).

Y los meses necesitan 4 bits (24 = 16).

Así pues, en realidad necesitamos 9 bits, no los 32 bits que por ahora ocupan.

Para el año, resulta que 11 bits nos dan un rango para llegar hasta el año 2048.

No tendríamos que preocuparnos por poco más de 30 años sobre nuestros datos, asumiendo que son datos hasta el día actual.

Peeero… es difícil crear una estuctura de datos que no contenga un múltiplo de 8.

Si tenemos en cuenta que el próximo múltiplo tras sumar bits de días (5), bits de meses (4), y bits de años (11), descubriríamos que es el 24, o tres bytes.

Así pues, los ocho caracteres del año los podemos condensar a 24 bits: 15 para el año, 4 para el mes, y 5 para el día.

Si aplicamos una lógica similar al siguiente conjunto de datos, de horas, minutos, y dos números de dos dígitos, llegamos a otra estructura similar:

  • cinco bits para la hora,
  • seis bits para los minutos,
  • siete bits para la parte entera,
  • y siete bits para la parte decimal.

Tras concatenar todo éso, y transformarlo en hexadecimal, tenemos lo siguiente:

fc15a098924
fc15be5892c
fc15cd1892a
fc15dbec928
fc15ec3092d

Logramos remover otros tres bits de la cadena original :D.

Sabrá Dios que mierda dice, pero está comprimido.

Y, aún podemos continuar, haciendo compresiones arcanas.

Por ejemplo, podemos usar un sistema base 32, expandiendo los símbolos con más letras del abecedario.

Éso seguiría reduciendo la cantidad de caracteres, de 11 a 6.

No obstante, creo que el punto de cómo se va realizando la compresión está un tanto más claro ahora.

Pero, ¡ya hemos hecho mucho!

Empezamos en 243 bytes y bajamos a 59 bytes en total.

El programa para compresión

Así que, de las observaciones anteriores, se crea el siguiente código:

#!/usr/bin/python
# -*- coding: utf8 -*-

def cambiarFormatoDeHoras(cadenaDeHora):
    amPm = cadenaDeHora[-2:]
    horas = int(cadenaDeHora[0:2])
    minutos = int(cadenaDeHora[3:5])

    if amPm == "AM" and horas == 12:
        horas = 0
    elif amPm == "PM" and horas != 12:
        horas += 12

    return str(horas).zfill(2) + ":" + str(minutos).zfill(2)

def cambiarNumeroAAnchoFijo(cadenaDeNumero):
    posicionDelPunto = cadenaDeNumero.index('.')
    parteEntera = "00" + str(int(cadenaDeNumero[0:posicionDelPunto]))
    parteDecimal = str(int(cadenaDeNumero[posicionDelPunto + 1:])) + "00"
    return parteEntera[-2:] + "." + parteDecimal[0:2]

archivo_entrada = open('datos_sin_compresion.dat', 'r')
archivo_salida = open('datos_comprimidos.dat', 'w')
for linea in archivo_entrada:
    # Paso 1: Eliminar la segunda columna pues es redundante.
    lineaProcesada = linea[0:10] + linea[29:]
    # Paso 2: Cambiar el formato de horas.
    formato24 = cambiarFormatoDeHoras(lineaProcesada[13:21])
    lineaProcesada = lineaProcesada[0:10] + " | " + formato24 + lineaProcesada[21:]
    # Paso 3: Eliminar espacio innecesario.
    lineaProcesada = lineaProcesada[0:10] + "|" + lineaProcesada[13:18] + "|" + lineaProcesada[21:]
    # Paso 4: Hacer número de ancho fijo.
    numeroAnchoFijo = cambiarNumeroAAnchoFijo(lineaProcesada[17:])
    lineaProcesada = lineaProcesada[0:10] + "|" + lineaProcesada[11:16] + "|" + numeroAnchoFijo
    # Paso 5: Eliminar separadores innecesarios.
    cadenaSinSeparadores = ""
    for caracter in lineaProcesada:
        if caracter.isdigit():
            cadenaSinSeparadores += caracter
    # Paso 6: Bits combinados en un solo número.
    anio = int(cadenaSinSeparadores[0:4])
    mes = int(cadenaSinSeparadores[4:6])
    dia = int(cadenaSinSeparadores[6:8])
    fechaCodificada = dia | (mes << 5) | (anio << 9)

    hora = int(cadenaSinSeparadores[8:10])
    minutos = int(cadenaSinSeparadores[10:12])
    entero = int(cadenaSinSeparadores[12:14])
    fraccion = int(cadenaSinSeparadores[14:16])
    horaMontoCodificado =  fraccion | (entero << 7) | (minutos << 14) | (hora << 20)

    # Resultado final de nuestra compresión.
    archivo_salida.write(hex(fechaCodificada)[2:].zfill(5) + hex(horaMontoCodificado)[2:].zfill(6) + "\n")

Aquí tomamos un archivo que contiene el listado 1 y nos produce un archivo con el contenido como el listado 5.

No obstante, y si vieron la película de “El Gran Truco”, saben que el truco no está completo sin el tercer acto:

Hay que regresar todo a como estaba.

Descomprimiendo el archivo, restaurando el original

Ya cuando queramos sacar la información del olvido, es necesario pasarla por el descompresor para poder entenderla.

Y éso es lo que hace el próximo código:

#!/usr/bin/python
# -*- coding: utf8 -*-
from datetime import date

archivo_entrada = open('datos_comprimidos.dat', 'r')
archivo_salida = open('datos_reconstruidor.dat', 'w')

def diaDeSemanaEnTresLetras(fecha):
    diaDeSemana = fecha.weekday()
    letras = [
        "Lun",
        "Mar",
        "Mie",
        "Jue",
        "Vie",
        "Sab",
        "Dom"
    ]

    return letras[diaDeSemana]

def mesEnTresLetras(mes):
    letras = [
        "Ene",
        "Feb",
        "Mar",
        "Abr",
        "May",
        "Jun",
        "Jul",
        "Ago",
        "Sep",
        "Oct",
        "Nov",
        "Dic"
    ]

    return letras[mes]

def horasAmPm(horas, minutos):
    if horas < 12:
        sufijo = "AM"
    else:
        sufijo = "PM"
    if horas == 0:
        horas = 12
    elif horas > 12:
        horas -= 12

    return str(horas).zfill(2) + ":" + str(minutos).zfill(2) + " " + sufijo

for linea in archivo_entrada:
    #######################################################
    # Deshaciendo el paso 7.
    #######################################################
    # Decodificar fecha
    enteroFecha = int(linea[0:5], 16)
    anio = enteroFecha >> 9
    mes = enteroFecha >> 5 & 0xf
    dia = enteroFecha & 0x1f
    columna1 = str(anio).zfill(4) + "-" + str(mes).zfill(2) + "-" + str(dia).zfill(2)
    # Decodificar hora y monto.
    enteroHoraMonto = int(linea[5:11], 16)
    horas = enteroHoraMonto >> 20
    minutos = enteroHoraMonto >> 14 & 0x3f
    entero = enteroHoraMonto >> 7 & 0x7f
    decimal = enteroHoraMonto & 0x7f
    #######################################################
    # Buscando la información perdida en el paso 1.
    #######################################################
    fecha = date(anio, mes, dia)
    letrasDia = diaDeSemanaEnTresLetras(fecha)
    letrasMes = mesEnTresLetras(mes)
    columna2 = letrasMes + " " + letrasDia + " " + str(dia).zfill(2) + ", " + str(anio).zfill(4)
    #######################################################
    # Regresando 24 horas a 12.
    #######################################################
    columna3 = horasAmPm(horas, minutos)
    #######################################################
    # Eliminando el padding de decimales.
    #######################################################
    columna4 = str(entero).zfill(2) + "."
    cadenaDecimal = str(decimal).zfill(2)
    if cadenaDecimal[1] == "0":
        cadenaDecimal = cadenaDecimal[0]
    columna4 += cadenaDecimal

    #######################################################
    # Reconstuyendo la línea.
    #######################################################
    lineaReconstruida  = columna1 + " | "
    lineaReconstruida += columna2 + " | "
    lineaReconstruida += columna3 + " | "
    lineaReconstruida += columna4

    print lineaReconstruida

¿Qué más hay?

Bueno… como dije, se puede usar un sistema base 32.

O caracteres que no se imprimen.

Y otras transformaciones matemáticas extrañas.

Encontrarían las cosas sorprendentes que se pueden hacer a un conjunto de ceros y unos.

Pero, éso es básico de compresión:

  • eliminar redundancia,
  • eliminar espacios o caracteres innecesarios, y
  • transformar datos a cosas que ocupen menos espacio.

¿Alguna duda?