De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Las cadenas "tap", "tap", "top" y "tops" se almacenan en un trie (izquierda) y un DAFSA (derecha), EOW significa End-of-word.

En informática , un autómata de estado finito acíclico determinista ( DAFSA ), [1] también llamado gráfico de palabras acíclicas dirigidas ( DAWG ; aunque ese nombre también se refiere a una estructura de datos relacionada que funciona como un índice de sufijo [2] ) es un dato estructura que representa un conjunto de cadenas y permite una operación de consulta que prueba si una determinada cadena pertenece al conjunto en un tiempo proporcional a su longitud. Existen algoritmos para construir y mantener tales autómatas, [1] manteniéndolos al mínimo .

Un DAFSA es un caso especial de un reconocedor de estado finito que toma la forma de un gráfico acíclico dirigido con un único vértice de origen (un vértice sin bordes entrantes), en el que cada borde del gráfico está etiquetado por una letra o símbolo, y en el que cada vértice tiene como máximo un borde saliente para cada letra o símbolo posible. Las cadenas representadas por DAFSA están formadas por los símbolos en las rutas en el gráfico desde el vértice de origen hasta cualquier vértice de sumidero (un vértice sin bordes salientes). De hecho, un autómata determinista de estado finito es acíclico si y solo si reconoce un conjunto finito de cadenas . [1]

Comparación con intentos [ editar ]

Al permitir que los mismos vértices sean alcanzados por múltiples rutas, un DAFSA puede usar significativamente menos vértices que la estructura de datos trie fuertemente relacionada . Considere, por ejemplo, las cuatro palabras en inglés "tap", "taps", "top" y "tops". Un trie para esas cuatro palabras tendría 12 vértices, uno para cada una de las cadenas formadas como prefijo de una de estas palabras, o para una de las palabras seguida del marcador de fin de cadena. Sin embargo, un DAFSA puede representar estas mismas cuatro palabras usando solo seis vértices v i para 0 ≤  i  ≤ 5, y los siguientes bordes: un borde de v 0 a v 1 etiquetado como "t",dos aristas de v 1 a v 2etiquetado "a" y "o", un borde de v 2 a v 3 etiquetado "p", un borde v 3 a v 4 etiquetado "s", y los bordes de v 3 y v 4 a v 5 etiquetados con el final- marcador de cuerda. Existe una compensación entre la memoria y la funcionalidad, porque un DAFSA estándar puede decirle si existe una palabra dentro de él, pero no puede indicarle información auxiliar sobre esa palabra, mientras que un trie sí puede.

La principal diferencia entre DAFSA y trie es la eliminación de la redundancia de sufijos e infijos en el almacenamiento de cadenas. El prefijo trie elimina la redundancia ya que todos los prefijos comunes son compartidos entre las cuerdas, como entre los médicos y Doctorado del médico es compartida prefijo. En un DAFSA, los sufijos comunes también se comparten, para palabras que tienen el mismo conjunto de posibles sufijos entre sí. Para los conjuntos de diccionarios de palabras comunes en inglés, esto se traduce en una importante reducción del uso de memoria.

Debido a que se puede llegar a los nodos terminales de un DAFSA por múltiples rutas, una DAFSA no puede almacenar directamente información auxiliar relacionada con cada ruta, por ejemplo, la frecuencia de una palabra en el idioma inglés. Sin embargo, si para cada nodo almacenamos el número de rutas únicas a través de ese punto en la estructura, podemos usarlo para recuperar el índice de una palabra, o una palabra dado su índice. [3] La información auxiliar se puede almacenar en una matriz.

Referencias [ editar ]

  1. ↑ a b c Jan Daciuk, Stoyan Mihov, Bruce Watson y Richard Watson (2000). Construcción incremental de autómatas de estado finito acíclicos mínimos. Lingüística computacional 26 (1): 3-16.
  2. ^  Este artículo incorpora material de dominio público  del documento NIST :  Black, Paul E. "gráfico de palabras acíclicas dirigidas" . Diccionario de algoritmos y estructuras de datos .
  3. ↑ Kowaltowski, T .; CL Lucchesi (1993). "Aplicaciones de autómatas finitos que representan grandes vocabularios". Práctica y experiencia en software . 1993 : 15-30. CiteSeerX 10.1.1.56.5272 . 
  • Blumer, A .; Blumer, J .; Haussler, D .; Ehrenfeucht, A .; Chen, MT; Seiferas, J. (1985), "El autómata más pequeño que reconoce las subpalabras de un texto", Informática teórica , 40 : 31-55, doi : 10.1016 / 0304-3975 (85) 90157-4
  • Appel, Andrew; Jacobsen, Guy (1988), "El programa de Scrabble más rápido del mundo" (PDF) , Comunicaciones del ACM , 31 (5): 572–578, doi : 10.1145 / 42411.42420. Una de las primeras menciones de la estructura de datos.
  • Jansen, Cees JA; Boekee, Dick E. (1990), "Sobre la importancia del gráfico de palabras acíclicas dirigidas en criptología", Avances en criptología - AUSCRYPT '90 , Lecture Notes in Computer Science , 453 , Springer-Verlag , págs. 318-326, doi : 10.1007 / BFb0030372 , ISBN 3-540-53000-2.
  • Epifanio, Chiara; Mignosi, Filippo; Lo haré, Jeffrey; Venturini, Ilaria (2004), "Gráficos Sturmian y una conjetura de Moser", en Calude, Cristian S .; Calude, Elena; Dineen, Michael J. (eds.), Desarrollos en la teoría del lenguaje. Actas, octava conferencia internacional (DLT 2004), Auckland, Nueva Zelanda, diciembre de 2004 , Lecture Notes in Computer Science, 3340 , Springer-Verlag , págs. 175–187, ISBN 3-540-24014-4, Zbl  1117.68454
  • Tresoldi, Tiago (2020), "DAFSA: a Python library for Deterministic Acyclic Finite State Automata", Journal of Open Source Software , 5 (46): 1986, doi : 10.21105 / joss.01986Una implementación de Python de código abierto .

Enlaces externos [ editar ]

  • http://pages.pathcom.com/~vadco/dawg.html - JohnPaul Adamovsky enseña cómo construir un DAFSA usando una matriz de números enteros.
  • http://pages.pathcom.com/~vadco/cwg.html - JohnPaul Adamovsky enseña cómo construir una función hash DAFSA utilizando una codificación novedosa con múltiples matrices de enteros. Esta codificación se llama Caroline Word Graph (CWG).