Query string matching method and apparatus
View Patent ↗In one implementation, a method is provided for increasing relevance of database search results. The method includes receiving a subject query string and determining a trained edit distance between the subject query string and a candidate string using trained cost factors derived from a training set of labeled query transformations. A trained cost factor includes a conditional probability for mutations in labeled non-relevant query transformations and a conditional probability for mutations in labeled relevant query transformations. The candidate string is evaluated for selection based on the trained edit distance. In some implementations, the cost factors may take into account the context of a mutation. As such, in some implementations multi-dimensional matrices are utilized which include the trained cost factors.
1. A computerized method for increasing relevance of database search results, the method comprising:
electronically receiving, via a computing device, a subject query string, the subject query string capable of including a plurality of words;
determining, via the computing device, a trained edit distance between the subject query string and at least one candidate string using trained cost factors derived from a training set of labeled query transformations, a trained cost factor comprises a sum of a conditional probability for mutations labeled as non-relevant query transformations and a conditional probability for mutations labeled as relevant query transformations, determining the trained edit distance includes using a multi-dimensional cost matrix, which is a transition matrix, including the trained cost factors, the cost matrix includes a list of acceptable mutations for a given query string and one or more probabilities of occurrence for a given character;
evaluating, via the computing device, the at least one candidate string for selection based on the trained edit distance; and
providing a list of candidate string, wherein determining the trained edit distance includes using the list of candidate strings.
2. The method of claim 1 wherein determining the trained edit distance comprises using at least one of: (a) a substitutions matrix, (b) an insertions matrix, (c) a deletions matrix, or (d) a transpositions matrix.
3. The method of claim 2 wherein determining the trained edit distance comprises using trained cost factors associated with a context of a mutation.
4. The method of claim 3 wherein determining the trained edit distance comprises using trained cost factors including at least one of: (a) trained costs based on a position of a mutation in a string, (b) trained costs of a mutation based on a size of a string, (c) trained costs of a mutation considering at least one other mutation within a string, (d) trained costs of a mutation in view of a character in a string, or (e) trained costs of a mutation in view of character combinations within a string.
5. The method of claim 1 wherein determining the trained edit distance comprises using trained cost factors associated with a context of a mutation.
6. The method of claim 5 wherein determining the trained edit distance further comprises using trained cost factors including at least one of: (a) trained costs based on a position of a mutation in a string, (b) trained costs of a mutation based on a size of a string, (c) trained costs of a mutation considering at least one other mutation within a string, (d) trained costs of a mutation in view of a character in a string, or (e) trained costs of a mutation in view of character combinations within a string.
7. The method of claim 1 wherein determining the trained edit distance comprises using trained cost factors associated with a context of a mutation.
8. The method of claim 1 selecting at least one candidate string corresponding to the subject query string based on the trained edit distance.
9. The method of claim 1 further comprising: providing an abbreviated list of candidate strings from a group of candidate strings; and wherein determining the trained edit distance comprises using the abbreviated list of candidate strings.
10. The method of claim 9 wherein providing the abbreviated list of candidate strings comprises providing candidate strings within a uniform edit distance of the subject query string.
11. The method of claim 1 further comprising: searching for an exact match for the subject query string prior to determining the trained edit distance; and determining the trained edit distance if an exact match for the subject query string is not found.