An efficient representation for implementing finite state machines based on the double-array
An efficient representation for implementing finite state machines based on the double-array
复制标题
基于双数组实现有限状态机的有效表示
DOI：
10.1016/s0020-0255(00)00061-x
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
J. Aoe
中科院分区：
文献类型：
--
作者：
Shoji Mizobuchi;Toru Sumitomo;M. Fuketa;J. Aoe
本文描述了扩展的双数组结构，以便将其应用于通用有限状态机。双数组是一种集时间效率和空间效率于一体的高效数据结构。然而，其应用范围仅限于使用带标记边的有向树作为数据结构的领域。这里，对双数组结构进行了扩展，使其可以表示图结构，并且可以动态操作。所提出的方法已经通过理论观察进行了评估，并且其空间效率在我们的实验中得到了验证。
This paper describes the double-array structure that is extended in order to apply it to general finite state machines. The double-array is an efficient data structure which combines time efficiency and space efficiency. However, the range of its application has been limited in the areas where a directed tree with labeled edges is used as the data structure. Here, the double-array structure is extended so that it can represent the graph structure and, furthermore, be operated dynamically. The presented method has been evaluated by theoretical observations, and its space efficiency is verified in our experiment.