Regular expression generation using combinatoric longest common subsequence algorithms

Patent metadata

Field	Value
Publication number	US-11269934-B2
Application number	US-201916438313-A
Country	US
Kind code	B2
Filing date	Jun 11, 2019
Priority date	Jun 13, 2018
Publication date	Mar 8, 2022
Grant date	Mar 8, 2022

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.

First claim

What is claimed is:

1. 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 data from a table of data corresponding to a first character sequence;
receiving, by the regular expression generator, second data from the table of data corresponding to a second character sequence;
executing, by the regular expression generator the longest common subsequence (LCS) algorithm on the first data and the second data more than a threshold plurality of times,
wherein an output is recorded for each said execution of the LCS algorithm on the first data and the second data, and
wherein each execution corresponds to a different combination of a plurality of text processing directions and a plurality of anchoring options;
analyzing, by the regular expression generator, a plurality of outputs recorded for the plurality of executions of the LCS algorithm, and selecting a first output of the plurality of outputs; and
generating, by the regular expression generator, a first regular expression based on the first selected output of the LCS algorithm.

2. The method of claim 1 , wherein analyzing the plurality of outputs and selecting the first output of the plurality of outputs comprises:
determining a first subset of the plurality of executions of the LCS algorithm that failed to identify a longest common subsequence between the first and second data, wherein the first subset of the plurality of executions of the LCS algorithm fail to identify the longest common subsequence between the first and second data when one or more negative examples are matched;
determining a second subset of the plurality of executions of the LCS algorithm that successfully identified the longest common subsequence between the first and second data; and
selecting, as the first output, a shortest of the longest common subsequences identified by the second subset of the plurality of executions of the LCS algorithm.

3. The method of claim 1 , wherein performing the plurality of executions of the LCS algorithm comprises:
performing a first subset of the plurality of executions of the LCS algorithm in which the first and second data are processed left-to-right during the LCS algorithm; and
performing a second subset of the plurality of executions of the LCS algorithm in which the first and second data are processed right-to-left during the LCS algorithm.

4. The method of claim 1 , wherein performing the plurality of executions of the LCS algorithm comprises:
performing a first subset of the plurality of executions of the LCS algorithm in which the output of the LCS algorithm is anchored to a beginning of the character sequences corresponding to the first and second data;
performing a second subset of the plurality of executions of the LCS algorithm in which the output of the LCS algorithm is anchored to an end of the character sequences corresponding to the first and second data; and
performing a third subset of the plurality of executions of the LCS algorithm in which the output of the LCS algorithm is not anchored to the beginning or the end of the character sequences corresponding to the first and second data.

5. The method of claim 1 , wherein performing the plurality of executions of the LCS algorithm comprises:
performing a first subset of the plurality of executions of the LCS algorithm in which the LCS algorithm is configured to identify and align on a common word within the first and second data; and
performing a second subset of the plurality of executions of the LCS algorithm in which the LCS algorithm is not configured to identify and align on common words within the first and second data.

6. The method of claim 1 , wherein each of the first and second data correspond to sets of regular expression codes generated based on input character sequences.

7. The method of claim 1 , wherein each of the first and second data correspond to sets of spans generated based on input character sequences.

8. 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 data from a table of data corresponding to a first character sequence;
receive second data from the table of data corresponding to a second character sequence;
execute the longest common subsequence (LCS) algorithm on the first data and the second data more than a threshold plurality of times,
wherein an output is recorded for each said execution of the LCS algorithm on the first data and the second data, and
wherein each execution corresponds to a different combination of a plurality of text processing directions and a plurality of anchoring options;
analyze a plurality of outputs recorded for the plurality of executions of the LCS algorithm, and selecting a first output of the plurality of outputs; and
generate a first regular expression based on the first selected output of the LCS algorithm.

9. The system of claim 8 , wherein analyzing the plurality of outputs and selecting the first output of the plurality of outputs comprises:
determining a first subset of the plurality of executions of the LCS algorithm that failed to identify a longest common subsequence between the first and second data, wherein the first subset of the plurality of executions of the LCS algorithm fail to identify the longest common subsequence between the first and second data when one or more negative examples are matched;
determining a second subset of the plurality of executions of the LCS algorithm that successfully identified the longest common subsequence between the first and second data; and
selecting, as the first output, a shortest of the longest common subsequences identified by the second subset of the plurality of executions of the LCS algorithm.

10. The system of claim 8 , wherein performing the plurality of executions of the LCS algorithm comprises:
performing a first subset of the plurality of executions of the LCS algorithm in which the first and second data are processed left-to-right during the LCS algorithm; and
performing a second subset of the plurality of executions of the LCS algorithm in which the first and second data are processed right-to-left during the LCS algorithm.

11. The system of claim 8 , wherein performing the plurality of executions of the LCS algorithm comprises:
performing a first subset of the plurality of executions of the LCS algorithm in which the output of the LCS algorithm is anchored to a beginning of the character sequences corresponding to the first and second data;
performing a second subset of the plurality of executions of the LCS algorithm in which the output of the LCS algorithm is anchored to an end of the character sequences corresponding to the first and second data; and
performing a third subset of the plurality of executions of the LCS algorithm in which the output of the LCS algorithm is not anchored to the beginning or the end of the character sequences corresponding to the first and second data.

12. The system of claim 8 , wherein performing the plurality of executions of the LCS algorithm comprises:
performing a first subset of the plurality of executions of the LCS algorithm in which the LCS algorithm is configured to identify and align on a common word within the first and second data; and
performing a second subset of the plurality of executions of the LCS algorithm in which the LCS algorithm is not configured to identify and

Assignees

• Oracle Int Corp

Inventors

• Malak Michael
• Rivas Luis E
• Kreider Mark L

Classifications

• G06F16/3322 Primary

  using system suggestions (G06F16/3325 takes precedence) · CPC title

• G06F16/3329 Primary

  Natural language query formulation · CPC title

• G06F18/2323

  based on graph theory, e.g. minimum spanning trees [MST] or graph cuts · CPC title

• G06F16/90344

  by using string matching techniques · CPC title

• G06F16/258

  Data format conversion from or to a database · CPC title