Premium
Fast construction of space‐optimized recursive automaton
Author(s) -
Ristov Strahil,
Korenčić Damir
Publication year - 2015
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.2261
Subject(s) - computer science , deterministic automaton , deterministic finite automaton , automaton , dfa minimization , finite state machine , trie , theoretical computer science , timed automaton , büchi automaton , two way deterministic finite automaton , nondeterministic finite automaton , algorithm , state space , state (computer science) , software , automata theory , data structure , mathematics , programming language , statistics
Summary Finite‐state automata are important components in information retrieval and natural language processing software. A recursive automaton is the most compact representation of the acyclic deterministic finite‐state automata. It is based on merging not only the equivalent states but also the identical substructures in an automaton. The LZ trie variant is the state‐of‐the‐art in automata compression regarding space, but the time needed for its construction was, until now, quadratic, which has made it impractical for large inputs. In this paper, we present the first algorithm for LZ trie construction that runs in effectively linear time thereby making it an attractive choice for finite‐state automata implementation. We achieve this goal by adding a new functionality to the enhanced suffix array data structure. We present two variants of the construction procedure – an optimal method regarding the final size and a method that sacrifices some compression for low intermediate memory usage. We have made the implementation of our algorithms available in an open source software package LzLex .Copyright © 2014 John Wiley & Sons, Ltd.