Method and mechanism for providing partial results in full context handwriting recognition

Abstract

A method and mechanism for displaying partial results of full context handwriting recognition. As handwritten characters are entered into a system, a shape matcher associates the character with a plurality of alternate code points, with each alternate code point having probability information associated therewith. The alternate code points are placed at the end of a queue, and a cost is determined from each alternate code point to any immediately preceding alternate in the queue. The cost is based on the probability information of the alternates and a transition cost therebetween. Then, the lowest cost path back from each of the alternates at the end of the queue to an alternate at the beginning of the queue is determined. If each lowest cost path back converges to a common alternate in the queue, the common alternate and any previous alternates on the path back are recognized as the code points for each of the handwritten characters associated therewith. Because further context cannot affect change the value of these code points, the alternates corresponding to these code points are removed from the queue, and the code points appropriately displayed on a screen as recognized characters, to allow editing thereof. The ability to provide partial results with no loss of accuracy may be extended to include the case where the language model is an arbitrarily complex non-determinsitic state machine including the case where the state machine may be generated from a dictionary.