Method and system for a pattern matching engine
AssigneeMicrosoft Corporation
InventorVlad Eminovici
Life of this patent
Estimating the term…
Abstract
A system and method directed to a matching engine for finding the best match for an input string from among a group of predefined string patterns is disclosed. The predefined patterns may include one or more wildcard characters. A metric value is computed for every predefined string pattern. If the input string matches more than one predefined pattern, then the pattern with the highest metric value is determined as the best match to the input string. Additionally, information of different types may be attached to the predefined patterns and used for further processing of information, for example, to make routing decisions or to run a program module.
Claims32
A computer-implemented method of finding a best match to a string of characters from among a plurality of string patterns;
- comprising:
- computing a metric value for each of the string patterns so that when the string of characters matches multiple string patterns, the metric values of the string patterns differentiate the quality of the matches;
- comparing the string of characters to each of the string patterns to determine which string patterns the string of characters matches;
- selecting from the matching string patterns a matching string pattern as the best match based on the quality of the match as indicated by the computed metric values of the matching string patterns;
- and
- storing and reporting the selected matching string pattern,
- wherein at least one of the string patterns includes at least one wildcard character;
- wherein computing the metric value of a string pattern further comprises:
- assigning a prefix value to all characters appearing before the wildcard;
- assigning a suffix value to all characters appearing after the wildcard;
- and
- adding the prefix value to the suffix value to obtain the metric value.
A system for finding the best match to an input string from among a plurality of predefined string patterns, comprising:
- means for computing a metric value for each predefined string pattern so that when the input string matches multiple predefined string patterns, the metric values of the string patterns differentiate the quality of the matches;
- means for determining which of the predefined string patterns match the input string;
- means for indicating a best match for the input string based on the quality of the match as indicated by the metric values of the matching predefined string patterns;
- and
- means for storing and reporting the best matching string pattern,
- wherein at least one of the string patterns includes at least one wildcard character;
- wherein the means for computing a metric value for each predefined string pattern further comprises:
- means for dividing the at least one string pattern into at least one substring;
- means for counting the number of characters in the at least one substring to obtain a substring value for the at least one substring;
- and
- means for adding the substring values of the at least one substring to obtain a metric value of the at least one pattern.
A computer-readable medium having computer executable instructions for finding a best match to a string of characters from among a plurality of string patterns, which, when executed comprise:
- computing a metric value for each of the string patterns so that when the string of characters matches multiple string patterns, the metric values of the string patterns differentiate the quality of the matches;
- comparing the string of characters to each of the string patterns to determine which string patterns match;
- selecting a string pattern from the matching string patterns as the best match based on the quality of the match as indicated by the computed metric value of the matching string patterns;
- and
- storing and reporting the selected matching string pattern,
- wherein at least one of the string patterns includes at least one wildcard character;
- wherein the computer executable instructions for computing the metric value of the first pattern, when executed, further comprise:
- assigning a prefix value to all characters appearing before the wildcard;
- assigning a suffix value to all characters appearing after the wildcard;
- and
- adding the prefix value to the suffix value to obtain the metric value.
A computer-implemented method of determining a best matching string pattern among a plurality of string patterns each including at least one wildcard character, comprising:
- dividing each string pattern into one or more substrings;
- determining a value for each substring;
- calculating a metric value of each pattern by adding together the value of each substring of the string pattern so that when an input string matches multiple string patterns, the metric values of the string patterns differentiate the quality of the matches;
- determining which string patterns match the input string;
- determining the best matching string pattern from among multiple matching string patterns based on the quality of the match as indicated by comparing the metric values of each matching string pattern;
- and
- storing and reporting the determined best matching string pattern.
A computer-implemented method of determining a metric value for a pattern including at least one wildcard, comprising:
- dividing the pattern into one or more substrings, wherein each substring is comprised of one or more contiguous characters separated from other characters by a wildcard character;
- counting the number of characters in each substring to obtain a value of the substring;
- adding the value of each substring to obtain a total value;
- assigning the total value as the metric value for the pattern, so that when an input string matches multiple patterns, the metric values of the patterns differentiate the quality of the matches;
- and
- storing and reporting the metric value for the string pattern.
A computer-implemented method of determining the best match to an input string from among predefined string patterns, comprising:
- receiving the input string;
- determining the predefined string patterns that match the input string;
- and
- selecting the predefined string pattern that is the best match for the input string from the matching predefined string patterns based on the quality of the match as indicated by a metric value computed for each string pattern that differentiates the quality of the matches;
- and
- storing and reporting the selected matching string pattern,
- wherein at least one of the predefined string patterns includes at least one wildcard character;
- wherein the metric value computed for each string pattern, further comprise:
- assigning a prefix value to all characters appearing before the wildcard;
- assigning a suffix value to all characters appearing after the wildcard;
- and
- adding the prefix value to the suffix value to obtain the metric value.
Dependencies are inferred from the claim text.