US 7,689,588 B2Granted

Method of syntactic pattern recognition of sequences

Assignee3618633 Canada Inc.

InventorsGhada Badr, John B. Oommen

Life of this patent

Estimating the term…

Loading patent…

Abstract

This invention relates to the Pattern Recognition (PR) of noisy/inexact strings and sequences and particularly to syntactic Pattern Recognition. The present invention presents a process by which a user can recognize an unknown sting X, which is an element of a finite, but possibly larger Dictionary, H, by processing the information contained in its noisy/inexact version, Y, where Y is assumed to contain substitution, insertion or deletion errors. The recognized string, which is the best estimate X+ of X, is defined as that element of H which minimizes the Generalized Levenshtein Distance D(X, Y) between X and Y, for all X<H. Rather than evaluate D(X5Y) for every X<H sequentially, the present invention achieves this simultaneously for every X<H by representing the Dictionary as a Trie, and searching the Trie using a new Al-based search strategy.

Claims14

Dependent claims

(a) Generating a multi-level Trie associated with the set of strings, the Trie having a null level and a null node thereon, and a plurality of data levels having a plurality of data nodes thereon, each data node having a symbol of the alphabet associated therewith;
(b) From the null node, traversing a plurality of levels of the Trie commencing with the first data level adjacent the null node, and thereafter descending level by level within the Trie;
(c) For each data level of the Trie traversed, making a first selection of a set of data nodes from that level, which first selection step includes the steps of:
i. In the case of the first data level of the Trie, selecting all of the data nodes in that level of the Trie;
and
ii. In the case of at least one other data levels of the Trie, for each such level
A. Making a second selection of all of the children of the nodes of the first selection of the level immediately previously traversed;
B. For each of the data nodes selected in step A, calculating a heuristic measurement between the sequence of symbols in the target string and the sequence formed by the symbols on the path from the null node to that selected data node;
and
C. For at least a first symbol represented, selecting a first cluster of nodes representing that first symbol that have the most optimal calculated heuristic measurement associated therewith, up to a bounded number of nodes and identifying the terminal nodes in the first cluster of nodes;
(d) Continuing to traverse the Trie, level by level, repeating step (c) in respect of each level traversed, until step (c) has been completed on that level of the Trie for which there are no children of the selected nodes;
and
(e) In respect of each terminal node identified during the traversal of the plurality of levels of the Trie, comparing the calculated heuristic measurement associated therewith and reporting at least one string from the set of strings associated with the optimal calculated heuristic measurement.

10 more elements

A method executed in a computer system for comparing the similarity of a target string to at least one string in a set of strings, the target string and each string in the set of strings being a sequence of symbols from an alphabet of symbols, and the set of strings being represented in a Trie, the Trie having a null level and a null node thereon, and a plurality of data levels having a plurality of data nodes thereon, each data node having a symbol of the alphabet associated therewith, the method comprising the steps of:

(a) From the null node, traversing a plurality of levels of the Trie commencing with the first data level adjacent the null node, and thereafter descending level by level within the Trie;
(b) For each data level of the Trie traversed, making a first selection of a set of data nodes from that level, which first selection step includes the steps of:
i. In the case of the first data level of the Trie, selecting all of the data nodes in that level of the Trie;
and
ii. In the case of at least one other data levels of the Trie, for each such level
A. Making a second selection of all of the children of the nodes of the first selection of the level immediately previously traversed;
B. For each of the data nodes selected in step A, calculating a heuristic measurement between the sequence of symbols in the target string and the sequence formed by the symbols on the path from the null node to that selected data node;
and
C. For at least a first symbol represented, selecting a first cluster of nodes representing that first symbol that have the most optimal calculated heuristic measurement associated therewith, up to a bounded number of nodes and identifying the terminal nodes in the first cluster of nodes;
(c) Continuing to traverse the Trie, level by level, repeating step (b) in respect of each level traversed, until step (b) has been completed on that level of the Trie for which there are no children of the selected nodes;
and
(d) In respect of each terminal node identified during the traversal of the plurality of levels of the Trie, comparing the calculated heuristic measurement associated therewith and reporting at least one string from the set of strings associated with the optimal calculated heuristic measurement.

9 more elements

Dependencies are inferred from the claim text.