String data error detection and repair
Some embodiments perform fully unsupervised string error detection and repair, for strings containing both syntactic errors and semantic errors. In some embodiments, string error mitigation includes learning a regular-expression-based pattern that characterizes at least a predefined fraction of a set of string data values, identifying and masking a semantic substring, deriving edits to repair a string which contains the semantic substring, and replacing a mask value with a replacement substring that conforms to the pattern. Some embodiments utilize a language model. Some embodiments include or utilize a pattern learner, one or more learned significant patterns, and a repair engine. Some embodiments exploit program execution information to generate patterns when significant patterns are not initially found.
1. A string error mitigation method performed by a computing system, the method comprising:
learning a regular-expression-based pattern that characterizes at least a predefined fraction of a set of string data values, the learning comprising utilizing an inductive synthesis framework;
identifying, and masking out with a mask value, a substring based on a predefined set of semantic data types;
deriving one or more edits to repair a string which contains the mask value, the deriving comprising extracting a minimal sequence of edits through dynamic programming; and
replacing the mask value by a replacement substring which conforms to the regular-expression-based pattern.
2. The method of claim 1 , wherein the method performs fully unsupervised error detection on the set of string data values, and the method performs fully unsupervised error correction on the set of string data values.
3. The method of claim 1 , wherein the method comprises:
getting program execution information of a program which lists a string as an input to the program; and
exploiting at least a portion of the program execution information for error detection or error correction or both.
4. The method of claim 1 , wherein a full performance of the method is performed without reliance during the full performance on any user interaction during the full performance as a source of: a constraint, an example, or an annotation.
5. The method of claim 1 , wherein the method comprises learning a relationship between a non-error value and a significant pattern, and using the relationship as a constraint when predicting a concrete value in the repaired string.
6. The method of claim 1 , wherein the method comprises ranking a set of candidate repairs.
7. The method of claim 1 , wherein the method comprises exploiting outcome information from execution of a string dataset transformation program which received at least part of the set of string data values as input, the exploiting comprising:
learning at least one non-negative-outcome-based pattern which is based solely on string data values which are not associated with any negative outcome from execution of the string dataset transformation program; and
utilizing a learned non-negative-outcome-based pattern to perform string repair.
8. The method of claim 1 , wherein the method comprises submitting a set of one or more prompts to a language model, the set of one or more prompts comprising:
an identification of a semantic type in string data as being a sematic type;
an example with a non-masked example data portion and a corresponding masked example data portion; and
an inference request with a non-masked inference data portion and a request for a corresponding masked inference data portion.
9. The method of claim 1 , wherein the method is further characterized in at least one of the following ways:
the regular-expression-based pattern characterizes at least half of the set of string data values; or
the method comprises modifying a threshold which specifies the predefined fraction of the set of string data values.
10. The method of claim 1 , wherein deriving one or more edits to repair a string which contains the mask value comprises receiving from a language model at least of: a spelling correction, or a correction which changes a semantic type of a corrected substring.
11. The method of claim 1 , wherein the method comprises prompting a language module with a unitary prompt that includes multiple string data values of the set of string data values together in the unitary prompt.
12. The method of claim 1 , wherein the method comprises converting the regular-expression-based pattern into a non-deterministic finite state automaton, forming a directed acyclic graph, and utilizing the directed acyclic graph for calculating an edit cost of a candidate repair of a string data value of the set of string data values.
13. A string error mitigation computing system, comprising:
a digital memory;
a processor set comprising at least one processor, the processor set in operable communication with the digital memory;
a pattern learner interface which upon execution by the processor set sends a set of string data values to a pattern learner, and receives a set of one or more significant patterns from the pattern learner, the set of significant patterns including a set of one or more regular expressions which collectively match a predefined fraction of the string data values, and which also collectively define at least one outlier string data value; and
a repair engine interface which upon execution by the processor set sends a repair engine at least one significant pattern and at least one outlier string data value, and receives at least one edit program from the repair engine which upon edit program performance edits the outlier string data value to produce an edited outlier string data value which conforms to at least one significant pattern.
14. The system of claim 13 , wherein the pattern learner comprises a language model interface which upon execution by the processor set accesses a language model, the set of significant patterns is learned by the language model, and at least one significant pattern includes a masked substring which is based on a semantic data type.
15. The system of claim 13 , further comprising a ranker which upon execution by the processor set ranks candidate edit programs based on at least respective edit costs of the edit programs.
16. The system of claim 13 , wherein the system comprises:
a cost matrix which represents edit costs of a candidate edit program; and
a move matrix which represents edit actions of the candidate edit program.
17. The system of claim 13 , further comprising a string data transformation program analyzer, which upon execution by the processor set analyzes actual execution outcomes or simulated execution of a string dataset transformation program, or both, and wherein the system utilizes a result of executing the transformation program analyzer as a basis of learning at least one significant pattern.
18. A computer-readable storage device configured with data and instructions which upon execution by a processor cause a computing system to perform a string error mitigation method, the string error mitigation method comprising:
an AI-based regular expression learner means learning a regular-expression-based pattern that characterizes at least a predefined fraction of a set of string data values;
an AI-based semantic substring masker means identifying, and masking out with a mask value, a substring based on a predefined set of semantic data types;
the AI-based regular expression learner means treating the mask value as a placeholder character;
an edit deriver means of the computing system deriving one or more edits to repair a string which contains the mask value;
an AI-based value predictor means predicting a replacement substring; and
the computing system replacing the mask value by the replacement substring.
19. The computer-readable storage device of claim 18 , wherein the method comprises executing a string dataset transformation program on string data values, thereby producing execution outcomes, and learning at least one regular-expression-based pattern based solely on string data values which are not associated with any negative execution outcome.
20. The computer-readable storage device of claim 18 , wherein the method comprises detecting and repairing syntactic errors and semantic errors in the string data values.