Giant complete automaton for uncertain multiple string matching and its high speed construction algorithm

doi:10.1007/s11432-011-4363-z

	Giant complete automaton for uncertain multiple string matching and its high speed construction algorithm
	Hu Yue 1,2; Gao QingShi 1,2; Guo Li 2; Wang PeiFeng 1
	2011-08-01
发表期刊	SCIENCE CHINA-INFORMATION SCIENCES
ISSN	1674-733X
卷号	54 期号:8 页码:1562-1571
摘要	Multiple string matching is often completed under the presence of U- or V-uncertain-strings, or combinations thereof. Recognizing large numbers of strings with U-, V-, and U-V-uncertain-strings, including the interleaving of two or more uncertain strings, is important to thoroughly gathering useful information and detecting harmful information. This paper proposes a complete automaton and its high-speed construction algorithm for large-scale U-, V-, and U-V-uncertain multiple strings, including two or more uncertain strings interlaced with one another. The maximum number of parallel complete automation of the V-uncertain string is also given. This paper reveals that there are two kinds of pretermissions, i.e., similarly-connected and interlaced-string pretermissions, and that mistake may appear in the matching of the regular expressions, or states in the automaton may increase in number, if the intersection of the U-uncertain strings sets and the homologous subsequent special point in the U-uncertain strings sets are not eliminated from the whole system.
关键词	multiple string matching U-uncertain-strings V-uncertain-strings U-V-uncertain-strings complete automaton
DOI	10.1007/s11432-011-4363-z
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[60873002] ; National High Technology Research and Development Program of China[2007CB311100]
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems
WOS记录号	WOS:000293188100002
出版者	SCIENCE PRESS
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/13072
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Hu Yue
作者单位	1.Univ Sci & Technol Beijing, Sch Informat Engn, Beijing 100083, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Hu Yue,Gao QingShi,Guo Li,et al. Giant complete automaton for uncertain multiple string matching and its high speed construction algorithm[J]. SCIENCE CHINA-INFORMATION SCIENCES,2011,54(8):1562-1571.
APA	Hu Yue,Gao QingShi,Guo Li,&Wang PeiFeng.(2011).Giant complete automaton for uncertain multiple string matching and its high speed construction algorithm.SCIENCE CHINA-INFORMATION SCIENCES,54(8),1562-1571.
MLA	Hu Yue,et al."Giant complete automaton for uncertain multiple string matching and its high speed construction algorithm".SCIENCE CHINA-INFORMATION SCIENCES 54.8(2011):1562-1571.