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

Yue Hu, Qingshi Gao, Li Guo, PeiFeng WangScience China Information Sciences 2011 · OpenReview

Abstract

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.
BibTeX
@article{hu2011giant,
  author = {Yue Hu and Qingshi Gao and Li Guo and PeiFeng Wang},
  title = {{Giant complete automaton for uncertain multiple string matching and its high speed construction algorithm}},
  journal = {Science China Information Sciences},
  year = {2011},
  url = {https://openreview.net/forum?id=dPCTgCad3Zs},
}

Loading related content...

Figure