Incremental construction of minimal acyclic finite-state automata
Incremental construction of minimal acyclic finite-state automata
复制标题
DOI：
10.1162/089120100561601
复制
发表时间：
2000-03-01
影响因子：
9.3
通讯作者：
Watson, RE
中科院分区：
文献类型：
--
作者：
Daciuk, J;Mihov, S;Watson, RE
在本文中，我们描述了一种新的方法，用于从一组字符串构造最小的，确定的，非循环的有限状态自动机。传统的方法包括两个阶段：第一阶段构造一个trie树，第二阶段最小化trie树，而我们的方法是通过一个接一个地添加新的字符串并在运行中最小化所得到的自动机，从而在一个阶段中构造一个最小自动机。我们提出了一个通用的算法，以及专业化，依赖于他的输入字符串的字典序。我们的方法是快速的，显着降低内存需求相比，其他方法。
In this paper, we describe a new method for constructing minimal, deterministic, acyclic finite-state automata from a set of strings. Traditional methods consist of two phases: the first to construct a trie, the second one to minimize it. Our approach is to construct a minimal automaton in a single phase by adding new strings one by one and minimizing the resulting automaton on-the-fly. We present a general algorithm as well as a specialization that relies upon the lexicographical ordering oft he input strings. Our method is fast and significantly lowers memory requirements in comparison to other methods.