domingo, julio 22, 2012

Renombrando canciones 2.1

Venga, vamos a darnos otra chuta de Python antes de pasar a Javascript...

El otro disco que me bajé tenía las canciones sin los números. Seguramente estarían en los tags id3, pero es algo que me da mucha pereza, así que miré el orden de las pistas en Amazon y me hice otro script ^_^

Este recibe como argumentos dos ficheros, uno con el listado de pistas de Amazon (copiado de la tabla usando ctrl+seleccionar)

  1. Half Remembered Dream
  2. We Built Our Own World
  3. Dream Is Collapsing
  4. Radical Notion
  5. Old Souls
  6. 528491
  7. Mombasa
  8. One Simple Idea
  9. Dream Within A Dream
10. Waiting For A Train
11. Paradox
12. Time

y otro con el nombre de los archivos:

528491.mp3
Dream Is Collapsing.mp3
Dream Within A Dream.mp3
Half Remembered Dream.mp3
Inception Teaser Trailer.mp3
Mind Heist.mp3
Mombasa.mp3
Old Souls.mp3
One Simple Idea.mp3
Paradox.mp3
Projections (bonus track).mp3
Radical Notion.mp3
Time.mp3
Waiting For A Train.mp3
We Built Our Own World.mp3
y se encarga de emparejarlos según cuáles sean más parecidos usando el Longest Common Substring (por lo que debería ser robusto ante pequeños cambios).


#!/usr/bin/env python

import sys
import itertools
import functools
from collections import defaultdict

allchars = (chr(i) for i in range(256))
table = ''.join(x.lower() if x.isalnum() else ' ' for x in allchars)

def memoize(obj):
        cache = obj.cache = {}
        @functools.wraps(obj)
        def memoizer(*args, **kwargs):
                if args not in cache:
                        cache[args] = obj(*args, **kwargs)
                return cache[args]
        return memoizer

@memoize
def lcs(ra, rb):
        if not (ra and rb):
                return 0
        elif ra[0] == rb[0]:
                return 1 + lcs(ra[1:], rb[1:])
        else:
                return max(lcs(ra[1:], rb), lcs(ra, rb[1:]))


def make_all_pairs(group_a, group_b):
        def rank(a, b):
                h = lcs(a.translate(table), b.translate(table))
                return 2.0*h/(len(a) + len(b))

        for ia, a in enumerate(group_a):
                ib, b = max(enumerate(group_b), key=lambda (_, b): rank(a, b))
                yield ia, ib


def format_pairs(number_name, file_ext):
        numbers, track_names = zip(*number_name)
        numbers = map(int, numbers)
        track_names = map(str.strip, track_names)
        file_names, exts = zip(*file_ext)
        for t_i, f_i in make_all_pairs(track_names, file_names):
                print 'mv "%(fname)s.%(ext)s" "%(n)02d - %(tname)s.%(ext)s"' % {
                        'fname' : file_names[f_i],
                        'ext' : exts[f_i],
                        'tname' : track_names[t_i],
                        'n' : numbers[t_i]
                }

tracks, files = (map(str.strip, open(x).readlines()) for x in sys.argv[1:])

number_name = [x.split('.',1) for x in tracks]
file_ext = [x.rsplit('.', 1) for x in files]

format_pairs(number_name, file_ext)

3 comentarios:

  1. Sólo por tocar un poco los huevines...

    ¿Lo del longest common substring, ya que sólo te interesa su longitud, no sería más eficiente hacerlo con Dijkstra?

    x = caracteres pasados de Str1

    y = caracteres pasados de Str2

    Sería con coste 0 en igualdad, avanzando 1 en x Y en y, 1 en diferencia, avanzando 1 en x O en y.

    Luego lcs = (x_max + y_max - coste_total) / 2, o algo así... :-P

    El truco del memoize está bien para evitarse recursiones repetidas, pero explora completamente el espacio de soluciones, mientras que una búsqueda dirigida por Dijkstra puede cortocircuitar las soluciones demasiado absurdas... y el uso de memoria debería ser comparable en el peor caso.

    ResponderEliminar
  2. Se agradece la tocada de huevines hombre, que hace mucho que nadie me escribe por aquí xD

    Que conste que con esta implementación top-down del LCS si los strings son iguales (o uno es prefijo del otro) va del tirón hasta el final sin hacer ningún backtracking.

    De hecho me parece que implementarlo como una búsqueda en un grafo como dices, sería equivalente en complejidad... Me has picado, voy a probarlo :-p

    ResponderEliminar
  3. pues he estado pensando y no compensa, el LCS es O(n·m) y Dijkstra es O(n²), pero aquí hay tantos nodos como pares de letras, así que sería O(n²·m²), mucho peor...

    además hay que tener en cuenta que la mayor ventaja de Dijkstra es que evita ir por aristas con mucho peso hasta que no se han explorado los caminos que son peores, pero aquí todas las aristas son de peso 1 o 0...

    ResponderEliminar