Negative Factor: Improving Regular-Expression Matching in Strings

• Main Authors: YANG, Xiaochun, QIU, Tao, WANG, Bin, ZHENG, Baihua, WANG, Yaoshu, LI, Chen
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2016
• Subjects: long sequence; performance; regular expression; algorithms; automata; patterns; search; Databases and Information Systems; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/3157; https://ink.library.smu.edu.sg/context/sis_research/article/4157/viewcontent/P_ID_51559_NegativeFactor_2015_afv.pdf
• Institution: Singapore Management University

The problem of finding matches of a regular expression (RE) on a string exists in many applications such as text editing, biosequence search, and shell commands. Existing techniques first identify candidates using substrings in the RE, then verify each of them using an automaton. These techniques be...