Microsoft patents method to split text search rules for faster processing
Microsoft has patented a method for breaking down complex text search patterns into two types of computer logic called deterministic and non-deterministic finite automata. The system checks if a search rule follows a single path or multiple paths and uses different splitting processes for each to create specific parts of a processing tree.
In the filing’s own words
Systems, methods, and computer-readable medium for splitting regular expressions between non-deterministic finite automaton and deterministic finite automaton are provided. A method includes parsing a set of regular expression patterns to generate an output. The method further includes processing the output to determine whether any of the set of regular expression patterns meets a specified criteria including whether a regular expression pattern is a single path regular expression. The method further includes using a first splitting process, splitting any of the set of regular expression patterns that meet the specified criteria into a first set of tokens. The method further includes using a second splitting process, different from the first splitting process, splitting any of the set of regular expression patterns that fail to meet the specified criteria into a second set of tokens.
What exactly they claim (claim 1)
1. A computer-implemented method comprising: parsing a set of regular expression patterns to generate an output; processing the output to determine whether any of the set of regular expression patterns meets a specified criteria including whether a regular expression pattern is a single path regular expression; using a first splitting process, splitting any of the set of regular expression patterns that meet the specified criteria into a first set of tokens; and using a second splitting process, different from the first splitting process, splitting any of the set of regular expression patterns that fail to meet the specified criteria into a second set of tokens, wherein the first splitting process outputs a first deterministic finite automaton (DFA) part of an abstract syntax tree (AST) and a first non-deterministic finite automaton (NFA) part of the AST, and wherein the second splitting process outputs a second DFA part of the AST and a second NFA part of the AST.
Facts
- Company
- Microsoft (Microsoft Technology Licensing, LLC)
- Official title
- Splitting regular expressions between non-deterministic finite automaton and deterministic finite automaton
- Patent number
- US12762344B2
- Application number
- 18661796
- Filed
- May 13, 2024
- Granted
- Oct 13, 2026
- Inventors
- 1
- Claims
- 20
Classified under
G06F 40/289 Physics & computingG06F 40/284 Physics & computingMore from Microsoft in AI & software
- Microsoft patents method to check AI answers against verified facts Oct 20, 2026
- Microsoft patents AI that presents PowerPoint slides for you Sep 3, 2026
- Microsoft patents method to check if LLM answers are based on real data Sep 10, 2026
- Microsoft patents system to blend multiple AI agents into one chat Oct 1, 2026
- Microsoft patents system that answers questions using your screen history Oct 15, 2026
Summaries are simplified from the filing’s own abstract and first claim. A patent filing is not a product announcement.
Patent data and drawings: U.S. Patent and Trademark Office (USPTO). Nebula is not affiliated with or endorsed by the USPTO.