Improving Regular-Expression Matching on Strings Using Negative Factors

The problem of finding matches of a regular expression (RE) on a string exists in many applications such as text edit-ing, biosequence search, and shell commands. Existing tech-niques first identify candidates using substrings in the RE, then verify each of them using an automaton. These tech-niques become inefficient when there are many candidate oc-currences that need to be verified. In this paper we propose a novel technique that prunes false negatives by utilizing neg-ative 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 give a full specification of this technique. We develop an efficient algorithm that utilizes negative factors to prune candidates, then improve it by us-ing bit operations to process negative factors in parallel. We show that negative factors, when used together with neces-sary 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 thorough experimental study of this tech-nique on real data sets, including DNA sequences, proteins, and text documents, and show the significant performance improvement when applying the technique in existing algo-rithms. For instance, it improved the search speed of the popular Gnu Grep tool by 11 to 74 times for text docu-ments