Autômato finito determinístico acíclico

Em ciência da computação, um autômato finito determinístico acíclico (AFDA),^[1] também chamado de grafo orientado acíclico de palavras (GOAP; apesar desse nome também se referir a uma estrutura de dados relacionada que funciona como um índice de sufixo^[2]) é uma estrutura de dados que representa um conjunto de cadeias de caracteres, e permite uma operação de consulta que testa se uma dada cadeia pertence ao conjunto em tempo proporcional ao seu comprimento. Algoritmos existem para criar e manter tais autômatos, enquanto os mantêm mínimo.

As seqüências de caracteres "tap", "taps", "top", e "tops" armazenadas na Trie (esquerda) e um AFDA (direita), o símbolo `EOW` representa o fim da palavra.

Um AFDA é um caso especial de uma máquina de estados finitos que toma a forma de um grafo acíclico orientado com um único vértice fonte (um vértice que nenhuma aresta o têm como destino), em que cada aresta do grafo é rotulada por uma letra ou um símbolo, e em que cada vértice tem no máximo uma aresta que o têm como origem por símbolo. As sequências de caracteres representados pelo AFDA são formada pelos símbolos nos caminhos do grafo a partir do vértice fonte para o vértice sumidouro (ou poço) (um vértice que nenhuma aresta o têm como origem). De fato, um autômato finito determinístico é acíclico se, e somente se reconhece um conjunto finito de cadeias de caracteres.^[1]

Comparação com Tries editar

Por permitir que os mesmos vértices possam ser alcançados por vários caminhos, um AFDA pode usar um número significativamente menor de vértices que uma trie. Considere, por exemplo, as quatro palavras em inglês "tap", "taps", "top", e "tops". Uma trie para essas quatro palavras teria 11 vértices, um para cada uma das cadeias formadas como um prefixo de uma dessas palavras, ou para uma das palavras seguidas pelo símbolo de fim da palavra. No entanto, um AFDA pode representar estas mesmas quatro palavras usando apenas seis vértices v_i para 0 ≤ i ≤ 5, e as seguintes arestas: uma aresta de v₀ para v₁ rotulada de "t", duas arestas de v₁ a v₂ rotuladas de "a" e "s", uma aresta de v₂ para v₃ rotulada de "p", uma aresta v₃ para v₄ rotulada de "s", e as arestas que saem de v₃ e v₄ e chegam a v₅ rotuladas com o símbolo de fim da palavra. Existe uma escolha entre memória ou funcionalidade, porque um AFDA padrão pode dizer se uma palavra existe dentro dele, mas não pode fornecer informações auxiliares sobre essa palavra, enquanto que uma trie pode.

A principal diferença entre um AFDA e uma trie é a eliminação da redundância de sufixos e infixos no armazenamento de cadeias de caracteres. A trie elimina a redundância de prefixos, pois todos os prefixos comuns são compartilhados entre cadeias de caracteres, como por exemplo, entre cachos e cachorro o prefixo cacho é compartilhado. Em um AFDA sufixos comuns também são compartilhados, para palavras que tem o mesmo conjunto de possíveis sufixos entre si. Para um dicionário da língua portuguesa, isso resulta em uma grande redução de memória.

Porque os nós terminais de um AFDA podem ser alcançados por vários caminhos, um AFDA não tem a capacidade de armazenar informações auxiliares relativas a cada caminho, ex. a frequência de uma palavra na língua portuguesa. No entanto, se em cada nó fosse armazenado o número de caminhos únicos através daquele ponto na estrutura, poderíamos usá-lo para obter o índice de uma palavra, ou uma palavra dado o seu índice.^[3] As informações auxiliares então podem ser armazenados em um array.

Referências editar

↑ ^a ^b Jan Daciuk, Stoyan Mihov, Bruce Watson and Richard Watson (2000).
↑ Black, Paul E. "directed acyclic word graph".
↑ Kowaltowski, T.; CL Lucchesi (1993). «Applications of finite automata representing large vocabularies». Software-Practice and Experience. 1993: 15–30. Predefinição:Citeseerx

Blumer, A.; Blumer, J.; Haussler, D.; Ehrenfeucht, A.; Chen, M.T.; Seiferas, J. (1985), «The smallest automation recognizing the subwords of a text», Theoretical computer science, 40: 31–55, doi:10.1016/0304-3975(85)90157-4
Appel, Andrew; Jacobsen, Guy (1988), «The World's Fastest Scrabble Program» (PDF), Communications of the ACM, doi:10.1145/42411.42420 . One of the early mentions of the data structure.
Jansen, Cees J. A.; Boekee, Dick E. (1990), «On the significance of the directed acyclic word graph in cryptology», Advances in Cryptology — AUSCRYPT '90, ISBN 3-540-53000-2, Lecture Notes in Computer Science, 453, Springer-Verlag, pp. 318–326, doi:10.1007/BFb0030372 .
Epifanio, Chiara; Mignosi, Filippo; Shallit, Jeffrey; Venturini, Ilaria (2004), «Sturmian graphs and a conjecture of Moser», in: Calude, Cristian S.; Calude, Elena; Dineen, Michael J., Developments in language theory. Proceedings, 8th international conference (DLT 2004), Auckland, New Zealand, December 2004, ISBN 3-540-24014-4, Lecture Notes in Computer Science, 3340, Springer-Verlag, pp. 175–187, Zbl 1117.68454

Ligações externas editar

http://pages.pathcom.com/~vadco/dawg.html (em inglês) - exemplo da construção de um AFDA usando um array de inteiros.
http://pages.pathcom.com/~vadco/cwg.html (em inglês)

[daciuk-1] Jan Daciuk, Stoyan Mihov, Bruce Watson and Richard Watson (2000).

[2] Black, Paul E. "directed acyclic word graph".

[kowaltowski1993-3] Kowaltowski, T.; CL Lucchesi (1993). «Applications of finite automata representing large vocabularies». Software-Practice and Experience. 1993: 15–30. Predefinição:Citeseerx

[1]

[2]

[3]