CompactedImplementationsofDeterministicFiniteAutomata资源-CSDN文库

101 浏览量 2021-02-09 00:48:04 上传评论收藏 137KB PDF 举报

资源推荐

资源详情

资源评论

RESEARCH ARTICLE

Printed in the United States of America

Journal of

Computational and Theoretical Nanoscience

Vol. 11, 1–6, 2014

Compacted Implementations of

Deterministic Finite Automata

Meng Zhang

1 ∗

, Yi Zhang

, Wei Lv

, and Chen Hou

College of Computer Science and Technology, Jilin University, Changchun, China

Department of Computer Science, Jilin Business and Technology College, Changchun, China

Automaton is a popular data structure with many applications. We present implementation methods

of deterministic ﬁnite automaton that allow both efﬁcient space usage and performance. The ﬁrst

method utilizes the succinct data structures to speedup the computation of the transition function.

The method archives O(log log  ) time state transition with little augmented memory where  is the

size of the alphabet. The second method, namely overlapping table, reduces the space require-

ments of automata implemented by the state transition table approach. It makes the transition tables

of states share the overlapping address space thus reduces the space usage. The method has an

O(1) time state transition, while using fewer memory.

Keywords: Automaton, Compression, Succinct Data Structure.

1. INTRODUCTION

The deterministic ﬁnite automaton (DFA) is one of the

most popular data structures.

1 2

It is used in many ﬁelds

of computer science, such as data compression, pattern

matching, regular expression matching and text indexing.

Several DFAs used in these applications have been pro-

posed, such as Aho-Corasick automata,

automata for rec-

ognizing regular expressions,

sufﬁx automata

5 6

and the

factor oracle.

The AC automaton solves the multiple pat-

tern matching problem in Onlog  time ( is the size of

the alphabet, n is the length of the input text) which gen-

eralizes the Knuth–Morris–Pratt algorithm.

The AC algo-

rithm is extensively used in practice, such as deep packet

inspection. The sufﬁx automaton presented by Blumer

et al.

is the minimal deterministic automaton accepting

the set of sufﬁxes of a text.

Sufﬁx automaton is one of

the core data structures of several efﬁcient string match-

ing algorithms.

The Factor Oracle

is derived from the

DAWG. It can recognize more than the exact factors of a

string to achieve simplicity and low memory requirements.

The factor oracle is also applied in pattern matching, data

compression and machine learning.

The high space usage of automata limits their appli-

cability. In this paper, we focus on the implementation

of automata that allows both efﬁcient storage and usage.

We don’t study the techniques for compacting speciﬁc

automata, such as reducing the number of states or edges

∗

Author to whom correspondence should be addressed.

or using the NFA (non-determined ﬁnite automaton) to

simulating the DFA. The problem that we consider is

to represent the general DFA space economically while

not slowing down the performance. Our techniques are

general-purpose that can be used in representing any type

of DFAs. We will use automata to refer to DFAs in

the rest of the paper. We give two representing meth-

ods. The ﬁrst one utilizes the succinct data structures

to speedup the computation of the transition function,

archiving O(log log ) running time. The second one,

namely overlapping table, reduces the space requirements

of automata implemented by the state transition table

approach. In the case of constant alphabets, each state

in a DFA has its own -entry transition table. There are

empty entries in the transition tables. Our approach makes

the transition tables overlap, that is, tables share some

space such that an empty entry of one table is used by

a non-empty entry of another table. To solve the prob-

lem of determining the ownership of table entries, we

introduce a method that uses log -bit labels to identify

each table. The total memory of the tables is reduced

by reusing empty entries. The problem of generating the

minimal overlapping table is an optimization problem.

This problem can be reduced to the shortest common

superstring problem (SCS for short). Given a substring-

free set of strings P, the SCS asks for a shortest com-

mon superstring of P , that is, a minimum-length string

containing all strings from P as substrings. In computa-

tional biology,

11–13

the SCS is used for the DNA frag-

ment assembly problem.

The SCS is NP hard

and even

J. Comput. Theor. Nanosci. 2014, Vol. 11, No. 3 1546-1955/2014/11/001/006 doi:10.1166/jctn.2014.3443 1

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余5页未读，立即下载

评论收藏

内容反馈

weixin_38747592

粉丝: 6
资源: 937

Compacted Implementations of Deterministic Finite Automata

Nondeterministic_to_Deterministic_Finite_Automata

finite automata

有穷自动机的化简与确定化

automata-dfa:有限确定自动机 (DFA) 的实现

有限状态自动机

BitArray_src.zip_As One_bit array

Numerical modelling of swelling and shrinking soils around

EIT - The Internal Extent Formula for Compacted Tries-计算机科学

Compacted Sewage Sludge as a Barrier for Tailings: the Microbial Functional Diversity in the Compacted Sludge Specimen

Compacted Sewage Sludge as a Barrier for Tailings: the Bacterial Community Structure Diversity in the Compacted Sludge

The in Situ Shear Strength of Roller Compacted Concrete in the Dam of Jinghong Hydropower Station

GitHub Compacted-crx插件

squashfs1.3r3.tar.gz

NewSID（光学习一下代码就可以了，没看清楚介绍别运行）

Hydrothermal Solidification of Diatomite and Its Heat Insulating Property (2012年)

船舶安全管理体系文件-船舶垃圾管理计划参照.pdf

InK-Compact- In-Kernel Stream Compaction and Its Application to Multi-Kernel Data Visualization on General-Purpose GPUs - 2013-计算机科学

squashfs2.2-r2.tar.gz

VB编程资源大全（英文源码 数据库）

einars-js-beautify

建筑工程名词解析.pdf

几篇经典的关于WMSN的IEEE论文

com组建C++调用封装

建筑地基基础工程施工质量验收规范.pdf

CCL非线性吸附特性及孔隙率变化对污染物运移影响分析 (2008年)

碾压混凝土调整为常态混凝土专题报告.docx

BattleshipRoyale-LPOO2018:使用@joaomalheiro开发的使用LIBGDX（LPOO最终项目）的Android战舰游戏

基于GA-BP神经网络的碾压混凝土压实度实时评价方法.pdf

建筑施工组织2021-第八章 砼工程施工.doc

最新资源

VB编程资源大全（英文源码数据库）

建筑施工组织2021-第八章砼工程施工.doc