Humos y arbolitos

Python — Martes 20 de Noviembre de 2007, 17:32

O árboles y humitos: Este post es el par de mi lado del post Python más rápido que Java que escribió Humitos hace algunos días.

Arranquemos desde el principio... una mañana en la que entra Humitos al canal IRC de Python Argentina (#pyar en irc.freenode.net), y plantea el problema de cual es la mejor estructura de datos para armar un autocompletador de palabras. Esto es, a partir de un diccionario de palabras, que estructura las guarda mejor para que cuando uno ponga joye, el sistema sugiera joyel, joyelero, joyero y joyer.

Yo pensé en un árbol con una letra por nodo. Al toque, le sugirieron que usase un árbol Trie. Yo, que como no soy informático no conozco muchos nombres, fui a revisar qué era un árbol Trie (acá hay una explicación piola, acá una más formal).

La cuestión es que un árbol Trie era lo que yo pensaba que era: un árbol con una letra por nodo. Por ejemplo, para las palabras que usé antes:



Perfecto. Humitos tenía la tortura de tener que hacer esto en Java para la facultad, así que luego de llorar un rato puso manos a la obra. Iba como "reportando" en el canal de PyAr, e hizo un par de preguntas. Yo, viendo que era dificil discutir el tema desde lo abstracto, me tomé un rato e hice una implementación en Python y se la pasé.

Salió bastante derechita. Basicamente hice una clase Nodo que mantenía la letra, los ramas hijas, y un flag para indicar que hasta ahí llegaba la palabra. Parecía andar, tanto que Humitos termino implementando casi lo mismo en Java.

Al otro día, sin embargo, Humitos me dió dos malas noticias. La primera, era que el sistema este consumía mucha memoria... para el diccionario de más de 80 mil palabras, ¡¡el árbol armado ocupaba 180 MB!!. Como efecto secundario, tardaba mucho en armar la estructura en memoria (como 7 segundos); lo bueno era que la búsqueda en sí era super rápida.

Por un lado lo mejoré usando __slots__ (para que cada objeto Nodo ocupe menos memoria, algo sólo relevante cuando uno tiene tantos y tantos objetos). Por otro lado, encontré y solucioné una ineficiencia importante: tenía un nodo casi al pedo en cada hoja del árbol. Con estas dos correcciones, el sistema pasó a ocupar 55 MB en memoria, y tardaba 4 o 5 segundos en levantar.

Hasta acá, todo bien.

Pero luego, Humitos se dió cuenta de que tanto su programa como el mío tenían algunos problemas en aquellas palabras que simultaneamente eran completas y parte de otras. Siguiendo con el ejemplo anterior, tenemos allí dos casos de estos: joyel es palabra completa, pero a su vez parte de joyelero; lo mismo con joyer y joyero (por otro lado, joye, por ejemplo, es sólo parte de otras palabras, no una palabra completa por si misma).

El problema era tan sutil que se mostraba en algunos casos y en otros no, dependiendo del órden de las letras (y esto era provocado por la forma en que armábamos la estructura palabra por palabra).

Estuve como tres horas en la oficina peleándome con esto, pero luego tuve que hacer otras cosas (trabajar, bah) y no lo pude solucionar. El código se iba complicando y complicando, y no le encontraba la vuelta.

Esa noche era el concert de uno de los jardines de Moni, así que tuve como media hora de auto hasta allá. En esa media hora el cerebro trabajó tranquilo, y me di cuenta de tres cosas....

Por un lado debía dejar de usar clases para el Nodo, una estructura de diccionarios debía de servir si encontraba la manera de marcar el fin de las palabras. Por otro lado, en lugar de ir armando la estructura palabra por palabra, seguramente sería más fácil a nivel de código el armarla teniendo todas las palabras y recorriéndolas por "columnas" de letras.

Esas eran optimizaciones, pero también se me ocurrió un cambio más fundamental. En los finales de las palabras, en muchos casos seguramente la estructura pierde forma de árbol frondoso y como que le quedan "ramas peladas". En estos casos, en lugar de almacenar secuencias de nodos, es mucho más eficiente guardar el resto de la palabra y listo.

Para verlo mejor, les redibujo el ejemplo anterior, pero bajo este concepto:



Como es una especie de Trie degenerado, excusándome bajo una incapacidad total a la hora de los nombres, y considerando que la versión anterior me tenía un poco frustrado, lo terminé llamando Fucked Trie.

Llegué al concert bastante antes que los padres, pasaron 40, o 45 minutos antes de que se ocupara el salón. Ese tiempo lo pasé codeando tirado en un rincón, e implementé el 95% de lo que sería la solución final. Le terminé de dar un par de retoques el lunes o el martes pasado, en Brasil, donde le corrí el profiler y optimizé un par de detalles.

El producto final tarda menos de un segundo en cargar, ocupa sólo 18 MB de memoria, y hace las busquedas en 60 micro segundos, centenares de veces más rápido que antes... ¡una preciosura! El código, junto con el diccionario de palabras, acá.
Usuarios de Software Libre de Argentina

comentarios

  1. Siempre que hago un comentario en tu blog, se me complica en la multiplicación. Agrr!

    La idea de guardar el final de la palabra si esa rama es "pelada" es genial. Se ahorran una cantidad de nodos en el árbol.

    El problema de esto, que de hecho no les dije, es que en el árbol se deben poder agregar y quitar palabras. Para lo cual de esta forma se complicaría un poco me parece. Al menos en Java ¿no? :)

    Como es un sistema de autocompletado la idea del ejercicio es que vaya cargando las palabras que uno va escribiendo en el documento. Además de las palabras del diccionario.

    Por otro lado, al mostrar las sugerencias se deben mostrar primero priorizando la cantidad de ocurrencias en el texto que uno halla escrito y luego por órden alfabético.

    Esto es realmente lo que dice el ejercicio de mi facultad. ¡Saludos!

    Escrito por humitos — 20 Nov 2007, 17:59

  2. normalmente lo que se hace en estos casos para resolver el tema de donde termina o no una palabra es meter un caracter "fin de palabra" al final de cada palabra. no entendi del texto como lo resolviste vos.

    Escrito por lucio — 20 Nov 2007, 19:07

  3. @humitos: en realidad el agregar palabras no es taaan complicado. Es recorrer el árbol según el prefijo de la palabra (¿quién dijo "iterar sobre la cadena"?) hasta llegar a una letra que no está o una hoja del árbol. En ambos casos se completa la palabra como siempre, opcionalmente quitando una letra del fin de la palabra y agregando el nodo correspondiente para mantener los invariantes.

    El borrar puede ser que se complique un poco dada las verificaciones que hay que hacer en la estructura. Pero ésto no quiere decir que no sea posible y/o rápido.

    El completar palabras de una lista dinámica sólo implica agregar y sacar palabras del diccionario. Como estás haciendo autocompletación tenés acceso al texto original y cuándo terminaste de escribir una palabra y cuándo no. Cuando no, mostrás la lista, cuando sí agregás la palabra al diccionario si no estaba y si ya estaba aumentás en 1 el índice de "coincidencia" en una estructura aparte.

    Una vez hecho esto, el autocompletar es tan simple como una búsqueda en el diccionario que devuelva todas las posibles "completaciones" (como el diccionario va a tener la lista de palabras escritas por uno, cumple con lo que pediste) y luego hacés un sort con una función de comparación que utilice la estructura de "coincidencia" que mencioné antes.

    Para que el ejercicio esté completo sólo tenés que considerar el caso que se borre una palabra (para eliminarla de tu diccionario y/o de la estructura de coincidencia). Pero creo que eso sería un punto extra para hacer el programa DEMASIADO correcto :P

    Escrito por Matías — 20 Nov 2007, 19:46

  4. Humitos: Para lo que yo quiero utilizar esto luego (más que autocompletador, sugerencia de búsqueda en la wikipedia offline), el estado actual alcanza y sobra...

    Lucio: La estructura son diccionarios en árbol, la clave es siempre una letra, y el valor es un string: una letra, varias o una cadena vacia. La cadena vacía se usa justamente para indicar el fin de palabra.

    Matías: No es tan fácil meter más palabras en la estructura, ya que no sólo es agregar, sino jugar con las anteriores (fijate, para el ejemplo del post, si tuvieras que agregar la palabra "joyeleria").

    Saludos a todos.

    Escrito por Facundo Batista — 21 Nov 2007, 04:23

  5. Mirá, parece que ésto tiene nombre:

    http://es.wikipedia.org/wiki/Dendrograma

    ¿No es lo mismo?

    Escrito por humitos — 03 Abr 2013, 16:30

  6. Hola Humitos!

    Me parece que es muy parecido, pero se termina usando para otra cosa. Sí, es un árbol que representa una estructura jerárquica, pero es más usado para mostrar clustering entre los datos...

    Abrazo!

    Escrito por Facundo Batista — 04 Abr 2013, 09:29

  7. ¿Lo tenés a éste?

    http://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton

    Guarda que 6 años después no le haya encontrado la mejor solución... :D

    Escrito por humitos — 29 Nov 2013, 18:41

  8. No lo tenía! Es parecido. Eso de compartir nodos no me convence del todo :p

    Uh, mirá "a standard DAFSA can tell you if a word exists within it, but it cannot point you to auxiliary information about that word, whereas a trie can."

    BTW, ¿viste que al código este lo emprolijé, agregué tests y lo puse como proyecto separado? Acá:

    https://launchpad.net/ftrie

    Saludos!!

    Escrito por Facundo Batista — 30 Nov 2013, 20:55


Añadir comentario

authimage






Powered by LifeType