# US 12,222,911 B1 · String data error detection and repair

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,222,911 B1
- Document ID: US12222911B1
- Status: Granted
- Kind: B1
- Application number: 18/374,131
- Filed: 2023-09-28
- Granted: 2025-02-11
- Earliest claimed: 2023-09-28
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Mukul Singh; José Pablo Cambronero Sánchez; Sumit Gulwani; Vu Minh Le; Carina Suzana Negreanu; Gust Ben Anneloes Verbruggen
- Web page: https://patentgrep.com/patent/US12222911B1

## CPC

- G06F 16/215: Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 40/18: of spreadsheets (form-filling G06F40/174)
- G06F 40/232: Orthographic correction, e.g. spell checking or vowelisation
- G06F 40/30: Semantic analysis
- G06N 3/0455: Auto-encoder networks; Encoder-decoder networks
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

The method of claim 1, wherein the method comprises ranking a set of candidate repairs.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 1)

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.

### Claim 10 (depends on 1)

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.

### Claim 11 (depends on 1)

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.

### Claim 12 (depends on 1)

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.

### Claim 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.

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 13)

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.

### Claim 16 (depends on 13)

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.

### Claim 17 (depends on 13)

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.

### Claim 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.

### Claim 19 (depends on 18)

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.

### Claim 20 (depends on 18)

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.