Can I read Negative Factor: Improving Regular-Expression Matching in Strings on EtoBox?
Negative Factor: Improving Regular-Expression Matching in Strings by Xiaochun Yang; Tao Qiu; Bin Wang; Baihua Zheng; Yaoshu Wang; Chen Li is a Computer Science article available to read on EtoBox.
What is Negative Factor: Improving Regular-Expression Matching in Strings about?
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 become inefficient when there are many candidate occurrences that need to be verified. In this article, we propose a novel technique that prunes false negatives by utilizing negative factors , which are substrings that cannot appear in an answer. A main advantage of the technique is that it can be integrated with many existing algorithms to improve their efficiency significantly. We present a detailed description of this technique. We develop an efficient algorithm that utilizes negative factors to prune candidates, then improve it by using bit operations to process negative factors in parallel. We show that negative factors, when used with necessary factors (substrings that must appear in each answer), can achieve much better pruning power. We analyze the large number of negative factors, and develop an algorithm for finding a small number of high-quality negative factors. We conducted a
Who reads Negative Factor: Improving Regular-Expression Matching in Strings?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Xiaochun Yang; Tao Qiu; Bin Wang; Baihua Zheng; Yaoshu Wang; Chen Li
- Publisher
- ACM
- Published
- 2016
- Language
- EN
- Field
- Computer Science (Physical Sciences)