Sentence reconstruction using word ambiguity resolution

• US 5,828,991 A
• Filed: 06/30/1995
• Issued: 10/27/1998
• Est. Priority Date: 06/30/1995
• Status: Expired due to Term

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Rau, Harald, Skiena, Steven S.
• Primary Examiner(s): Weinhardt, Robert A.
• Application Number:
  US08/497,149
• Time in Patent Office: 1,215 Days
• Field of Search: 395/751, 395/759, 395/2.66, 395/2.8, 379/52, 379/93, 379/96, 379/97, 379/93.27, 340/825.19, 704/1, 704/9, 704/251, 704/271
• US Class Current: 704/9
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique

Abstract

Single stroke text entry via a telephone keypad is subject to ambiguities resulting from the overloading of three letters on one key. After text is entered the three letter per position code block represented by the key strokes for a word position is hashed to all matches in a stored dictionary type word list. The resulting word group of alternative word choices for that word position is subjected to probability analysis. Probabilities of usage of specific words are evaluated based on frequency of usage in the selected language, such as English. Syntax type probabilities of word sequencing are evaluated through (i) rules based on transitional probability of use of two particular words in sequence in English usage and (ii) rules based on probability of relative positioning of words of particular word categories (e.g., nouns and adjectives) in a sentence structure in English usage. A word trellis or lattice represents choice paths for alternative sentence structures. By selecting the path with the highest probability values, highly accurate sentence reconstruction is provided. Communication with hearing impaired persons via any telephone keypad is facilitated by described systems and methods also applicable to a variety of systems wherein computer stored text is subject to ambiguities as to intended words.

Claims

1. A sentence reconstruction method, for resolving word ambiguities in a selected language sentence structure entered using single stroke activation of a key set including text entry keys each representing a group of letters, comprising the steps of:

(a) providing first key stroke indicia each ambiguously representing a letter of a group of letters and second key stroke indicia including indicia representing spaces between words;

(b) partitioning, by use of said second key stroke indicia, said first key stroke indicia into a sequence of word positions, each word position comprising a code block represented by at least one of said first key stroke indicia;

(c) accessing a database including a word list to identify for an individual word position a word group including alternative word choices formable from the letter groups represented by the code block for said word position;

(d) repeating step (c) for said sequence of word positions to identify a corresponding word group including at least one word choice for each of a plurality of word positions;

(e) utilizing a stored word use rule set representative of relative frequency of particular word usage in said selected language to derive, for the word group for one of said word positions, probability values for word choices for said word position;

(f) utilizing a stored language rule set representative of usage in said selected language to derive probability values for a sequencing of individual word choices for said word position relative to at least one word choice for an adjacent word position in said sentence structure, said language rule set including rules in both of the following categories (i) rules based on transitional probability of use of particular word sequences, and (ii) rules based on probability of relative positioning of words of particular word categories in a sentence structure;

(g) repeating steps (e) and (f) for any additional word positions having an associated word group including a plurality of alternative word choices; and

(h) selecting, by use of said probability values derived in steps (e) and (f), one word from each said word group for inclusion at a respective word position in a reconstructed sentence structure.

2. A sentence reconstruction method as in claim 1, wherein step (h) comprises selecting words for inclusion in said reconstructed sentence structure based upon the highest relative probability values as derived in steps (e) and (f).

3. A sentence reconstruction method as in claim 1, wherein in step (a) said second key stroke indicia additionally include indicia representing a period delimiting said sentence structure and step (b) additionally includes partitioning said word positions into at least one sentence.

4. A sentence reconstruction method as in claim 1, including between steps (c) and (d) an additional step as follows:

(x) for each word position for which no word group including at least one word choice is identified in step (c), utilizing a stored word assembler unit to attempt to identify at least one of a suffix construction, a prefix construction and a combination word construction, and to thereby identify a word group including at least one word choice for said word position.

5. A sentence reconstruction method as in claim 1, additionally including the following step:

(j) using the words selected in step (h) to provide a representation of the reconstructed sentence structure in at least one of the following forms;

a viewable display, a printout, a synthesized speech output.

6. A sentence reconstruction method as in claim 1, wherein step (f) comprises utilizing a stored language rule set including rules in both of said categories (i) and (ii), and category (i) includes rules based on transitional probabilities of use of particular word pairs.

7. A sentence reconstruction method as in claim 1, wherein step (a) comprises providing said first and second key stroke indicia by activation of a telephone type keypad.

8. A sentence reconstruction method as in claim 1, wherein step (c) comprises accessing a database including a word list including word groups of alternative word choices for particular word positions generated by use of predetermined word association techniques.

9. A sentence reconstruction method as in claim 8, wherein said word association techniques comprise one of the following;

multiple letter key code set word alternatives, phonetic word association, similarly spelled word association, and definitional alternatives of translated words.

10. A sentence reconstruction method wherein text in a selected language is entered by key stokes each ambiguously representing one letter of a group of letters, key stroke indicia are partitioned into a sequence of word positions each represented by a code block, and a code block is used to identify a word group of one or more word choices formable from letter groups represented by the respective code block, to thereby provide a sequence of word groups representing an input sentence structure, said method characterized by the steps of:

(a) utilizing a stored word use rule set representative of relative frequency of particular word usage in said selected language to derive, for the word group for one of said word positions, values for word choices for said word position;

(b) utilizing a stored language rule set representative of usage in said selected language to derive probability values for sequencing of individual word choices for said word position relative to at least one word choice for an adjacent word position in said sentence structure, said language rule set including rules in both of the following categories (i) rules based on transitional probability of use of particular word sequences, and (ii) rules based on probability of relative positioning of words of particular word categories in a sentence structure; and

(c) selecting, by use of said probability values derived in steps (a) and (b), one word from each said word group for inclusion at a respective word position in a reconstructed sentence structure.

11. A sentence reconstruction method as in claim 10, additionally including the following step:

(d) using words selected in step (c) to provide a representation of the reconstructed sentence structure in at least one of the following forms;

a viewable display, a printout, and a synthesized speech output.

12. A sentence reconstruction system to resolve word ambiguities in a selected language sentence structure comprising:

an input terminal for coupling of key activation indicia from a key set including keys each representing a group of letters;

a memory unit arranged to store

a sentence structure having a sequence of word positions each comprising a code block represented by at least one indicia ambiguously representing one letter of a group of letters;

a word list of words of said selected language;

a word use rule set representative of frequency of particular word usage in said selected language; and

a language rule set including rules in both of the following categories (i) rules based on transitional probability of use of particular word sequences, and (ii) rules based on probability of relative positioning of particular word categories in a sentence structure;

a processor arranged to (i) use said word list to identify, for said sequence of word positions, word groups including alternative word choices formable from letter groups represented by said indicia, (ii) use said word use rule set to derive probability values for word choices for the word group for each said word position, and (iii) use both categories of rules of said language rule set to derive probability values for sequencing of individual word choices for individual word positions relative to at least one word choice for an adjacent word position in said sentence structure, and to select, by use of said probability values, one word from each said word group for inclusion at a respective word position in a reconstructed sentence structure; and

an output device arranged to provide a representation of said reconstructed sentence structure.

13. A sentence reconstruction system as in claim 12, wherein said memory unit is arranged to store said language rule set including rules in both of said categories (i) and (ii), and category (i) includes rules based on transitional probabilities of use of particular word pairs.

14. A sentence reconstruction system as in claim 12, wherein said key activation indicia are produced by use of a telephone type keypad.

15. A sentence reconstruction system as in claim 12, wherein said output device provides said representation in the form of at least one of a viewable display, a printout, and synthesized speech.