lunes, noviembre 28, 2011

Leyendas urbanas sobre el JPEG

Una amiga me comentó hace poco que un profesor suyo le había dicho que la calidad de las imágenes guardadas en JPEG se degradaba cada vez que se abrían para visualizarlas.

Le expliqué que es cierto que las imágenes en JPEG pierden calidad, pero sólo cada vez que se escriben. Me quedé pensando un momento en mis días de la universidad, en la transformada del coseno y en su puta madre, y pensé que seguramente llegaría un punto en el que después de codificar y decodificar varias veces en cadena una imagen, se llegaría a un punto fijo, en el que no se perdería más calidad.

Me daba bastante pereza ponerme a probarlo, pero al final tiré de scripting en Python una vez más y he aquí los resultados:



import Image
import ImageMath
import sys

def main():
    prefix, suffix = sys.argv[1].split('.')

    prev = Image.open(sys.argv[1])
    go_on = True
    i = 0
    while go_on and i < 100:
        name = prefix + str(i) + '.' + suffix
        print 'name=',name
        prev.save(name)
        next = Image.open(name)
        diff = ImageMath.eval('abs(float(a) - float(b))', a=next, b=prev)
        go_on = tuple(next.getdata()) != tuple(prev.getdata())
        prev = next
        hist = diff.histogram()
        i += 1
        print hist


if __name__ == "__main__":
    sys.exit(main())

El programilla va imprimiendo el histograma de la diferencia entre dos imágenes consecutivas y se para cuando todos los píxels están a cero. Probando con un par de imágenes, parece que el punto fijo se alcanza tras unas cuantas iteraciones, entre 8 y 40. Así que no temáis demasiado por una degradación sin límites de vuestras fotos si las andáis retocando sobre los JPEGs, aunque nunca está de más guardar los originales en RAW, TIFF o PNG.

domingo, noviembre 13, 2011

Otra de exploración de árboles de palabras

El lunes pasado se cayó Internet en el curro. Mientras yo estaba con mis pajas mentales, mis queridos compañeros nerds se empezaron a aglomerar en torno a un ordenador. Para no desentonar, me acerqué yo también y pregunté que qué regalaban.

Resultó que estaban jugando con un programita de consola (no me refiero a xbox ni ps3, sino a terminal de texto) que muestra una parrilla con letras y nosotros tenemos que introducir todas las palabras inglesas que se puedan formar con las letras siguiendo un camino de casilla en casilla.

Acordándome del mítico post sobre El Melenas de Cifras y Letras y de cómo le quité la gracia al juego del facebook de hacer anagramas, decidí que iba petarlo en cuanto volviese Internet y pudiese descargarme la lista de palabras inglesas...

Total, que como buen procrastinador, me puse a hacer mi script en Python, que ahora pasaré a explicar:

from itertools import product
import sys

# not much shorter, but much funnier to write than
# [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
# at first I used range(-1,2), but (-1,0,1) is cleaner and shorter
neighbours = [(i,j) for i,j in product(*[(-1,0,1)]*2) if i or j]
allow_repeat = True

def make_tree(words_list):
        base = {}
        for word in words_list:
                d = base
                for c in word:
                        if c not in d:
                                nd = {}
                                d[c] = nd
                                d = nd
                        else:
                                d = d[c]
                d[None] = None # complete word marker
        return base

def parse_matrix(text):
      return map(str.upper, filter(None, (filter(str.isalpha, line) for line in text)))

def is_valid_and_prefix(d, word):
        for c in word:
                if c not in d:
                        return False, False
                else:
                        d = d[c]
        valid = None in d
        prefix = len(d) > valid # more keys than None
        return (valid, prefix)

def successors(word, path, matrix):
        i,j = path[-1]
        for di, dj in neighbours:
                ni, nj = i+di, j+dj
                if (ni >= 0 and nj >= 0 and
                    ni < len(matrix) and nj < len(matrix[ni]) and
                    (allow_repeat or (ni,nj) not in path)):
                        successor = word + matrix[ni][nj], path + [(ni,nj)]
                        yield successor

def find_words(d, path, word, matrix):
        valid, prefix = is_valid_and_prefix(d, word)
        if valid:
                yield word
        if prefix:
                for nw, np in successors(word, path, matrix):
                        for x in find_words(d, np, nw, matrix):
                                yield x

if __name__ == '__main__':
        wordlist = sys.argv[1]
        tree = make_tree(x.upper().strip() for x in open(wordlist))
        matrix = parse_matrix(sys.stdin.readlines())
        words = set()
        for i,j in product(range(len(matrix)), range(len(matrix[0]))):
                c = matrix[i][j]
                words |= set(find_words(tree, [(i,j)], c, matrix))
        for w in sorted(words, key=len):
                print w

Para usarlo, recibe como primer y único argumento el nombre del fichero con el corpus de palabras válidas y lee por la entrada estándar la "sopa de letras" (de la cuál descartará cualquier caracter que no sea alfabético, así que puede estar formateada como os dé la gana).

¿Cómo funciona el jodío? Pues muy fácil, esta vez en lugar de construir un hash de las palabras que ignorase el orden de aparición de las letras, nuestra estructura de consulta es un arbolito (como bien indica el nombre de la función make_tree).

