Un GADDAG es una estructura de datos presentada por Steven Gordon en 1994, para usar en la generación de movimientos para Scrabble y otros juegos de generación de palabras donde dichos movimientos requieren palabras que "enganchen" palabras existentes. A menudo contrasta con los algoritmos de generación de movimientos que utilizan un gráfico de palabras acíclicas dirigidas (DAWG) como el que utiliza Maven . Por lo general, es el doble de rápido que los algoritmos DAWG tradicionales, pero ocupa aproximadamente 5 veces más espacio para regular los diccionarios de Scrabble. [1]
Un GADDAG es una especialización de un Trie , que contiene estados y ramas a otros GADDAG. Se distingue por su almacenamiento de cada prefijo invertido de cada palabra en un diccionario. Esto significa que cada palabra tiene tantas representaciones como letras; dado que la palabra promedio en la mayoría de los diccionarios de regulación de Scrabble tiene 5 letras, esto hace que el GADDAG sea aproximadamente 5 veces más grande que un DAWG simple.
Para cualquier palabra en un diccionario que esté formada por un prefijo x no vacío y un sufijo y, un GADDAG contiene una ruta directa y determinista para cualquier cadena REV ( x )+ y , donde + es un operador de concatenación.
Los algoritmos basados en DAWG aprovechan la segunda y la tercera restricción: el DAWG se construye alrededor del diccionario y se recorre usando mosaicos en el bastidor. Sin embargo, falla en abordar la primera restricción: suponiendo que uno quiere 'enganchar' la letra P en HARPY , y el tablero tiene 2 espacios antes de la P, uno debe buscar en el diccionario todas las palabras que contienen letras del estante donde el tercera letra es P. Esto es ineficiente cuando se busca a través de DAWG, ya que muchas búsquedas a través de trie serán infructuosas.
Esto se aborda mediante el almacenamiento de prefijos de GADDAG: al atravesar la rama P de un GADDAG, uno ve todas las palabras que tienen una P en algún lugar de su composición y puede "viajar hacia arriba" por el prefijo para formar la palabra con mosaicos en el estante. Para usar el ejemplo de la sección § Definición , al buscar P aparece " pxe+lain ". Las letras entre la P y el + se pueden colocar encima de la P en el tablero, y el resto debajo (si el espacio en el tablero lo permite).