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á.
