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

• Published in: Science China. Information sciences 2011-08, Vol.54 (8), p.1562-1571
• Main Authors: Hu, Yue, Gao, QingShi, Guo, Li, Wang, PeiFeng
• Format: Article
• Language: English
• Subjects: Algorithms; Automation; Computer Science; Construction; High speed; Information Systems and Communication Service; Research Papers; String matching; Strings; 信息检测; 字符串匹配; 巨人; 正则表达式; 算法; 自动机
• ISSN: 1674-733X; 1869-1919
• DOI: 10.1007/s11432-011-4363-z

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.