Trie based method for indexing handwritten databases

摘要

A method is disclosed for matching input data representing a continuous combination of input objects to a plurality of objects in a trie database structure. This data structure has a plurality of nodes partitioned into a plurality of levels. Each node in the Trie includes a plurality of elements where each element corresponds to a respective one of the component objects. In addition, a hidden Markov model corresponding to the component object is associated with the element in the database. According to the method, the input object is applied to each of the hidden Markov models associated with the respective plurality of elements of a node to generate a respective plurality of acceptance values. The element which generates the largest acceptance value is identified with a segment of the input data. The component object for this element is recorded and the identified segment is deleted from the input data string. These steps are repeated at successive levels of the Trie data structure until each segment of the input data has been identified with an element of a node of the Trie data structure. The input data is matched with the objects stored in the database by concatenating the component objects associated with the respective identified elements.