Means for resolving ambiguities in text passed upon character context

• US 5,261,009 A
• Filed: 03/24/1992
• Issued: 11/09/1993
• Est. Priority Date: 10/15/1985
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: The Palantir Corp.
• Inventors: Bokser, Mindy R.
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US07/856,472
• Time in Patent Office: 595 Days
• Field of Search: 382/9, 382/30, 382/34, 382/36-40
• US Class Current: 382/230
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/274 Syntactic or semantic context, e.g. balancing

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. A method as in claim 5 wherein said elements are characters and said selected elements comprise uppercase letters and lowercase letters.

7. 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.

8. A method as in claim 2 wherein each group contains all elements having the property associated with said group.

9. 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.

10. 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.

11. A method as in claim 1 wherein the groups contained in each set of groups collectively contain substantially all of said elements.

12. A method as in claim 11 wherein the number of groups in each set is substantially smaller than the number of said elements.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. A method as in claim 1 wherein said elements are characters.

22. 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.

23. 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.

24. 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.

25. A method as in claim 24 wherein said selected set further comprises one or more nonletter groups.

26. 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.

27. A method as in claim 26 wherein said selected set further comprises one or more nonletter groups.

32. 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.

33. 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.

34. A method as in claim 33 wherein each generic letter dependent group is as large as possible.

35. 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.

36. A method as in claim 35 wherein, for each of selected sets, all other nonletter characters are contained in the generic letter independent group.

38. 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.

39. A method as in claim 33 wherein one of said selected sets includes a group containing all letters.

51. A method as in claim 3 wherein the step of combining the values uses relationships among contextual properties.

52. 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.

53. 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.

28. 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.

29. A method as in claim 28 wherein;

for said selected set, each of said one or more nonletter groups is as large as possible.

30. 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.

31. 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.

37. 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.

40. 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.

41. 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.

42. 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.

43. A method as in claim 42 wherein said step of combining is performed using an Nth order Markov model.

44. 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.

45. 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.

46. 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.

47. 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.

48. 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.

49. 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.

50. A method as in claim 48 wherein a lookup table is used to determine whether the probability of the window of groups is small.