Prague Stringology Conference 2017
Tobias Runge, Ina Schaefer, Loek Cleophas and Bruce W. Watson
Many-MADFAct: Concurrently Constructing MADFAs
| Abstract: |
| Minimal acyclic deterministic finite automata (MADFAs) are used to represent dictionaries, i.e., finite sets of finite words, in, e.g., spell checkers and network security applications. Given the size of such dictionaries, which may contain millions of words, their efficient construction is a critical issue. Watson (2010) published a classification of such algorithms in an algorithm taxonomy with correctness arguments. We report on a new algorithm which constructs MADFAs in parallel---each for a keyword set from a partition of the original keyword set---and afterwards merges and minimizes the resulting automata into a single MADFA; on our experience implementing the algorithms in a Java-based toolkit; and on empirical performance results obtained. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |