DETECTING LONGEST REGULAR EXPRESSION MATCHES

摘要

In one embodiment, a computer-implemented method includes receiving a regular expression (regex) and input data. One or more spans are identified representing one or more matches in which the regex matches at least a portion of the input data. Each span corresponds to a corresponding match and includes a start offset of the corresponding match in the input data and an end offset of the corresponding match in the input data. The one or more matches are identified in a sequence. An order of the sequence of the one or more spans is modified. One or more filtered spans are generated, by a computer processor, by filtering out a subset of the one or more spans that are each contained by at least one other span in the one or more spans. The identifying, the modifying, and the filtering are performed at streaming rate.

主权项

1. A computer-implemented method, comprising:
receiving a regular expression (regex) and input data; identifying one or more spans representing one or more matches in which the regex matches at least a portion of the input data, wherein each span of the one or more spans corresponds to a corresponding match of the one or more matches and comprises a start offset of the corresponding match in the input data and an end offset of the corresponding match in the input data, and wherein the one or more matches are identified in a sequence; modifying an order of the sequence of the one or more spans; and generating, by a computer processor, one or more filtered spans by filtering out a subset of the one or more spans that are each contained by at least one other span in the one or more spans; wherein the identifying, the modifying, and the filtering are performed at streaming rate.