sábado, noviembre 22, 2008

Trie de palabras

Me gustaría saber el número de palabras distintas que he utilizado en el blog, para ello estoy pensando como podría obtener todo lo que he escrito, que es lo más complejo del problema. Una vez obtenido, contarlo es algo trivial.

Para contarlas, se puede montar una estructura de datos conocida como Trie, que en términos matemáticos, es un árbol multicamino, que suena a una cosa muy extraña.

Dicho de otra forma (y cogiendo lápiz y papel), imaginemos un Trie para las palabras 'casa, perro y cena'. Tendría un nodo raíz (sin letras) del que parten dos ramas, cada rama contiene un nodo con una letra, la C y la P. A su vez, de la rama que contiene la C, parten otras dos ramas, una con la letra A y otra con la letra E, etc.

Pero que pasa si tenemos un Trie con palabras como 'Casa y Casas'. Al nodo que contiene la letra, se le añade un atributo indicando que es final de palabra. De esa forma, el nodo que contienen la cuarta letra (la A) tiene ese atributo de fin de palabra, además de que tiene una rama para la letra S.

Contar las palabras distintas es tan fácil como recorrer el árbol y contar el número de marcas de fin de palabra. En la facultad llegue a implementar el algoritmo para las prácticas de una asignatura.

1 comentario:

  1. :) Me flipas y me haces gracia a partes iguales. O no. Depende del día xD.

    ResponderEliminar