Etiquetas

Actualización: modifiqué radicalmente el algoritmo de selección de HTML alternativos. Es más elegante y predecible, ya no funcionan con pesos sino fundamentado en múltiples colas ordenadas por la “diferencia de texto” usando el algoritmo de Levenshtein.

Hoy se cumplen dos semanas desde que escribí el último apunte. Como cada puente e inicio de vacaciones, estuve muy líado. Con Benjamí hemos quedado de acuerdo que cada seis meses introduciríamos cambios importantes en el Menéame, solemos aprovechar el inicio de las vacaciones de verano y las de navidades para concentrarnos e implementarlas en poco tiempo.

Para estas vacaciones teníamos planeado varias, entre ellas una reprogramación de la versión móvil del Menéame y la inclusión completamente automática de imágenes miniaturas de las webs enlazadas.

La programación de la versión móvil fue trabajosa aunque muy sencilla una vez decidido cómo se iba a hacer (subclases de “Link” y “Comment” con la sobrecarga de las funciones de “imprimir” -print_summary()–). Ojalá todos los desarrollos de web fuesen así de sencillos y programáticos.

Pero lo que más me obsesionó y me llevó mucho tiempo y neuronas quemadas fueron los ciclos de diseñar implementar y probar los algoritmos para detectar las imágenes candidatas y que valiesen la pena para generar e incluir una miniatura. Al final el programa funciona bastante bien y da muy buenos resultados.

Estuve mirando cómo se hace la selección en otros sistemas, aunque no encontré ninguno que sea totalmente automático, si hacen un filtrado para que el usuario seleccione –paso que queríamos evitar–. Analicé por ejemplo el código de Reddit, pero éste es muy simple, demasiado, naïve. Da muchos positivos (logos, publicidad, imágenes no relevantes…) y muchos negativos (por ejemplo por el coeficiente de aspecto que no puede ser mayor a 1.5, lo que por ejemplo no incluiría las fotos panorámicas que suele incluir 20 Minutos en sus noticias).

La complejidad –y lo divertido– de este tipo de programas es que no puedes conocer de antemano todas las “entradas” posibles, es increíble la cantidad de variantes que hay en la forma de incluir imágenes en el HTML –con sus distintas versiones–, dintinguir cuáles de ellas son de la noticia y cuál de otras –por ejemplo “noticias relacionadas”, cuáles son de publicidad o enlaces externas, cuáles son más visibles, etc. Esa es la parte complicada, pero también tiene una ventaja, no hace falta”precisión” abosulta en los resultados, unas pocas miniaturas de menos o más no molestan ni llaman la atención.

El primer paso fue analizar el HTML, encontrar todas las imágenes y elegir entre ellas a la mejor candidata. Para ello se toma primero en cuenta el tamaño si es que tienen especificado en la etiqueta IMG. Si no están completa pero tampoco son menores al mínimo y además no incluyen palabras como “ads” en el URL se marcan como candidatas.

// First filter to avoid downloading very small images
if (($this->&& $this->100) || ($this->&& $this->100)) {
    $this->candidate false;
    return;
}

