Patent ID: 7167588

Claim:
A method for reducing hypothesis exploration in document image decoding incorporating a Stack algorithm comprising: determining whether a first partial path is semantically equivalent to a second partial path, the second partial path having already been processed, wherein the first partial path has a first weight W 1 , and the second partial path has a second weight W 2 ; determining whether the second partial path has been extended further into a Stack graph than the first partial path: and adjusting a queue or discarding one of the first partial path and the second partial path if the first partial path is semantically equivalent to the second partial path by placing the first partial path in a second queue if the second partial path has been extended further into the Stack graph than the first partial path or adding, if the second partial path has been extended and if the first weight W 1 is greater than the second weight W 2 , the first partial path to the first queue.