Means for resolving ambiguities in text based upon character context

• US 4,754,489 A
• Filed: 10/15/1985
• Issued: 06/28/1988
• 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): Boudreau, Leo H.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US06/787,816
• Time in Patent Office: 987 Days
• Field of Search: 364/200, 364/900, 364/513.5, 364/513, 382/1, 382/10, 382/14, 382/15, 382/36, 382/37, 382/38, 382/40, 382/42, 382/51
• 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 processing a reference sequence of occurrences of elements, having an order, comprising the steps of:

assigning each of said elements to a plurality of groups of elements, said groups of elements being formed into a plurality of sets of groups of elements such that an element is assigned to at most one group belonging to a given set, said groups of elements being formed such that all elements contained in a group share a common contextual property such that for each selected set of said plurality of sets of groups, each selected group within said selected set of said plurality of sets of groups is distinguishable from the groups other than said selected group within said selected set of said plurality of sets of groups based on the order of occurrences of elements in said reference sequence of occurrences of elements;

selecting a set of positive integer values;

defining, for each selected set of groups of elements, and for each positive integer value N in said set of positive integer values, an N-gram table, each table containing one or more entries, each entry associated with a specified sequence of N groups of elements contained in said selected set;

examining said reference sequence of occurrences of elements in order to determine the number of occurrences of each of said specified sequence of N groups of elements; and

associating with each entry of each of said N-gram tables a value related to the number of occurrences of the specified sequences of groups of elements associated with said entry.

2. A method as in claim 1 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 contextual property associated with any one of the groups to which it belongs.

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

4. A method as in claim 1 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.

5. A method as in claim 1 wherein each group contains all elements having the contextual property associated with said group.

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

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

8. A method as in claim 1 wherein, for each positive integer value N in said set of positive integer values, and each set of groups of elements, the associated N-gram table contains an entry for each possible sequence of N groups of elements contained in said set.

9. A method as in claim 1 wherein said set of positive integer values contains two consecutive positive integers.

10. A method as in claim 1 wherein said set of positive integer values contains the integers two and three.

11. A method as in claim 1 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 of elements and said second collection of elements.

12. A method as in claim 11 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.

13. A method as in claim 11 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 occurrences of elements in said reference sequence of occurrences of elements.

14. A method as in claim 13 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.

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

16. A method as in claim 15 wherein said characters comprise letters, punctuation, digits, blank, and other nonletters.

17. A method as in claim 16 wherein each of said groups of elements is selected from the types of groups consisting of letter groups and nonletter groups and no group contains both letters and nonletters.

18. A method as in claim 17 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.

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

20. A method as in claim 17 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 groups containing two letters:

a specific lowercase character and its associated uppercase character.

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

22. A method as in claim 17 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 occurrences of elements in said reference sequence of occurrences of elements.

23. A method as in claim 22 wherein, for said selected set, each of said nonletter groups is as large as possible.

24. A method as in claim 22 wherein, for said selected set, the characters in each of said nonletter groups are contextually distinguishable from the characters in other groups of said selected set based on the order of occurrences of elements in said reference sequence of occurrences of elements.

25. A method as in claim 22 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.

26. A method as in claim 18 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, each generic letter group containing two letters:

a specific lowercase character and its associated uppercase character, and nonletter characters in a reference sequence of occurrences of generic letter groups and nonletter characters obtained from said reference sequence of occurrences of elements by replacing each letter in said reference sequence of occurrences of elements with its associated generic letter group than on the order of an uppercase group containing only uppercase letters and a lowercase group containing only lowercase letters and nonletter characters in a reference sequence of occurrences of said uppercase group, said lowercase group, and nonletter characters obtained from said reference sequence of occurrences of elements by replacing each lowercase letter in said reference sequence of occurrences of elements with said lowercase group and each uppercase letter in said reference sequence of occurrences of elements with said uppercase group, and which are not substantially useful in contextually distinguishing among generic letters based on the order of occurrences of generic letter groups and nonletter characters in said reference sequence of occurrences of generic letter groups and nonletter characters.

27. A method as in claim 26 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 occurrences of elements in said reference sequence of occurrences of elements.

28. A method as in claim 27 wherein each generic letter dependent group is as large as possible.

29. A method as in claim 27 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.

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

31. A method as in claim 22 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.

32. A method as in claim 27 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 of characters containing two letters:

a specific lowercase character and its associated uppercase character.

34. A method as in claim 17 wherein:

for a first 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 groups containing two letters;

a specific lowercase character and its associated uppercase character; and

the nonletter groups of said set comprise

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 a reference sequence of occurrences of generic letter groups and nonletter characters obtained from said reference sequence of occurrences of elements by replacing each letter in said reference sequence of occurrences of elements with its associated generic letter group than on the order of an uppercase group containing only uppercase letters and a lowercase group containing only lowercase letters and nonletter characters in a reference sequence of occurrences of said uppercase group, said lowercase group, and nonletter characters obtained from said reference sequence of occurrences of elements by replacing each lowercase letter in said reference sequence of occurrences of elements with said lowercase group and each uppercase letter in said reference sequence of occurrences of elements with said uppercase group, and which are not substantially useful in contextually distinguishing among generic letters based on the order of occurrences of generic letter groups and nonletter characters in said reference sequence of occurrences of generic letter groups and nonletter characters, and

a plurality of generic letter dependent groups such that the characters within a generic letter dependent group are contextually indistinguishable from each other based on the order of occurrences of elements occurring in said reference sequence of occurrences of elements;

for a second 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; and

each nonletter group is a group having the property that characters contained therein are substantially not contextually distinguishable from each other based on the order of occurrences of elements in such reference sequence of occurrences of elements; and

for a third selected set of groups of characters;

the letter groups comprise a letter group containing all letters; and

the nonletter groups comprise a generic letter independent group and a plurality of generic letter dependent groups.

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

35. A method for processing a reference sequence of occurrences of elements comprising the steps of:

assigning each of said elements to one of a plurality of groups of elements, said groups of elements being formed such that all elements contained in a group share a common contextual property, all elements having the contextual property associated with a group are contained in that group, and no element is assigned to more than one group;

selecting a positive integer N;

defining an N-gram table containing one or more entries, each entry associated with a specified sequence of groups of elements;

examining said reference sequence of occurrences of elements in order to determine the number of occurrences of each of said specified sequences of groups of elements; and

associating with each entry of said table a first value indicating there are few occurrences of the specified sequence of groups of elements associated with said entry in the reference sequence of occurrences of elements and otherwise associating a second value.

36. A method as in claim 35 wherein the number of groups is significantly less than the number of elements.

37. A method as in claim 36 wherein said elements are characters.

38. A method as in claim 37 wherein said plurality of groups comprise groups selected from the following groups:

a first group of characters having the property of being uppercase letters,

a second group of characters having the property of being lowercase letters,

a third group containing only the blank character, and

a fourth group containing digits.