TWO ALGORITHMS FOR INCREMENTAL CONSTRUCTION OF DIRECTED ACYCLIC WORD GRAPHS
Kyriakos Sgarbas, Nikos Fakotakis, George K. Kokkinakis · International Journal of Artificial Intelligence Tools · 1995
In this paper we present two algorithms for building lexicons in Directed Acyclic Word-Graphs (DAWGs). The two algorithms, one for deterministic and the other for non-deterministic DAWGs, can be used instead of the traditional subset construction method. Although the proposed algorithms do not produce the optimal DAWG (i.e., the one with the minimum number of states), they are simple, fast and able to build the DAWG incrementally, as new words are added to the lexicon. Thus, building large lexicons in a DAWG structure becomes an easy task, even for a modest computer.