Anatree

Un anatree ^{[ 1 ]} es una estructura de datos diseñada para resolver anagramas . Resolver un anagrama consiste en encontrar una palabra a partir de una lista de letras dada. Estos problemas se encuentran comúnmente en juegos de palabras como el Scrabble o en crucigramas de periódicos . El problema de la rueda de palabras también tiene la condición de que la letra central aparezca en todas las palabras formadas con el conjunto dado. Se pueden introducir otras condiciones con respecto a la frecuencia (número de apariciones) de cada una de las letras en la cadena de entrada dada. Estos problemas se clasifican como problemas de satisfacción de restricciones en la literatura de ciencias de la computación.

Un anatree se representa como un árbol dirigido que contiene un conjunto de palabras (W) codificadas como cadenas en algún alfabeto . Los vértices internos están etiquetados con alguna letra del alfabeto y las hojas contienen palabras. Las aristas están etiquetadas con enteros no negativos. Un anatree tiene la propiedad de que la suma de las etiquetas de las aristas desde la raíz hasta la hoja es la longitud de la palabra almacenada en la hoja. Si los vértices internos están etiquetados como${\displaystyle \alpha _{1}}$,${\displaystyle \alpha _{2}}$...${\displaystyle \alpha _{l}}$y las etiquetas de los bordes son${\displaystyle n_{1}}$,${\displaystyle n_{2}}$...${\displaystyle n_{l}}$, entonces el camino desde la raíz hasta la hoja a lo largo de estos vértices y aristas es una lista de palabras que contienen${\displaystyle n_{1}}$${\displaystyle \alpha _{1}}$s,${\displaystyle n_{2}}$${\displaystyle \alpha _{2}}$s y así sucesivamente. Los anatrees están pensados ​​para ser estructuras de datos de solo lectura con todas las palabras disponibles en el momento de su construcción.

Un anatree mixto es un anatree cuyos vértices internos también almacenan palabras. Un anatree mixto puede contener palabras de longitud variable, mientras que en un anatree regular todas las palabras tienen la misma longitud.

Se han propuesto diversas estructuras de datos para resolver anagramas en tiempo constante. Dos de las más utilizadas son el mapa alfabético y el mapa de frecuencias.

El mapa alfabético mantiene una tabla hash de todas las palabras posibles que pueden existir en el idioma (esto se denomina léxico ). Para una cadena de entrada dada, ordena las letras alfabéticamente. Esta cadena ordenada se asigna a una palabra en la tabla hash. Por lo tanto, encontrar el anagrama requiere ordenar las letras y buscar la palabra en la tabla hash. La ordenación se puede realizar en tiempo lineal con el algoritmo de ordenación por conteo y las búsquedas en la tabla hash se pueden realizar en tiempo constante. Por ejemplo, dada la palabra ANATREE, el mapa alfabético produciría una asignación de${\displaystyle \{AAEENRT->\{''anatree''\}\}}$.

Un mapa de frecuencias también almacena la lista de todas las palabras posibles en el léxico en una tabla hash. Para una cadena de entrada dada, el mapa de frecuencias mantiene las frecuencias (número de apariciones) de todas las letras y utiliza este recuento para realizar una búsqueda en la tabla hash. Se ha descubierto que el tiempo de ejecución en el peor de los casos es lineal con respecto al tamaño del léxico. Por ejemplo, dada la palabra ANATREE, el mapa alfabético produciría una asignación de${\displaystyle f(A)->2,f(E)->2,f(N)->1,f(R)->1,f(T)->1}$Las palabras que no aparecen en la cadena no se escriben en el mapa.

La construcción de un anatree comienza seleccionando una etiqueta para la raíz y dividiendo las palabras según dicha etiqueta. Este proceso se repite recursivamente para todas las etiquetas del árbol. La construcción de un anatree no es canónica para un conjunto de palabras dado; dependiendo de la etiqueta elegida para la raíz, el anatree variará en consecuencia. El rendimiento del anatree se ve muy afectado por la elección de las etiquetas.

A continuación se presentan algunas heurísticas para elegir etiquetas:

• Comience a etiquetar los vértices en orden alfabético desde la raíz. Este enfoque reduce la complejidad de la construcción.
• Comience a etiquetar los vértices en función de la frecuencia relativa. Se utiliza un enfoque probabilístico para asignar etiquetas a los vértices. Si${\displaystyle W_{n}^{\alpha }}$es el conjunto de palabras que contienen${\displaystyle n\alpha s}$, luego etiquetamos el vértice con${\displaystyle \alpha }$si maximiza la distancia esperada a la hoja. Este enfoque tiene los caracteres que aparecen con mayor frecuencia (como E) etiquetados en la raíz y los caracteres que aparecen con menor frecuencia etiquetados en las hojas. La siguiente ecuación se maximiza${\displaystyle D_{\alpha }=\sum _{n}n{\frac {|W_{n}^{\alpha }|}{|W|}}}$Este enfoque evita largas secuencias de aristas con etiqueta cero, ya que no aportan letras a las palabras generadas por el anatree.

Para encontrar una palabra en un anatree, comience en la raíz, dependiendo de la frecuencia de la etiqueta en la cadena de entrada dada, siga la arista que tenga esa frecuencia hasta la hoja. La hoja contiene la palabra requerida. Por ejemplo, considere el anatree de la figura, para encontrar la palabra${\displaystyle perro}$, la cadena dada puede ser${\displaystyle ogd}$. Empiece en la raíz y siga el borde que tiene${\displaystyle 1}$como la etiqueta. Seguimos esta etiqueta ya que la cadena de entrada dada tiene${\displaystyle 1}$${\displaystyle d}$Recorre este borde hasta encontrar la hoja. Eso te dará la palabra requerida.

Un léxico que almacena${\displaystyle w}$palabras (cada palabra puede ser${\displaystyle l}$caracteres de longitud) en un alfabeto${\displaystyle O}$tiene los siguientes requisitos de espacio.

El tiempo de ejecución en el peor de los casos de un anatree es${\displaystyle O(|w|(l+w|O|^{2}))}$

• Algoritmos geniales Parte 3 - Árboles de anagramas
• Anagrama en SourceForge