US6205428B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Confusion set-base method and apparatus for pruning a predetermined arrangement of indexed identifiers
Assignee: AT&T Inc
•
Filing: 1997-11-20
•
Granted: 2001-03-20
•
Expires: 2017-11-20
Abstract
Abstract A method and apparatus for reducing a set of reference identifiers to a candidate subset of reference identifiers. The reference identifiers are associated in memory with a plurality of index codes. A user provides an input identifier, causing a recognizing device of the present invention to produce a recognized identifier on the basis of the input identifier. The present invention determines an index code based on the recognized identifier and on the basis of a plurality of pre-stored confusion sets of characters that group together in individual confusion sets those characters having a relatively high likelihood of being confused with each other by the recognizing device. After matching the determined index code with one of the reference index codes, the present invention determines which reference index codes are within a predetermined distance of the matched reference index code. The reference identifiers that are associated with these reference index codes constitute the candidate subset of reference identifiers.
Inventors
- 👤 Deborah W. Brown
- 👤 Randy G. Goldberg
- 👤 Piyush C. Modi
- 👤 Richard R. Rosinski
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 16:22
CPC Classifications
G; G10; G10L; G10L17/00; G10L17/06; G10L17/14; G10L17/22; G10L17/24; G10L15/00; G10L15/08; G10L2015/085
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
155 words
A method of matching an input identifier to one of a set of reference identifiers, each of the reference identifiers being associated with one of a plurality of reference index codes, the method comprising the steps of: a) providing a recognized identifier, the input identifier being provided by a user; on the basis of the input identifier; b) determining an index code for the recognized identifier; c) determining which of the plurality of reference index codes are within a predetermined distance of the index code for the recognized identifier; d) accessing the reference identifiers associated with the reference index codes determined in step c), the accessed reference identifiers forming a candidate subset of reference identifiers; e) searching the candidate set of reference identifiers for a reference identifier that matches the recognized identifier; and g) selecting a matching reference identifier as corresponding to the input identifier, wherein each reference identifier is a set of alphanumeric characters.
Claim 2
Independent Claim
155 words
A method of matching an input identifier to one of a set of reference identifiers, each of the reference identifiers being associated with one of a plurality of reference index codes, the method comprising the steps of: a) providing a recognized identifier, the input identifier being provided by a user; on the basis of the input identifier; b) determining an index code for the recognized identifier; c) determining which of the plurality of reference index codes are within a predetermined distance of the index code for the recognized identifier; d) accessing the reference identifiers associated with the reference index codes determined in step c), the accessed reference identifiers forming a candidate subset of reference identifiers; e) searching the candidate set of reference identifiers for a reference identifier that matches the recognized identifier; and g) selecting a matching reference identifier as corresponding to the input identifier, wherein each reference identifier is a set of alphanumeric characters.
Claim 3
Dependent Claim
42 words
The method according to claim 1 , wherein the step b) comprises: i) providing a plurality of confusion sets; and ii) determining the index code for the recognized identifier on the basis of the recognized identifier and the plurality of confusion sets.
Claim 4
Dependent Claim
34 words
The method according to claim 2 , wherein each one of the input identifier, the recognized identifier, and the plurality of reference identifiers comprise at least one character selected from a plurality of characters.
Claim 5
Dependent Claim
105 words
The method according to claim 3 , wherein the step i) comprises: iii) obtaining, for each one of the plurality of characters, a plurality of recognition values, each recognition value representing a likelihood that one of the plurality of characters is recognized as another one of the plurality of characters; and iv) dividing the plurality of characters into a plurality of subsets of characters, each subset of characters including characters having a recognition value of being recognized as another character of the same subset that is higher than a predetermined threshold, wherein each of the confusion sets corresponds to one of the subsets of characters.
Claim 6
Dependent Claim
51 words
The method according to claim 2 , wherein each one of the plurality of reference index codes and the index code for the recognized identifier comprises a plurality of segments, each segment comprising a predetermined number of bits, wherein each segment is associated with one of the plurality of confusion sets.
Claim 7
Dependent Claim
55 words
The method according to claim 5 , wherein the step ii) comprises: iii) determining, for each confusion set, an amount of characters of the confusion set appearing in the recognized identifier; and iv) encoding, for each segment, the amount of characters of the associated confusion set determined in step iii) appearing in the recognized identifier.
Claim 8
Dependent Claim
22 words
The method according to claim 1 , wherein the recognized identifier is entered by the user speaking into a voice input device.
Claim 9
Independent Claim
375 words
A method of matching an input identifier to one of a set of reference identifiers, each of the reference identifiers being associated with one of a plurality of reference index codes, the method comprising the steps of: a) providing a recognized identifier on the basis of the input identifier; b) determining an index code for the recognized identifier; c) determining which of the plurality of reference index codes are within a predetermined distance of the index code for the recognized identifier; d) accessing the reference identifiers associated with the reference index codes determined in step c), the accessed reference identifiers forming a candidate subset of reference identifiers; e) searching the candidate set of reference identifiers for a reference identifier that matches the recognized identifier; and g) selecting a matching reference identifier as corresponding to the input identifier wherein the step c) comprises: i) arranging the reference index codes into a predetermined data structure, wherein the predetermined data structure comprises a plurality of nodes, each node representing at least a portion of at least one of the plurality of reference index codes; ii) traversing the predetermined data structure, wherein moving from any one of the nodes to another node along a first predetermined direction represents a first value, and wherein moving from any one of the nodes to another node along a second predetermined direction represents a second value; iii) calculating a travel path value for each node based on at least one of the first predetermined value and the second predetermined value, each reference index code being associated with a corresponding travel path value; iv) comparing a value of each bit position of each travel path value with a value of each corresponding bit position of the index code for the reference identifier; v) determining for each travel path value an amount of bit positions having a different value than those in corresponding bit positions of the index code for the recognized identifier; and vi) including in a candidate set of reference index codes those reference index codes associated with travel path values for which the associated amount of bit positions having a different value than the corresponding bit positions of the index code for the recognized identifier is no more than the predetermined distance.
Claim 10
Independent Claim
375 words
A method of matching an input identifier to one of a set of reference identifiers, each of the reference identifiers being associated with one of a plurality of reference index codes, the method comprising the steps of: a) providing a recognized identifier on the basis of the input identifier; b) determining an index code for the recognized identifier; c) determining which of the plurality of reference index codes are within a predetermined distance of the index code for the recognized identifier; d) accessing the reference identifiers associated with the reference index codes determined in step c), the accessed reference identifiers forming a candidate subset of reference identifiers; e) searching the candidate set of reference identifiers for a reference identifier that matches the recognized identifier; and g) selecting a matching reference identifier as corresponding to the input identifier wherein the step c) comprises: i) arranging the reference index codes into a predetermined data structure, wherein the predetermined data structure comprises a plurality of nodes, each node representing at least a portion of at least one of the plurality of reference index codes; ii) traversing the predetermined data structure, wherein moving from any one of the nodes to another node along a first predetermined direction represents a first value, and wherein moving from any one of the nodes to another node along a second predetermined direction represents a second value; iii) calculating a travel path value for each node based on at least one of the first predetermined value and the second predetermined value, each reference index code being associated with a corresponding travel path value; iv) comparing a value of each bit position of each travel path value with a value of each corresponding bit position of the index code for the reference identifier; v) determining for each travel path value an amount of bit positions having a different value than those in corresponding bit positions of the index code for the recognized identifier; and vi) including in a candidate set of reference index codes those reference index codes associated with travel path values for which the associated amount of bit positions having a different value than the corresponding bit positions of the index code for the recognized identifier is no more than the predetermined distance.
Claim 11
Dependent Claim
17 words
The method according to claim 8 , wherein the predetermined data structure comprises a tree data structure.
Claim 12
Independent Claim
170 words
An apparatus for matching an input identifier to one of a set of reference identifiers, each of the reference identifiers being associated with one of a plurality of reference index codes, the apparatus comprising: a) first means for providing a recognized identifier on the basis of the input identifier; b) first means for determining an index code for the recognized identifier, the input identifier being provided by a user; c) second means for determining which of the plurality of reference index codes are within a predetermined distance of the index code for the recognized identifier; d) means for accessing the reference identifiers associated with the reference index codes determined by the second means for determining, the accessed reference identifiers forming a candidate subset of reference identifiers; e) means for searching the candidate set of reference identifiers for a reference identifier that matches the recognized identifier; and f) means for selecting a matching reference identifier as corresponding to the input identifier, wherein each reference identifier is a set of alphanumeric characters.
Claim 13
Independent Claim
170 words
An apparatus for matching an input identifier to one of a set of reference identifiers, each of the reference identifiers being associated with one of a plurality of reference index codes, the apparatus comprising: a) first means for providing a recognized identifier on the basis of the input identifier; b) first means for determining an index code for the recognized identifier, the input identifier being provided by a user; c) second means for determining which of the plurality of reference index codes are within a predetermined distance of the index code for the recognized identifier; d) means for accessing the reference identifiers associated with the reference index codes determined by the second means for determining, the accessed reference identifiers forming a candidate subset of reference identifiers; e) means for searching the candidate set of reference identifiers for a reference identifier that matches the recognized identifier; and f) means for selecting a matching reference identifier as corresponding to the input identifier, wherein each reference identifier is a set of alphanumeric characters.
Claim 14
Dependent Claim
49 words
The apparatus according to claim 10 , wherein the first means for determining comprises: i) means for providing a plurality of confusion sets; and ii) third means for determining the index code of the recognized identifier on the basis of the recognized identifier and the plurality of confusion sets.
Claim 15
Dependent Claim
34 words
The apparatus according to claim 11 , wherein each one of the input identifier, the recognized identifier, and the plurality of reference identifiers comprises at least one character selected from a plurality of characters.
Claim 16
Dependent Claim
111 words
The apparatus according to claim 12 , wherein the second means for providing comprises: iii) means for obtaining, for each one of the plurality of characters, a plurality of recognition values, each recognition value representing a likelihood that one of the plurality of characters is recognized as another one of the plurality of characters; and iv) means for dividing the plurality of characters into a plurality of subsets of characters, each subset of characters including characters having a recognition value of being recognized as another character of the same subset that is higher than a predetermined threshold, wherein each of the confusion sets corresponds to one of the subsets of characters.
Claim 17
Dependent Claim
51 words
The apparatus according to claim 11 , wherein each one of the plurality of reference index codes and the index code for the recognized identifier comprises a plurality of segments, each segment comprising a predetermined number of bits, wherein each segment is associated with one of the plurality of confusion sets.
Claim 18
Dependent Claim
66 words
The apparatus according to claim 14 , wherein the third means for determining comprises: iii) fourth means for determining, for each confusion set, an amount of characters of the confusion set appearing in the recognized identifier; and iv) means for encoding, for each segment, the amount of characters of the associated confusion set determined by the third means for determining to appear in the recognized identifier.
Claim 19
Dependent Claim
261 words
The apparatus according to claim 10 , wherein the second means for determining comprises: i) means for arranging the reference index codes into a predetermined data structure, wherein the predetermined data structure comprises a plurality of nodes, each node representing at least a portion of at least one of the plurality of reference index codes; ii) means for traversing the predetermined data structure, wherein moving from any one of the nodes to another node along a first predetermined direction represents a first value, and wherein moving from any one of the nodes to another node along a second predetermined direction represents a second value; iii) means for calculating a travel path value for each node based on at least one of the first predetermined value and the second predetermined value, each reference index code being associated with a corresponding travel path value; iv) means for comparing a value of each bit position of each travel path value with a value of each corresponding bit position of the index code for the reference identifier; v) third means for determining for each travel path value an amount of bit positions having a different value than those in corresponding bit positions of the index code for the recognized identifier; and vi) means for including in a candidate set of reference index codes those reference index codes associated with travel path values for which the associated amount of bit positions having a different value than the corresponding bit positions of the index code for the recognized index code is no more than the predetermined distance.
Claim 20
Dependent Claim
17 words
The apparatus according to claim 16 , wherein the predetermined data structure comprises a tree data structure.
Claim 21
Independent Claim
95 words
An apparatus, comprising: a processing device; a recognizing device coupled to the processing device, the recognizing device including an input for receiving an input identifier, the input identifier being provided by a user; a reference identifier database coupled to the processing device, the reference identifier database including at least one reference identifier, each reference identifier being associated with one of a plurality of reference index codes; an index pruning module coupled to the processing device; a confusion matrix memory coupled to the processing device; and a confusion set generating module coupled to the processing device.
Claim 22
Independent Claim
95 words
An apparatus, comprising: a processing device; a recognizing device coupled to the processing device, the recognizing device including an input for receiving an input identifier, the input identifier being provided by a user; a reference identifier database coupled to the processing device, the reference identifier database including at least one reference identifier, each reference identifier being associated with one of a plurality of reference index codes; an index pruning module coupled to the processing device; a confusion matrix memory coupled to the processing device; and a confusion set generating module coupled to the processing device.
Claim 23
Dependent Claim
27 words
The apparatus according to claim 18 , further comprising: a data input device coupled to the processing device; and a display device coupled to the processing device.
References Cited (Backward Citations)
US3466394A
Cited
US3752904A
Cited
US3896266A
Cited
US3988715A
Cited
US4718102A
Cited
US4908865A
Cited
US4783804A
Cited
US4819271A
Cited
US5769527A
Cited
US4817156A
Cited
US5050215A
Cited
EP0319193A2
Cited
US5034989A
Cited
US5023912A
Cited
US5384833A
Cited
US5101345A
Cited
US5179718A
Cited
US5027406A
Cited
US5216720A
Cited
US5509104A
Cited
US5255310A
Cited
US5167016A
Cited
US5127043A
Cited
US5297194A
Cited
US5303299A
Cited
US5365574A
Cited
US5125022A
Cited
US5517558A
Cited
US5499288A
Cited
US5794042A
Cited
US5418717A
Cited
US5526465A
Cited
US5274560A
Cited
US5748840A
Cited
US5535120A
Cited
US5497319A
Cited
US5465290A
Cited
US5454062A
Cited
US5283833A
Cited
US5875108A
Cited
US5841901A
Cited
US5870492A
Cited
US5502774A
Cited
US5784631A
Cited
US5675704A
Cited
US5452397A
Cited
US5455889A
Cited
US5504805A
Cited
US5677989A
Cited
US5623609A
Cited
US5613109A
Cited
US5566272A
Cited
US5623578A
Cited
US5806040A
Cited
US5577164A
Cited
US5675647A
Cited
US5655058A
Cited
US5642519A
Cited
US5799269A
Cited
US5754695A
Cited
US5745555A
Cited
US5519786A
Cited
US5802205A
Cited
US5680509A
Cited
WO1996010795A1
Cited
US5640490A
Cited
US5729656A
Cited
US5818952A
Cited
US5675706A
Cited
US5677990A
Cited
WO1996036042A1
Cited
US5687287A
Cited
US5680511A
Cited
US5764799A
Cited
US5903864A
Cited
US5781882A
Cited
US5832063A
Cited
US5850480A
Cited
US5797123A
Cited
US5829000A
Cited
US5889897A
Cited
US5937385A
Cited
US5913196A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-03-19 | 2004-09-18 | 2005-03-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-03-19 | 2008-09-18 | 2009-03-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-03-19 | 2012-09-18 | 2013-03-20 | $7700.00 | Window Closed / Lapsed |