Improving Automata Efficiency by Stretching and Jamming
Improving Automata Efficiency by Stretching and Jamming
复制标题
通过拉伸和干扰提高自动机效率
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
B. Watson
中科院分区：
文献类型：
--
作者：
Noud de Beijer;L. Cleophas;D. Kourie;B. Watson
近年来，有限自动机应用中通常使用的字母表大小范围有了相当大的增长，现在的范围从DNA字母表（其符号可使用2位表示）到Unicode字母表（其符号表示可能需要高达32位）。由于自动机传统上使用8位的符号编码，不同的字母表和符号大小带来了一个问题，即它们是否可以用来减少自动机转换表的内存使用或减少字符串处理时间。在文献[3]中，拉伸和干扰被引入作为有限自动机上的变换。给定一个有限自动机，我们可以通过将每个单个转换分裂为两个或更多个连续转换来扩展它，从而引入额外的中间状态。干扰是逆变换，其中两个或多个连续的转换被加入到单个转换中，从而去除冗余的中间状态。在本文中，我们只考虑一种限制形式的拉伸和堵塞，其中一个固定的因素是用来拉伸（堵塞）过渡（过渡路径）在一个给定的自动机，并在过渡符号被假定为编码为位串。我们考虑了[3]中提出的算法的改进版本，用于这种特殊形式的拉伸和干扰。这些算法在c++中实现，并用于对转换进行基准测试。这个基准测试的结果表明，在某些条件下，拉伸可能有利于内存的使用，而不利于处理时间，而干扰可能有利于处理时间，而不利于内存的使用。后者似乎在DNA处理的情况下可能有用，而前者可能用于Unicode处理。关键词：有限自动机;转换;分裂转换;连接转换;转换表大小;字符串处理时间
In recent years, the range of alphabet sizes typically used in applications of finite automata has grown considerably, now ranging from DNA alphabets—whose symbols are representable using 2 bits—to Unicode alphabets—whose symbol representation may take up to 32 bits. As automata traditionally use symbol encodings taking 8 bits, the different alphabet and symbol sizes bring up the question whether they may be exploited to either decrease memory use for the automata’s transition tables or to decrease string processing time. In [3], stretching and jamming were introduced as transformations on finite automata. Given a finite automaton, we can stretch it by splitting each single transition into two or more sequential transitions, thereby introducing additional intermediate states. Jamming is the inverse transformation, in which two or more successive transitions are joined into a single transition, thereby removing redundant intermediate states. In this paper, we only consider a restricted form of stretching and jamming, in which a fixed factor is used to stretch (jam) transitions (transition paths) in a given automaton, and in which transition symbols are assumed to be encoded as bit strings. We consider improved versions of the algorithms that were presented in [3] for this particular form of stretching and jamming. The algorithms were implemented in c++ and used to benchmark the transformations. The results of this benchmarking indicate that, under certain conditions, stretching may be beneficial to memory use to the detriment of processing time, while jamming may be beneficial to processing time to the detriment of memory use. The latter seems potentially useful in the case of DNA processing, while the former may be for Unicode processing. Keywords: finite automata; transformation; split transition; join transition; transition table size; string processing time