FUZZY STRING MATCHING USING TREE DATA STRUCTURE

• US 20070260595A1
• Filed: 05/02/2006
• Published: 11/08/2007
• Est. Priority Date: 05/02/2006
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horne, David, Wood, Elizabeth, Beatty, Bryan, Lawler, Duncan, Faaland, Nikolai
• Application Number:
  US11/381,182
• Publication Number:
  US 20070260595A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/903 Querying for retrieval from the web G06F16/953
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually

Abstract

The subject disclosure pertains to systems and methods for performing fuzzy searches of a tree data structure. A search request can include a search term or terms and search conditions. The tree is traversed in response to the search request and nodes of the tree are examined using a function or set of rules to generate a score. The score reflects the probability that the current node is a match to the search term and can be used to determine the search results to be returned. Due to the organization of the tree, if the score indicates that the current node is not a possible match, child nodes of the current node will not be possible matches. Therefore, the traversal of the current node and its children can be terminated.

Claims

1. A system for facilitating a fuzzy search of a tree data store, comprising:

a traversal component that traverses the tree data store to a node; and

an evaluation component that evaluates a key of the node to determine a score based at least in part upon a search term and the key, search results are based at least in part on the score.

2. The system of claim 1, the traversal component utilizes the score in determining traversal of the tree data store.

3. The system of claim 1, further comprising:

a subgroup component that evaluates subgroup results for a plurality of subgroups of the search term and generates a subgroup score based at least in part upon the search term and the subgroup results, the subgroup score is used in determining the search result.

4. The system of claim 1, further comprising:

an input component that receives the search term and at least one search condition.

5. The system of claim 4, the at least one search condition includes a termination condition.

6. The system of claim 4, the at least one search condition includes a traversal threshold, traversal of the tree data store is based at least in part on a comparison of the score to the traversal threshold.

7. The system of claim 1, further comprising:

an output component that outputs the search results, the search results are based upon the and an output threshold.

8. The system of claim 1, further comprising:

an interface component that allows a user to specify the search term and an evaluation function to be used by the evaluation component.

9. The system of claim 1, the tree data store is a trie.

10. A method facilitating fuzzy searching of a tree data store for a search term, comprising:

navigating the tree data store;

generating a score for a node of the tree data store utilizing a fuzzy matching function based at least in part upon the search term; and

determining search results based at least in part on the score.

11. The method of claim 10, further comprising:

updating the fuzzy matching function.

12. The method of claim 10, generating the score for the node further comprises:

applying a penalty determined by the fuzzy matching function to the score for each mismatch between the search term and a key of the node.

13. The method of claim 10, further comprising:

providing the search results to a user.

14. The method of claim 13, further comprising:

ordering the search results based at least in part upon the score.

15. The method of claim 13, providing the search results further comprises:

obtaining a value associated with the node

obtaining data from a data store using the value; and

providing the data to the user.

16. The method of claim 10, further comprising:

receiving a search request that includes the search term;

separating the search term into a plurality of subgroups; and

evaluating the subgroup results for each of the plurality of subgroups to determine a possible match for the search term.

17. A system for facilitating a fuzzy search of a tree data structure, comprising:

means for traversing the tree data structure;

means for evaluating a node to generate a score based at least in part on a search term utilizing a fuzzy matching function; and

means for providing search results based at least in part on the score.

18. The system of claim 17, further comprising:

means for separating the search term into a plurality of subgroups; and

means for evaluating subgroup results for each of the plurality of subgroups to determine the search results.

19. The system of claim 17, means for providing search results, further comprises:

means for obtaining a value associated with the node; and

means for obtaining data from a data store using the value associated with the node.

20. The system of claim 17, the tree data structure is a trie.