Este arbolito es básicamente un puñado de diccionarios (no en el sentido de RAE, sino tablas asociativas) anidados, en el cuál la clave es una letra y el valor, pues otro diccionaro. Hay un caso especial en el que algunos diccionarios tendrán una entrada None:None.

Para saber si una palabra está en el diccionario (esta vez sí, en el sentido de RAE, Collins, Oxford, etc.), tenemos que ver si podemos llegar a un nodo que tenga una clave None pegando saltitos por las ramas que tengan como clave cada letra de nuestra palabra de forma consecutiva. Esto es lo que hace la función is_valid_and_prefix, que además nos dice si la palabra es un prefijo de otras.

A partir de aquí es pan comido, sólo tenemos que hacer el típico backtracking por las casillas de la rejilla, podando cuando lleguemos a palabras que no son prefijo de ninguna y devolviendo aquellas que sean palabras completas. Los generadores de Python ayudan mucho para escribir este código de forma elegante.

Posibles optimizaciones:
  • Reemplazar los diccionarios por alguna otra estructura más compacta en memoria, ya que buscar linealmente entre un máximo de 28 caracteres seguramente sea más eficiente que un hash lookup.
  • Pasar sólo el sub-árbol con los sufijos de la palabra que estamos explorando en cada nivel de la búsqueda... No es que vaya a ser una gran diferencia, pero si ya estamos seguros de que vamos por un prefijo válido ¿para qué comprobarlo otra vez?
Lo más gracioso es la cantidad de palabras que se pueden formar con una matriz pequeñita si permitimos repetir casillas. Para probar, usé esta matriz de entrada (sí, ya sé que tiene algunas palabras muy obvias):

DONE
OIRT
PASS

¿Y a que no sabéis cuántas palabras había escondidas? 848.

martes, noviembre 08, 2011

Rock Estatal

Hace un buen puñado de años, cuando había una tienda Tipo en la C/Fuencarral a la que solía ir a mirar discos con algunos colegas; siempre me sorprendía ver la sección de "Rock Estatal", donde estaban todos los grupos chungos del país.

Aún a día de hoy podemos ver tamaña lerdez en su web:


¿Tanta es la aversión que tienen los guarros a palabras como español o nacional que llegan a utilizar otras que no vienen al caso?

Porque tampoco hace falta ser un erudito (basta con echarle un vistazo al diccionario o haber prestado un poquito de atención en clase cuando explicaban la diferencia entre país, nación y estado en lugar de estar fumando porros) para saber que el Estado es la estructura política y organizativa, el gobierno, la policía, los jueces y todas esas cositas que tanto les gustan nuestros amigos los punkis.

Ya me los imagino yendo a un bar, pidiendo un whisky y cuando el camarero pregunta ¿Nacional o importación? responden muy ufanos: Estatal. Pero como el Tito Fortran siempre ha tenido vocación didáctica, os voy a dar algunos sinónimos para que no os salgan sarpullidos y no hagáis el gilipollas: autóctono, local, de la tierra, patrio, vernáculo (qué grande sería pedir un güisqui vernáculo para que luego te pongan un puto DYC)...

Mientras tanto, tenemos a los panderetas de Rajoy y Rubalcaba diciendo más chorradas en la tele. La verdad es que no estoy viendo el debate, pero me la suda, porque sé de sobra de lo que están hablando, porque ya lo he visto cientos de veces. Estarán echándose mierda el uno al otro, Rajoy dirá que hay paro y estamos en crisis, Rubalcaba hablará de los años del gobierno de Aznar, Rajoy le hablará del gobierno de Zapatero, hablarán de ETA para intentar sumarse puntos, etc.

En fin, cuánta mierda por todas partes.

martes, noviembre 01, 2011

Si los lenguajes de programación fuesen vehículos

Esto es una chorrada que comenté con un colega en IMG hace un par de años, que elaboré un poco cuando volví a España y ahora que estoy de nuevo en UK me he decidido a terminar, aunque sea a lo cutre.

Se trata de hacer símiles entre vehículos y lenguages de programación (a cada cuál más estúpido). Vamos allá.

C y C++: Son una moto para la que no tienes casco. Van muy rápido, consumen poco, pero como te pegues una hostia, vas apañado. C++ es como añadirle un sidecar a la amoto; se supone que es práctico, pero realmente parece un engorro más que otra cosa.


Python: una bicicleta. Es sencillo, es divertido, te lleva a los sitios que quieres (no muy rápido), pero es peligroso montar con varios colegas al mismo tiempo.


Java: un tractor. No es bonito ni cómodo, pero hace su trabajo como ninguno y le puedes poner montones de accesorios.


Ruby: es el Homer-Mobile. Montones cosas que parece que molan, pero si las pones todas juntas, son una puta mierda.



Lisp (y variantes): son un vehículo lunar. Llegan hasta donde no llega ningún otro. Pero hay que ser astronauta (por lo menos) para manejarlos. Aunque bien pensado, hay otra cosa que tienen en común, nos parecen del futuro, pero realmente son tecnología de los años 60.



Y ya me he cansado.