if (!preg_match('/button|banner|\Wads\W|\Wpub\W|header|rss/i'$this->url) {
    $this->candidate true;
}

Luego se bajan cada una de esas candidatas y se completa la información de tamaño faltante, por lo que se vuelve a hacer un filtrado. Una vez calculado el tamaño de todas se elige a la mejor candidata basada en su posición en el HTML (las primeras tienen más peso), su superficie y aspecto (las más cuadradas y grandes tienen más peso):


$img->coef intval($img->surface()/$img->max());
if (!$this->selected || ($this->selected->coef $img->coef/1.33)) {
    $this->selected $img;
    $n++;
    echo "<!-- SELECTED: "htmlentities($img->url).
              " X: $img->html_x Y: $img->html_y -->\n";
}

Pero los filtros anterior, aunque ya es bastante más sofisticado de lo que he visto no es suficiente ni mucho menos. Estos filtros dan muchos falsos positivos: imágenes de logos, publicidad insertada como imágenes (no como javascript), imágenes no relevantes (como índices de otras noticias, bastante habitual en medios digitales), etc.

El primer diseño lo que hacía era sólo permitir imágenes del mismo servidor. Como esto no era suficiente –muchos sitios incluyen imágenes de otros servidores de la misma red (como Yahoo de yimg.com), de Flickr u otros sitios de almacenamiento– tuve que agregar excepciones.


|| preg_match('/images\W|wp-content\W|upload\W|imgs\W|pics\W|pictures\W/',
              $this->url)
|| preg_match('/gfx\.|cdn\.|imgs*\.|\.img|media\.|cache\.|\.cache|static\.
              |\.ggpht.com|upload|files|blogspot|blogger|wordpress\.com|pic\./',
              $this->parsed_url['host'])

Aún así esto se convirtió en una pesadilla, cada día me encontraba con nuevas excepciones. Así que finalmente tuve que eliminar esas restricciones/excepciones y generalizar aún más el algoritmo: permitir imágenes de cualquier dominio, pero que no apareciesen en “páginas similares” al URL enlazado. La idea es analizar los enlaces hacia el mismo sitio, elegir un par de ellas, bajar el HTML y almacenarlos para comparar si cada una de las candidatas aparece en las páginas “alternativas”:


function check_in_other($str) {
    if (preg_match('/'.preg_quote($str,'/').'/'$this->other_html)) {
        echo "<!-- Skip: " htmlentities($str). "-->\n";
        return true;
    }
    return false;
}

Hasta aquí muy fácil, pero me encontré de nuevo con el problema de elegir qué páginas debería bajar y almacenar (en $this->other_html) para la comparación. La decisión no es sencilla porque de ella depende que el filtrado funcione. Así por ejemplo interesa –por ejemplo– bajar una noticia de la misma sección o categoría (el “template” será muy similar) y no bajar la página principal o el índice de categoría/sección que seguramente también incluyen la misma imagen relavente pero que harían que no fuese seleccionada.

Primero se aplican filtros básicos para ignorar enlaces que no aportan nada, cuyo URL es “demasiado similar” (los primeros 45 caracteres del URI son iguales) y también se tienen en cuenta sitios que usan “queries”:


if ( preg_match('/\.(gif|jpg|zip|png|jpeg|rar|mp3|mov|mpeg|mpg)($|\s)/i'$url) ||
       (!empty($this->parsed_url['query']) && 
          substr($this->parsed_url['query'], 020) == substr($parsed_match['query'], 020)) ||
       (empty($this->parsed_url['query']) && 
          substr($parsed_match['path'], 045) == substr($this->parsed_url['path'], 045)) ||
        preg_match('/feed|rss|atom|trackback/i'$match[1])) {
      continue;
}

Pero luego de eso me volví a encontrar el mismo problema que con las imágenes, ¿cómo seleccionar los dos “mejores”? Volví a recurrir al mismo truco de asignar pesos según unas pocas características, similitud en el URI entre el origen y las enlazadas:


// Assign weights
if (!empty($parsed_match['query'])) {
    if (empty($this->parsed_url['query'])) $weight *= 0.5;
    elseif ($this->parsed_url['path'] == $parsed_match['path']) {
        $weight *= 2;
        if (preg_replace('/(.+?)=.*/', '$1', $parsed_match['query']) ==
                preg_replace('/(.+?)=.*/', '$1', $this->parsed_url['query'])) {
                $weight *= 2;
        }
    }
}
if (preg_match('#/[\d/]{6,}#',  $parsed_match['path']) &&
        preg_match('#/[\d/]{6,}#',  $this->parsed_url['path']) ) {
        // Decrease weight if the path has numbers which resemble a date
        // of the type /aaaa/mm, /aaaamm or /aa/mm/dd
        if (preg_replace('#.*?/([\d/]{6,}).*#', "$1", $parsed_match['path']) ==
            preg_replace('#.*?/([\d/]{6,}).*#', "$1", $this->parsed_url['path'])) {
            $weight *= 0.1;
        }
} else {
    $equals = path_equals($parsed_match['path'], $this->parsed_url['path']);
    if ($equals > 0 && $equals < 5) {
        $weight *= 1.1 * $equals;
    }
}
$weight *= strlen($url);

De esta forma no se “ignoran” candidatas pero la probabilidad de elegir las dos mejores aumenta considerablemente. Esta técnica de asignar pesos es una sobre simplificación bastarda de conjuntos difusos –los matemáticos me matarían–, pero es muy efectiva en casos como este:

  • Entradas desconocidas y de formatos variables pero que siguen unos patrones básicos.
  • No se necesita precisión matemática, sino una buena aproximación.

Lo curioso de esto es que resultó como un flashback o una deformación profesional de algo similar que hice en 1991 para un proyecto del [viejo] aeropuerto de Palma de Mallorca. Yo estaba acabando mi PFC en el Dept. de Control de Procesos del  Centro Atómico Bariloche (tenía un título pomposo: “Resolución de problema de asignación dinámica –scheduling– de recursos usando satisfacción de restricciones”) cuando nos visitó un profesor de la UIB que vio lo que estaba haciendo y nos propuso intentar solucionar un problema del aeropuerto de Palma usando técnicas similares (exactamente éste es el origen de mi historia personal en Mallorca).

El problema era que había pocas plazas de aparcamiento de aviones –71 si lo recuerdo bien–, cada una con caracterísiticas propias: tamaños y modelos de aviones, necesidad de pushback, con rampa o jardinera, con boca de combustible o necesidad de camión, con boca de bomberos o no, etc. A su vez cada empresa tenía preferencias de las más diversas: no usar pushback en algunos modelos de avión, boca de combustible en la plaza si la estancia era corta, aparcamiento cercano a otros aviones de la misma compañía, etc. Además cada comandante podía solicitar cambios o requermientos especiales según las condiciones del vuelo.

El problema era muy diverso, luego de probar la resolución con diferentes métodos optamos por asignar pesos “relativos” (significando “poco importante”, “importante, “muy importante”, “…) a cada requisito, sumar los pesos de los requisitos que cumplia cada plaza, ordenarlas y luego mostrarlas ordenadas a los responsables de la asignación. Un chapuza matemática, pero funcionó muy bien durante los meses del verano de 1991 que probamos en el aeropuerto [*].

Esta misma idea de la chapucilla de “pesos” me sirvió para resolver este otro problema. También funciona bastante bien, mucho mejor de lo que esperaba inicialmente, se puede ver en las de portadas o en esta otra como ejemplo curioso de que funciona (la imágen no se ve en la primera pantalla, pero está🙂 ) [**].

La reflexión seria es que este tipo de problemas –aunque no tan simples como los que acabo de describir– serán cada vez más frecuentes, sobre todo con datos masivos y “entradas inciertas” (o “no controladas”). Es algo bastante habitual en Google –su PageRank ordenado y elegante al principio evolucionó en complejos sistemas de “pesos”– y en empresas que tratan con muchos datos y cuya “precisión” no es lo más importante. Es un tema muy interesante en informática, lo mencioné hace un año y dos días (en el #7), otra vez hace 8 meses,  y suelo insistir bastante que deberíamos estudiar y enseñar estos tipos problemas en las carreras informáticas.

Hay otra curiosidad relacionada con el tema del “tratamiento de formatos inciertos”. Hay muchos que ven al problema como casi intratable y pretenden que los humanos den mejor “formato”, y más “controlado”, a los datos que exponen en la red. Algo así como “hagamos que los humanos ordenen los que no podemos hacer automáticamente con los ordenadores”. A mí me parece una actitud o proyecto muy poco ambicioso, pero muchos –aunque no todos– usan un nombre pomposo para camuflarlo: “web semántica”.

[*] El sistema estaba formado por dos PCs, con DOS y programado en Turbo/Borland C++. Uno mostraba el mapa con el estado de cada plaza (y permitía editarlas), el otro era el “asignador” con la interfaz y la conexión con puerto serie a uno de los PDP-11 (que se usaban para registrar en tiempo real los eventos el mismo del que se obtenían los datos para las pantallas de anuncio) para obtener los datos de vuelos. Obtenía los estimados una día antes para preparar la lista de asignaciones “preferidas” del día siguiente, luego la modificaba en tiempo real con los datos que recibía del PDP-11 y/o de los responsables. El sistema al final no se usó más. A los pocos meses cambiaron los sistemas informáticos por otros montados sobre un mainframes Xerox –si mal no recuerdo– y al año siguiente se empezó la construcción del macro aeropuerto que tenemos ahora.

[**] Incluso pensé en programarlo en Python y ponerlo en marcha en Google AE para que de este tipo de servicios a los que lo necesiten. Pero luego pensé que es una chorrada, el código está disponible y es libre, el que lo necesite lo puede usar y/o adaptar mejor que yo.