METHOD AND SYSTEM FOR APPROXIMATE STRING MATCHING

• US 20080275837A1
• Filed: 04/07/2008
• Published: 11/06/2008
• Est. Priority Date: 05/01/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lambov, Branimir Z.
• Granted Patent: US 8,140,462 B2
• Time in Patent Office: Days
• US Class Current: 706/48
• CPC Class Codes: G06F 16/90344 by using string matching techniques

Abstract

A method and system for approximate string matching are provided for generating approximate matches whilst supporting compounding and correction rules. The method for approximate string matching of an input pattern to a trie data structure, includes traversing a trie data structure to find approximate partial and full character string matches of the input pattern. Traversing a node of the trie data structure to process a character of the string applies any applicable correction rules to the character, wherein each correction rule has an associated cost, adjusted after each character processed. The method includes accumulating costs as a string of characters is gathered, and restricting the traverse through the trie data structure according to the accumulated cost of a gathered string and potential costs of applicable correction rules.

Claims

1. A method for approximate string matching of an input pattern to a trie data structure, comprising:

traversing a trie data structure to find approximate partial and full character string matches of the input pattern, wherein traversing a node of the trie data structure to process a character of the string applies any applicable correction rules to the character, wherein each correction rule has an associated cost, adjusted after each character processed;

accumulating costs as a string of characters is gathered; and

restricting the traverse through the trie data structure according to the accumulated cost of a gathered string and potential costs of applicable correction rules.

2. A method as claimed in claim 1, wherein recursive processing of branches of the trie is:

fully performed if accumulated costs of a character string are below a predefined threshold;

performed with restriction to characters that match characters at active positions in the input pattern, or are in applicable outstanding correction rules;

or

not performed if such characters are not present.

3. A method as claimed in claim 1, wherein in addition to correction rules the method applies elementary transitions of characters including one of an insertion, a deletion, or a replacement, each associated with a cost.

4. A method as claimed in claims 1, wherein correction rules are generated automatically for all possible applications of character transposition in the input pattern.

5. A method as claimed in claim 1, further comprising including determining correction rules that are applicable to characters in an input pattern, before starting the traverse.

6. A method as claimed in claim 1, wherein applicable correction rules are indexed by a position of the character to be processed.

7. A method as claimed in claim 6, wherein indexing by the character position to be processed includes allowing for a predefined number of inserted or deleted characters in the string.

8. A method as claimed in claim 1, further comprising determining candidate approximate matches and using the accumulated cost as a weighting for the candidate matches.

9. A method as claimed in claim 1, including determining approximate partial matches where a length of the partial match is less than a length of the input pattern, and saving the partial matches with the accumulated cost as a starting cost for a traverse for right hand matches to the input pattern.

10. A method as claimed in claim 9, wherein traverses for right hand matches of compound words are started at the character position of an end position of the partial match.

11. A method as claimed in claim 9 further comprising iterating through all positions for which there is a partial match and using saved accumulated costs as starting points for right hand side match traverses.

12. A method as claimed in claim 11, wherein any full right hand side matches are combined with all left hand side partial matches.

13. A method as claimed in claim 12, wherein left hand side partial matches are combined.

14. A method as claimed in claim 9, wherein accumulated costs for one or more partial matches are used to compile a best case scenario for the right hand side look-up.

15. A method as claimed in claim 1, wherein correction rules are applied across points of attachments of word parts.

16. A method as claimed in claim 1, wherein vector processing is used to perform the corrections simultaneously for a range of displacements.

17. A data structure for use in approximate string matching of an input pattern to a trie data structure, comprising:

a data structure element for each applicable correction rule for a character of an input pattern, the element being indexed by a position of the character;

a matrix of costs indexed by the character position, wherein the matrix of costs is updated during the traverse of the trie data structure to reflect accumulated costs of applied correction rules.

18. A data structure as claimed in claim 17, wherein the character position is determined by a number of characters processed together with a displacement of inserted or deleted characters.

19. A data structure as claimed in claim 17, wherein multiple data structure elements are provided for a character position for multiple applicable correction rules for the character.

20. A data structure as claimed in any one of claims 17, wherein multiple data structure elements are stacked corresponding to a number of characters in the output of a correction rule.

21. A data structure as claimed in claim 20, wherein the stacked data elements are reversely linked.

22. A data structure as claimed in claim 17, including a matrix of saved costs for character positions of partial matches to the input pattern.

23. A system for approximate string matching of an input pattern to a trie data structure, comprising:

a trie data structure having nodes representing characters in a string, the trie data structure storing allowed character strings;

a plurality of character correction rules to be applied to the input pattern including a transition of one or more characters in the input pattern; and

a means for generating a correction rule structure for applicable correction rules for an input pattern, the correction rule structure having a plurality of rule elements indexed by a position of the character.

24. A system as claimed in claim 23, including means for setting parameters for approximate string matching, including costs of correction rules.

25. A system as claimed in claim 23, including means for storing accumulating costs for a gathered character string.

26. A system as claimed in claim 23, including means for setting a maximum cost to restrict the traverse of the trie data structure.

27. A system as claimed in claims 23, including means for storing partial string matches with a saved accumulated cost.

28. A system as claimed in claim 23, including vector processing means to perform correction on a range of displacements simultaneously.

29. A system as claimed in claim 23, wherein allowed character strings are words and word parts, or recognised data components and partial data components.

30. A computer program product stored on a computer readable storage medium, comprising computer readable program code means for performing the steps of:

traversing a trie data structure to find approximate partial and full character string matches of the input pattern, wherein traversing a node of the trie data structure to process a character of the string applies any applicable correction rules to the character, wherein each correction rule has an associated cost, adjusted after each character processed;

accumulating costs as a string of characters is gathered; and

restricting the traverse through the trie data structure according to the accumulated cost of a gathered string and potential costs of applicable correction rules.