Recognition of sequential data using finite state sequence models

Abstract

In a method of automatically recognizing data which comprises sequential data units represented as sequential tokens grouped into one or more items, known items are stored as respective finite state sequence models. Each state corresponds to a token and the models which have common prefix states are organized in a tree structure such that suffix states comprise branches from common prefix states and there are a plurality of tree structures each having a different prefix state. Each sequential data unit is compared with stored reference data units identified by reference tokens to generate scores indicating the similarity of the data units to reference data units. An accumulated score for the final state in the models is determined by steps of (a) sequentially calculating the accumulated score for a model to reach the final state comprising a leaf in the tree, (b) identifying the closest branch to the leaf corresponding to a next model for which an accumulated score for the final stage has not yet been calculated, and (c) accumulating the score from the identified closest branch for the next model to the final state. These steps are repeated for the branches of the trees. The item corresponding to a model having the highest accumulated score is recognized as the model best matching the data.