Búsqueda por prefijos tolerante a errores

Hace un tiempo les hablé de un árbol que hice para sacar prefijos de palabras.

En el laburo estoy estudiando la forma de hacer un autocompletador. Entonces, luego de leer cosas por ahí, decidí probar ese árbol que ya tenía hecho.

Nunca le había tirado tantos datos, pero la verdad es que salió andando de perlas.

Por otro lado, tenía un detalle que necesitaba solucionar: yo quería que la búsqueda de palabras soportara errores en la escritura. O sea, que si uno buscara "maise", encontrara "maizena".

Encontré un paper bastante loco, Efficient Error-tolerant Query Autocompletion, pero que mostraba la forma de soportar errores al buscar palabras completas, no prefijos. Igual, apliqué ideas de ahí, y en un par de días de laburo conseguí lo que quería. Pero, al cargar el millón y medio de registros que tengo que cargar, ¡explotaba por memoria!

Luego de algunas optimizaciones obvias, se me ocurrió lo de deduplicar los subtrees internos. ¿Qué es deduplicar? Deduplicar es la acción por la cual si tengo un objeto A, y luego tengo otro B, que resulta ser igual a A, puedo usar el A directamente en ambos casos, descartando B (libera memoria), y listo.

Deduplicar diccionarios no es un asunto trivial. Tiré el asunto en la lista de PyAr, y en pocas horas logré que todo funcione correctamente. Ahora no sólo no explota, sino que ocupa bastante poca memoria!

Memory usage after loading the tree: rss: +586 MB  vms: +586 MB
Time to load the tree: 327190.99 msec
<WordTree at 3068071276 [tau=1]: 1478347 words 30015540 (2201293) nodes (unique)>

Millón y medio de palabras, 30 millones de nodos (de los cuales 2.2 millones son únicos), ocupando 590 MB de memoria. Nada mal, ¿no? Que tarde 5.5 minutos en armar toda la estructura es un problema, la semana que viene voy a mirar eso bien.

Todo el código, acá.

Comentarios Imprimir

Mis lugares favoritos en el mapa

Hace algunos años me empezó a pasar que leía (o me pasaban) recomendaciones de lugares para comer, tomar algo, jugar al pool, etc, y luego cuando estaba en la calle, no las recordaba y terminaba yendo a cualquier lado al azar.

Se me ocurrió empezar a registrar los lugares en un mapa. La solución que usé fue basada en Google Maps: en la interfaz web creé una capa mía, en la cual empecé a cargar todos esos lugares. Luego, en el teléfono, iba a Google Maps, le decía que me mostrara esa capa, y ahí tenía el mapa con muchas estrellitas (cada lugar que había cargado) y podía ver qué tenía cerca, o para donde iba, etc.

Con el tiempo, se empezó a complicar.

En un momento, Google decidió que la versión del teléfono de Maps no iba a mostrar más "custom layers" (o sea, las capas que creabas vos). En otras palabras, ¡no podía ver más mis datos! Esto lo solucioné instalando una versión vieja de Google Maps en el teléfono (lo cual no es sencillo de hacer, pero funcionaba). Más adelante, Google empezó a complicar el uso de las capas en la versión web también. Y hace algunos meses, dejó de servir esa información, con lo cual aunque en el teléfono tuviera una versión que pedía esas capas al servidor, el servidor no las contestaba.

Esta foto es vieja, pero me encanta

En paralelo, hace un par de años largos que quiero empezar a irme en lo posible de los servicios de Google, y en función de eso en los últimos meses empecé a usar los mapas de OpenStreetMap ("OSM"), por recomendaciones de Nico, Humitos y Marcos Dione. Desde mitad del año pasado también lo puse en el teléfono, mediante la gran aplicación OsmAnd primero, y desde hace un par de semanas con MAPS.ME (que es bastante más rápida al mostrar los datos, y creo que es mejor decidiendo dónde mostrarte los nombres de las calles, lo cual es importante).

La gran ventaja de OsmAnd y MAPS.ME es que usan los mapas de OpenStreetMap (que son mejores en su calidad que los de Google Maps, y además son abiertos y colaborativos), y que además lo usan de forma offline. O sea, te bajás los mapas que te interesan (por ejemplo, el de Argentina) cuando tenés una buena conexión de internet y luego el mapa está en tu teléfono, con lo cual no necesitás internet cuando estás en la calle para consultar estos datos.

Pero, aunque estaba contento con la solución de "mapas" en su forma genérica, me faltaba esto de "anotar mis lugares". Hasta que Humitos me recomendó umap, donde podés justamente crear capas de lugares arriba de los mapas de OpenStreetMap (hay una gran cantidad de sitios que utilizan los datos de OSM y dan servicios arriba de ellos, ejemplos que me pasó Humitos: su propio "puntos de interes", otro con fotos de ciudades, y uno donde la gente registra árboles frutales).

En ese sitio, entonces, creé mi mapa de lugares para ir de parranda (no volví a armarlo de cero, sino que importé lo que exporté previamente de google maps). Para llevar estos datos a mi teléfono, exporté un KML, me lo mandé por mail, y en el teléfono le dije que lo abra con el MAPS.ME.

Y listo, :)

Comentarios Imprimir

Hay días en el laburo...

Hay días en el laburo donde tenés que hacer un trabajo, lo planeás, te juntás con gente, se decide que cosas se van a hacer, se separa todo en tres o cuatro partes, hacés cada una (con tests y todo), todo bien, te hacen los review, entra en trunk, va a producción, todo muy lindo, mirás las métricas, suben y bajan como corresponde, y sos feliz.

Hay otros días en el laburo, donde empezás a ver algo y decís "esto no puede ser", empezás rastrear por qué está ese número ahí y te das cuenta que los logs tienen un problema, entonces lo querés contrastar con las métricas, y te das cuentas que en las métricas falta data, decidís cruzarlo con otro dato y te das cuenta que todavía no están sincronizados los archivos donde eso está, lo tenés que pedir y te tardan tres o cuatro horas en dártelo, y después cuando lo podés cruzar te das cuenta que deberías haber estado registrando algún otro número más, pero que no todo está perdido porque lo podés sacar de forma indirecta, hacés un script para parsear un quintillón de registros, te da un resultado más o menos coherente, pero todavía tenés que resolver como puede ser que el problema realmente esté sucediendo, mirás el código, te das cuenta que esa función está siendo llamada desde siete lados de los cuales solamente te acordabas tres, y de esos siete lados hay dos que no tenes datos de cómo están llamados...

Está todo roto

En fin, la mayoría de las veces termina todo con un final feliz, pero realmente estás uno, dos o tres días rascándote grupalmente la cabeza con tus compañeros de trabajo hasta que se resuelve el acertijo.

Comentarios Imprimir