Regular expression generation using longest common subsequence algorithm on spans

1. A method of generating regular expressions using a longest common subsequence (LCS) algorithm on spans, the comprising:

receiving, by a regular expression generator comprising one or more processors, input data comprising a plurality of character sequences;

converting, by the regular expression generator, each of the plurality of character sequences into a set of spans, resulting in a plurality of sets of spans, wherein each span comprises a data structure storing a character class code and a repetition count range;

executing, by the regular expression generator, the longest common subsequence (LCS) algorithm, wherein said executing comprises;

receiving a first set of spans, including a first span corresponding to a first subsequence of characters;

receiving a second set of spans, wherein the second set of spans does not include a span corresponding to the first subsequence of characters

executing the LCS algorithm on the plurality of sets of spans; and

capturing an output of executing the LCS algorithm on the plurality of sets of spans; and

generating, by the regular expression generator, a first regular expression based on the output of the LCS algorithm, wherein the output of the LCS algorithm includes a third set of spans, including a second span corresponding to a first subsequence of characters, and wherein the repetition count range of the second span includes a minimum count range of zero.

2. The method of claim 1 , wherein the first regular expression matches one or more character sequences that include the first subsequence of characters, and matches one or more character sequences that do not include the first subsequence of characters.

3. The method of claim 1 , further comprising:

identifying a first text fragment comprising one or more characters, wherein the first text fragment is found within each of the plurality of character sequences;

storing the first text fragment; and

after generating the first regular expression, executing a simplification process on the first regular expression, wherein the simplification process comprises replacing a corresponding portion of the first regular expression with the first text fragment.

4. The method of claim 3 , wherein executing the simplification process on the first regular expression comprises:

determining a first span associated the first text fragment;

determining a number of times within the plurality of sets of spans, that the first span corresponds to the first text fragment; and

replacing the first span within the first regular expression, with the first text fragment, in response to determining that the number of times that the first span corresponds to the first text fragment within the plurality of spans, is greater than a predetermined threshold.

5. The method of claim 1 , wherein converting each of the plurality of character sequences into the set of spans comprises:

converting, by the regular expression generator, each of the plurality of character sequences into a set of regular expression codes, resulting in a plurality of sets of regular expression codes; and

converting, by the regular expression generator, each of the plurality of sets of regular expression codes into a set of spans.

6. The method of claim 1 , wherein the input data comprises three or more character sequences, and wherein executing the LCS algorithm comprises:

identifying, within the output of the LCS algorithm, a first span with a minimum count range of zero, and a second span with a minimum count range of zero; and

merging the first span and the second span within the output of the LCS algorithm.

7. A system for generating regular expressions using a longest common subsequence (LCS) algorithm on spans, the system comprising:

a processing unit comprising one or more processors; and

memory storing instructions that, when executed by the processing unit, cause the system to:

receive input data comprising a plurality of character sequences;

convert each of the plurality of character sequences into a set of spans, resulting in a plurality of sets of spans, wherein each span comprises a data structure storing a character class code and a repetition count range;

executing, by a regular expression generator, the longest common subsequence (LCS) algorithm, wherein said executing comprises:

receiving a first set of spans, including a first span corresponding to a first subsequence of characters;

receiving a second set of spans, wherein the second set of spans does not include a span corresponding to the first subsequence of characters

executing the LCS algorithm on the plurality of sets of spans; and

generate a first regular expression based on an output of the LCS algorithm, wherein the output of the LCS algorithm includes a third set of spans, including a second span corresponding to a first subsequence of characters, wherein the repetition count range of the second span includes a minimum count range of zero.

8. The system of claim 7 , wherein the first regular expression matches one or more character sequences that include the first subsequence of characters, and matches one or more character sequences that do not include the first subsequence of characters.

9. The system of claim 7 , the memory storing further instructions that, when executed by the processing unit, cause the system to:

identify a first text fragment comprising one or more characters, wherein the first text fragment is found within each of the plurality of character sequences;

store the first text fragment; and

after generating the first regular expression, execute a simplification process on the first regular expression, wherein the simplification process comprises replacing a corresponding portion of the first regular expression with the first text fragment.

10. The system of claim 9 , wherein executing the simplification process on the first regular expression comprises:

determining a first span associated the first text fragment;

determining a number of times within the plurality of sets of spans, that the first span corresponds to the first text fragment; and

replacing the first span within the first regular expression, with the first text fragment, in response to determining that the number of times that the first span corresponds to the first text fragment within the plurality of spans, is greater than a predetermined threshold.

11. The system of claim 7 , wherein converting each of the plurality of character sequences into the set of spans comprises:

converting each of the plurality of character sequences into a set of regular expression codes, resulting in a plurality of sets of regular expression codes; and

converting each of the plurality of sets of regular expression codes into a set of spans.

12. The system of claim 7 , wherein the input data comprises three or more character sequences, and wherein executing the LCS algorithm comprises:

identifying, within the output of the LCS algorithm, a first span with a minimum count range of zero, and a second span with a minimum count range of zero; and

merging the first span and the second span within the output of the LCS algorithm.

13. A non-transitory computer-readable media for generating regular expressions using a longest common subsequence (LCS) algorithm on spans, the computer-readable media comprising computer-executable instructions which when executed on a computer system, cause the computer system to:

receive input data comprising a plurality of character sequences;

convert each of the plurality of character sequences into a set of spans, resulting in a plurality of sets of spans, wherein each span comprises a data structure storing a character class code and a repetition count range;

execute the longest common subsequence (LCS) algorithm, wherein said executing comprises:

receiving a first set of spans, including a first span corresponding to a first subsequence of characters;

receiving a second set of spans, wherein the second set of spans does not include a span corresponding to the first subsequence of characters

executing the LCS algorithm on the plurality of sets of spans; and

capturing an output of executing the LCS algorithm on the plurality of sets of spans; and

generate a first regular expression based on the output of the LCS algorithm, wherein the output of the LCS algorithm includes a third set of spans, including a second span corresponding to a first subsequence of characters, wherein the repetition count range of the second span includes a minimum count range of zero.

14. The computer-readable media of claim 13 , wherein the first regular expression matches one or more character sequences that include the first subsequence of characters, and matches one or more character sequences that do not include the first subsequence of characters.

15. The computer-readable media of claim 13 , the computer-executable instructions further causing the computer system to:

identify a first text fragment comprising one or more characters, wherein the first text fragment is found within each of the plurality of character sequences;

store the first text fragment; and

after generating the first regular expression, execute a simplification process on the first regular expression, wherein the simplification process comprises replacing a corresponding portion of the first regular expression with the first text fragment.

16. The computer-readable media of claim 15 , wherein executing the simplification process on the first regular expression comprises:

determining a first span associated the first text fragment;

determining a number of times within the plurality of sets of spans, that the first span corresponds to the first text fragment; and

replacing the first span within the first regular expression, with the first text fragment, in response to determining that the number of times that the first span corresponds to the first text fragment within the plurality of spans, is greater than a predetermined threshold.

17. The computer-readable media of claim 15 , wherein converting each of the plurality of character sequences into the set of spans comprises:

converting each of the plurality of character sequences into a set of regular expression codes, resulting in a plurality of sets of regular expression codes; and

converting each of the plurality of sets of regular expression codes into a set of spans.