Back to results
US 12,524,446 B2Granted
Regular expression generation using longest common subsequence algorithm on regular expression codes
AssigneeOracle International Corporation
InventorsMichael Malak, Luis E. Rivas, Mark L. Kreider
Life of this patent
Estimating the term…
Abstract
Disclosed herein are techniques related to automated generation of regular expressions. In some embodiments, a regular expression generator may receive input data comprising one or more character sequences. The regular expression generator may convert character sequences into a sets of regular expression codes and/or span data structures. The regular expression generator may identify a longest common subsequence shared by the sets of regular expression codes and/or spans, and may generate a regular expression based upon the longest common subsequence.
Claims20
A method of generating regular expressions using a longest common subsequence (LCS) algorithm, the comprising:
- receiving, by a regular expression generator comprising one or more processors, first input data comprising a first character sequence;
- converting, by the regular expression generator, the first character sequence into a first set of regular expression codes, wherein the first set of regular expression codes include one or more character categories associated with characters in the first character sequence;
- receiving, by the regular expression generator, second input data comprising a second character sequence;
- converting, by the regular expression generator, the second character sequence into a second set of regular expression codes, wherein the second set of regular expression codes include one or more character categories associated with characters in the second character sequence, and
- wherein the first set of regular expression codes and the second set of regular expression codes are intermediate regular expression codes generated prior to a first regular expression and configured to map an output of executing the LCS algorithm on the first set of regular expression codes and the second set of regular expression codes to the first regular expression;
- executing, by the regular expression generator, the longest common subsequence algorithm on the first set of regular expression codes for the first character sequence and the second set of regular expression codes for the second character sequence;
- capturing the output of executing the LCS algorithm on the first set of regular expression codes for the first character sequence and the second set of regular expression codes for the second character sequence;
- and
- generating, by the regular expression generator, the first regular expression based on the output of the LCS algorithm, wherein the first regular expression comprises a sequence of characters defining a pattern in the output of the first set of regular expression codes and the second set of regular expression codes.
6 more elements
A system for generating regular expressions using a longest common subsequence (LCS) algorithm, 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 first input data comprising a first character sequence;
- convert the first character sequence into a first set of regular expression codes, wherein the first set of regular expression codes include one or more character categories associated with characters in the first character sequence;
- receive second input data comprising a second character sequence;
- convert the second character sequence into a second set of regular expression codes, wherein the second set of regular expression codes include one or more character categories associated with characters in the second character sequence, and
- wherein the first set of regular expression codes and the second set of regular expression codes are intermediate regular expression codes generated prior to a first regular expression and configured to map an output of executing the LCS algorithm on the first set of regular expression codes and the second set of regular expression codes to the first regular expression;
- execute the longest common subsequence algorithm on the first set of regular expression codes for the first character sequence and the second set of regular expression codes for the second character sequence;
- capturing the output of executing the LCS algorithm on the first set of regular expression codes for the first character sequence and the second set of regular expression codes for the second character sequence;
- and
- generate the first regular expression based on the output of the LCS algorithm, wherein the first regular expression comprises a sequence of characters defining a pattern in the output of the first set of regular expression codes and the second set of regular expression codes.
9 more elements
A non-transitory computer-readable media for generating regular expressions using a longest common subsequence (LCS) algorithm, the computer-readable media comprising computer-executable instructions which when executed on a computer system, cause the computer system to:
- receive first input data comprising a first character sequence;
- convert the first character sequence into a first set of regular expression codes, wherein the first set of regular expression codes include one or more character categories associated with characters in the first character sequence;
- receive second input data comprising a second character sequence;
- convert the second character sequence into a second set of regular expression codes, wherein the second set of regular expression codes include one or more character categories associated with characters in the second character sequence, and
- wherein the first set of regular expression codes and the second set of regular expression codes are intermediate regular expression codes generated prior to a first regular expression and configured to map an output of executing the LCS algorithm on the first set of regular expression codes and the second set of regular expression codes to the first regular expression;
- execute the longest common subsequence algorithm on the first set of regular expression codes for the first character sequence and the second set of regular expression codes for the second character sequence;
- capturing the output of executing the LCS algorithm on the first set of regular expression codes for the first character sequence and the second set of regular expression codes for the second character sequence;
- and
- generate the first regular expression based on the output of the LCS algorithm, wherein the first regular expression comprises a sequence of characters defining a pattern in the output of the first set of regular expression codes and the second set of regular expression codes.
6 more elements
Dependencies are inferred from the claim text.