METHOD AND SYSTEM FOR APPROXIMATE STRING MATCHING

摘要

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 (211) to find approximate partial and full character string matches (203) of the input pattern (201). Traversing a node of the trie data structure (211) to process a character of the string applies any applicable correction rules (213) to the character, wherein each correction rule (213) 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 (211) according to the accumulated cost of a gathered string and the potential costs of applicable correction rules.