US5261009A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Means for resolving ambiguities in text passed upon character context
Assignee: Nuance Communications Inc
•
Filing: 1992-03-24
•
Granted: 1993-11-09
•
Expires: 2012-03-24
Abstract
Abstract A method of identifying an object within a set of object candidates includes the steps of: calculating the probability of occurrence of each member of a set of string candidates, wherein each string candidate contains one member of the set of object candidates, the calculating employing formulae using a method of groups and projections; and identifying one of the objects based on the calculated probability.
Inventors
- 👤 Mindy R. Bokser
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:34
CPC Classifications
G; G06; G06V; G06V30/00; G06V30/10; G06V30/26; G06V30/262; G06V30/274
Claims Analysis
Total Claims: 55
Claim 1
Independent Claim
191 words
A method for determining a value related to the probability of occurrence, within a reference sequence of occurrences of elements, of an input window of N element candidates, comprising the steps of: predefining a plurality of sets of groups of elements, wherein each group is defined by an element property and contains exactly those elements which share said element property, and wherein, for each set, an element has at most one of the element properties associated with said set, and therefore no two groups within the same set share any elements in common; associating each element candidate in the input window to one group within each set of groups based on the properties of said element candidate, thereby forming, for each set of groups, an associated window of N groups; for each set of groups, determining a value related to the probability of occurrence of the associated window of groups in said reference sequence; and computing said value related to the probability of occurrence of said input window by combining the values related to the probability of occurrence of each of said windows of groups to obtain an aggregate window value.
Claim 2
Independent Claim
191 words
A method for determining a value related to the probability of occurrence, within a reference sequence of occurrences of elements, of an input window of N element candidates, comprising the steps of: predefining a plurality of sets of groups of elements, wherein each group is defined by an element property and contains exactly those elements which share said element property, and wherein, for each set, an element has at most one of the element properties associated with said set, and therefore no two groups within the same set share any elements in common; associating each element candidate in the input window to one group within each set of groups based on the properties of said element candidate, thereby forming, for each set of groups, an associated window of N groups; for each set of groups, determining a value related to the probability of occurrence of the associated window of groups in said reference sequence; and computing said value related to the probability of occurrence of said input window by combining the values related to the probability of occurrence of each of said windows of groups to obtain an aggregate window value.
Claim 3
Dependent Claim
27 words
A method as in claim 1 wherein each of said groups is associated with a property such that all elements contained in said group share said property.
Claim 4
Dependent Claim
49 words
A method as in claim 2 wherein the property associated with each of a plurality of groups is a contextual property such that for each group within a set is distinguishable from the other groups within said set based on the order of elements occurring in said reference sequence.
Claim 5
Dependent Claim
45 words
A method as in claim 2 wherein the property associated with each group is a contextual property such that for each group within a set is distinguishable from the other groups within said set based on the order of elements occurring in said reference sequence.
Claim 6
Dependent Claim
47 words
A method as in claim 3 wherein selected elements are uniquely specified by the conjunction of the contextual properties associated with the groups to which each such element belongs though not uniquely specified by the property associated with any one of the groups to which is belongs.
Claim 7
Dependent Claim
21 words
A method as in claim 5 wherein said elements are characters and said selected elements comprise uppercase letters and lowercase letters.
Claim 8
Dependent Claim
35 words
A method as in claim 3 wherein each element which is contextually distinguishable from all other elements is uniquely specified by the conjunction of the contextual properties associated with the groups to which it belongs.
Claim 9
Dependent Claim
19 words
A method as in claim 2 wherein each group contains all elements having the property associated with said group.
Claim 10
Dependent Claim
92 words
A method as in claim 2 wherein said step of computing a value related to the probability of occurrence of said input window of element candidates further comprises the steps of: determining an aggregate unigram value related to the probability of occurrence of those elements in the input window which are not uniquely specified by the conjunction of the properties of the groups to which they belong; and combining said aggregate unigram value with said aggregate window value to obtain said value related to the probability of occurrence of said input window.
Claim 11
Dependent Claim
110 words
A method as in claim 9 wherein said aggregate unigram value is determined by the steps of: for each element candidate in said input window which is not uniquely specified by the conjunction of the properties of the groups to which they belong determining a first associated value related to the probability of occurrence of said element candidate in said reference string; determining a second associated value related to the probability of occurrence in said reference string of a selected group containing said element candidate; forming a value related to the ratio of said first and second associated values; and combining said values related to obtain said aggregate unigram value.
Claim 12
Dependent Claim
22 words
A method as in claim 1 wherein the groups contained in each set of groups collectively contain substantially all of said elements.
Claim 13
Dependent Claim
23 words
A method as in claim 11 wherein the number of groups in each set is substantially smaller than the number of said elements.
Claim 14
Dependent Claim
71 words
A method as in claim 1 wherein said input window comprises N element candidates and for each set of groups said step of determining a value related to the probability of occurrence of its associated window of groups comprises the steps of: retrieving a value from a precalculated N-gram table associated with said set, said N-gram table containing one or more entries, each entry associated with a specific sequence of groups.
Claim 15
Dependent Claim
33 words
A method as in claim 13 wherein each precalculated N-gram table associated with a set of groups contains an entry for each possible sequence of N groups of elements contained in said set.
Claim 16
Dependent Claim
38 words
A method as in claim 3 wherein said elements are partitioned into a first collection of elements and a second collection of elements and wherein no group contains elements from both said first collection and said second collection.
Claim 17
Dependent Claim
39 words
A method as in claim 15 wherein, for one or more selected sets, each member of said second collection of elements is unambiguously specified by the conjunction of properties of the groups containing said elements in said selected sets.
Claim 18
Dependent Claim
56 words
A method as in claim 15 wherein, for a selected set, each member of said first collection of elements is assigned to a group in said selected set, having the property that its elements are substantially not distinguishable from each other based on the order of elements occurring in said reference sequence of occurrences of elements.
Claim 19
Dependent Claim
39 words
A method as in claim 16 wherein for one or more selected sets, each member of said second collection of elements is unambiguously specified by the conjunction of properties of the groups containing said elements in said selected areas.
Claim 20
Dependent Claim
81 words
A method as in claim 18 wherein said step of computing a value related to the probability of occurrence of said input window of element candidates further comprises the steps of: determining an aggregate unigram value related to the probability of occurrence of those elements in the input window which are members of said first collection; and combining said aggregate unigram value with said aggregate window value to obtain said value related to the probability of occurrence of said input window.
Claim 21
Dependent Claim
100 words
A method as in claim 19 wherein said aggregate unigram value is determined by the steps of: for each element candidate in said input window which is a member of said first collection: determining a first associated value related to the probability of occurrence of said element candidate in said reference string; determining a second associated value related to the probability of occurrence in said reference string of a selected group containing said element candidate; and forming a value related to the ratio of said first and second associated values; and combining said values to obtain said aggregate unigram value.
Claim 22
Dependent Claim
11 words
A method as in claim 1 wherein said elements are characters.
Claim 23
Dependent Claim
26 words
A method as in claim 21 wherein said characters comprise characters selected from the types of characters consisting of letters, punctuation, digits, blank, and other nonletters.
Claim 24
Dependent Claim
26 words
A method as in claim 22 wherein said groups comprise groups selected from letter groups and nonletter groups and no group contains both letters and nonletters.
Claim 25
Dependent Claim
44 words
A method as in claim 23 wherein for a selected set of groups of characters the letter groups comprise a first group of characters having the property of being uppercase letters and a second group of characters having the property of being lowercase letters.
Claim 26
Dependent Claim
17 words
A method as in claim 24 wherein said selected set further comprises one or more nonletter groups.
Claim 27
Dependent Claim
47 words
A method as in claim 23 wherein for a selected set of groups of characters, the letter groups comprise a plurality of generic letter groups of characters, each of said plurality of generic letter group containing two letters: a specific lowercase character and its associated uppercase character.
Claim 28
Dependent Claim
17 words
A method as in claim 26 wherein said selected set further comprises one or more nonletter groups.
Claim 29
Dependent Claim
47 words
A method as in claim 60 wherein, for a selected set of groups of characters, each nonletter group has the property that the characters contained in said group are substantially not contextually distinguishable from each other based on the order of characters occurring in said reference sequence.
Claim 30
Dependent Claim
24 words
A method as in claim 28 wherein; for said selected set, each of said one or more nonletter groups is as large as possible.
Claim 31
Dependent Claim
46 words
A method as in claim 28 wherein, for said selected set, the characters in each of said one or more nonletter groups are contextually distinguishable from the characters in other groups of said selected set based on the order of characters occurring in said reference sequence.
Claim 32
Dependent Claim
69 words
A method as in claim 28 wherein, for said selected set, the nonletter groups comprise one or more of the following groups: a first group containing the blank character; a second group containing the apostrophe character; a third group containing digit characters; a fourth group containing arithmetic symbols; a fifth group containing sentence-ending punctuation; a sixth group containing currency prefix characters; and a seventh group containing currency suffix characters.
Claim 33
Dependent Claim
97 words
A method as in claim 23 wherein, for each of one or more selected sets of groups of characters, one nonletter group is a generic letter independent group which contains all and only nonletters which are not substantially more contextually distinguishable from other characters based on the order of generic letter groups and nonletter characters in the reference sequence than on the order of uppercase and lowercase groups and nonletter characters in the reference sequence and which are not substantially useful in contextually distinguishing among generic letters based on the order of characters in said reference sequence.
Claim 34
Dependent Claim
71 words
A method as in claim 32 wherein, for each of said one or more selected sets of groups of characters, each nonletter which is not a member of the generic letter independent group is assigned to a generic letter dependent group in such a way that the characters within a generic letter dependent group are contextually indistinguishable from each other based on the order of characters occurring in said reference sequence.
Claim 35
Dependent Claim
17 words
A method as in claim 33 wherein each generic letter dependent group is as large as possible.
Claim 36
Dependent Claim
47 words
A method as in claim 33 wherein, for each of said selected sets, the generic letter dependent groups comprise one or both of the following groups: a first generic letter dependent group containing the blank character; and a second generic letter dependent group containing the apostrophe character.
Claim 37
Dependent Claim
24 words
A method as in claim 35 wherein, for each of selected sets, all other nonletter characters are contained in the generic letter independent group.
Claim 38
Dependent Claim
34 words
A method as in claim 28 wherein the letter groups of said selected set comprise a first group containing all and only uppercase letters and a second group containing all and only lowercase letters.
Claim 39
Dependent Claim
43 words
A method as in claim 33 wherein the letter groups of one of said selected sets comprise one or more generic letter groups of characters, each of said generic letter groups containing two letters: a specific lowercase character and its associated uppercase character.
Claim 40
Dependent Claim
18 words
A method as in claim 33 wherein one of said selected sets includes a group containing all letters.
Claim 41
Independent Claim
184 words
A method for determining a value related to the probability of occurrence, within a reference sequence of occurrences of elements, of an input window of N element candidates comprising the steps of: predefining a plurality of sets of groups of elements, wherein each group is defined by an element property and contains exactly those elements which share said element property, and wherein, for each set, an element has at most one of the element properties associated with said set, and therefore no two groups within the same set share any elements in common; associating each element candidate in the input window to one group within each set of groups based on the properties of said element candidate, thereby forming, for each set of groups, an associated window of N groups; determining a value related to the probability of occurrence of the associated window of groups in said reference sequence; and computing said value related to the probability of occurrence of said input window by combining said window value with an aggregate unigram value related to the probability of each element in the input window.
Claim 42
Independent Claim
184 words
A method for determining a value related to the probability of occurrence, within a reference sequence of occurrences of elements, of an input window of N element candidates comprising the steps of: predefining a plurality of sets of groups of elements, wherein each group is defined by an element property and contains exactly those elements which share said element property, and wherein, for each set, an element has at most one of the element properties associated with said set, and therefore no two groups within the same set share any elements in common; associating each element candidate in the input window to one group within each set of groups based on the properties of said element candidate, thereby forming, for each set of groups, an associated window of N groups; determining a value related to the probability of occurrence of the associated window of groups in said reference sequence; and computing said value related to the probability of occurrence of said input window by combining said window value with an aggregate unigram value related to the probability of each element in the input window.
Claim 43
Dependent Claim
89 words
A method as in claim 40 wherein said aggregate unigram value is determined by the steps of: for each element candidate in said input window: determining a first associated value related to the probability of occurrence of said element candidate in said reference string; determining a second associated value related to the probability of occurrence of its associated group in said reference string; and forming a value related to the ratio of said first and second associated values; and combining said values related to obtain said aggregate unigram value.
Claim 44
Dependent Claim
97 words
A method as in claim 41 wherein said input window of element candidates is one of a plurality of input windows of element candidates obtained by dividing an input string of M element candidates into overlapping windows of length N and N-1, where N is an integer less than M and wherein said step of calculating a value related to the probability of occurrence of each of said input windows is followed by the step of combining said values to obtain a value related to the probability of occurrence of said input string within said reference string.
Claim 45
Dependent Claim
19 words
A method as in claim 42 wherein said step of combining is performed using an Nth order Markov model.
Claim 46
Dependent Claim
41 words
A method as in claim 42 wherein each element candidate of said input string has an associated prior probability value and wherein the value related to the probability of occurrence of said input string is combined with said prior probability associated.
Claim 47
Dependent Claim
56 words
A method as in claim 42 wherein said input string is one of a plurality of input strings and said step of computing a value related to the probability of occurrence of each of said input strings is followed by the step of selected for output that string of element candidates having the highest computed probability.
Claim 48
Dependent Claim
60 words
A method as in claim 45 wherein, if after said first calculation, the probability of occurrence of each input string is zero, the probability of each string is recalculated a second time using fewer sets of groups than were used in said first calculation and the input string with the highest probability after the second calculation is selected for output.
Claim 49
Dependent Claim
35 words
A method as in claim 46 which further includes the step of, prior to the step of computing the probability of each input string, eliminating from contention those input strings which contain highly unlikely substrings.
Claim 50
Dependent Claim
79 words
A method as in claim 47 wherein said step of eliminating comprises the steps of: for each input string, dividing said input string into overlapping windows of element candidates length N; and for each window of element candidates, assigning each element candidate to one of a plurality of groups of elements thereby creating a window of groups and then eliminating said string of element candidates from contention if its probability of occurrence in said reference string is very small.
Claim 51
Dependent Claim
38 words
A method as in claim 47 wherein the step of eliminating further comprises the step of checking to see whether all input strings have been eliminated and, if so, again considering those input strings which have been eliminated.
Claim 52
Dependent Claim
24 words
A method as in claim 48 wherein a lookup table is used to determine whether the probability of the window of groups is small.
Claim 53
Dependent Claim
18 words
A method as in claim 3 wherein the step of combining the values uses relationships among contextual properties.
Claim 54
Dependent Claim
34 words
A method as in claim 1 wherein said selected group has the property that its elements are substantially not distinguishable from each other based on the order of elements occurring in said reference sequence.
Claim 55
Dependent Claim
34 words
A method as in claim 20 wherein said selected group has the property that its elements are substantially not distinguishable from each other based on the order of elements occurring in said reference sequence.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-11-08 | 1997-05-10 | 1997-11-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-11-08 | 2001-05-10 | 2001-11-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-11-08 | 2005-05-10 | 2005-11-09 | $7700.00 | Window Closed / Lapsed |