Optimal insertion in deterministic DAWGs

✍ Scribed by Kyriakos N. Sgarbas; Nikos D. Fakotakis; George K. Kokkinakis

• Book ID: 104325594
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 426 KB
• Volume: 301
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00571-6

✦ Synopsis

In this paper, we present an on-line algorithm for adding words (strings) in deterministic directed acyclic word graphs (DAWGs) i.e. acyclic deterministic ÿnite-state automata (DFAs). The proposed algorithm performs optimal insertion, meaning that if applied to a minimal DAWG, the DAWG after the insertion will also be minimal. The time required to add a new word is O(n) with respect to the size of the DAWG. Repetitive application of the proposed insertion algorithm can be used to construct minimal deterministic DAWGs incrementally, although the algorithm is not time-e cient for building minimal DAWGs from a set of words: to build a DAWG of n words this way, O(n 2 ) time is required. However, the algorithm is quite useful in cases where existing minimal DAWGs have to be updated rapidly (e.g. speller dictionaries), since each word insertion traverses only a limited portion of the graph and no additional minimization operation is required. This makes the process very e cient to be used on-line. This paper provides a proof of correctness for the algorithm, a calculation of its time-complexity and experimental results.