The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Dec. 09, 2003
Filed:
May. 12, 1999
Walid G. Aref, Monmouth Junction, NJ (US);
Junichi Kanai, East Windsor, NJ (US);
Matsushita Electric Industrial Co., Ltd., Osaka, JP;
Abstract
A method for searching for a query word in a database of automatically recognized text generated, for example by an optical character recognition (OCR) system or a speech recognition (SR) system finds entries that most closely match the query word. The database is indexed into a trie data structure, which represents all possible words in the database. The trie data structure has a plurality of branch nodes, each representing a letter of at least one word, and a plurality of leaf nodes, each representing a respective word. The trie data structure is searched for each query word by selecting the first letter of the query word and also selecting a root node in the trie data structure as the current node. All possible child nodes of the current node are identified. Respective estimated probability values for matching respective letters of the query word with the letters associated with the nodes in the path taken through the trie data structure are calculated for each identified child node. The identified child nodes are then placed into a list of candidate nodes. The node, in the list of candidate nodes, having the highest probability value is selected as the current node and is then deleted from the list of candidate nodes. The process repeats with this current node until a leaf node is reached. When a leaf node is reached, a determination is made whether to store the word into a list of best matches based on the probability value of the word compared to the probability values for all the words in the list of best matches.