Sentence reconstruction using word ambiguity resolution

• US 5,960,385 A
• Filed: 05/05/1998
• Issued: 09/28/1999
• Est. Priority Date: 06/30/1995
• Status: Expired due to Fees

• 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: Skiena, Steven S., Rau, Harald
• Primary Examiner(s): Hudspeth, David R.
• Assistant Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US09/073,096
• Time in Patent Office: 511 Days
• Field of Search: 704/1, 704/9, 704/251, 707/530, 707/533
• US Class Current: 704/9
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique

Abstract

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.

Claims

1. A sentence reconstruction method, for resolving word ambiguities in a selected language sentence structure, comprising the steps of:

(a) storing a sentence structure having a sequence of word positions with at least one word position represented by a word group including alternative word choices;

(b) 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;

(c) 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

(d) selecting, by use of said probability values derived in steps (b) and (c), 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 (a) 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.

3. A sentence reconstruction method as in claim 2, wherein said word association techniques comprise one of the following:

phonetic word association, similarly spelled word association, and definitional alternatives of translated words.

4. A sentence reconstruction method as in claim 1, including between steps (a) and (b) 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 (a), 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, wherein in step (c) category (i) includes rules based on transitional probabilities of use of particular word pairs.

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

(y) repeating steps (b) and (c) for any additional word positions having word groups including alternative word choices.

7. A sentence reconstruction method as in claim 1, wherein step (d) comprises selecting words for inclusion in said reconstructed sentence structure based upon the highest relative probability values as derived in step (c).

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

(e) using the words selected in step (d) 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.

9. A sentence reconstruction method as in claim 1, wherein in step (a) said sentence structure is the stored resultant of one of the following (i) computerized storage of spoken words, (ii) typed input subject to transcription errors, (iii) translation of text provided in a first language into a second language, and step (a) additionally includes generating, by computer use of a stored word list, word groups of alternative word choices for particular word positions by use of predetermined word association techniques.

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

phonetic word association, similarly spelled word association, and definitional alternatives of translated words.

11. A sentence reconstruction method, for resolving word ambiguities in a selected language sentence structure, comprising the steps of:

(a) storing a sentence structure having a sequence of word positions including at least one letter for each word position;

(b) accessing a database including a word list to identify for an individual word position a word group including alternative word choices formable using at least one letter included for said word position;

(c) 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 said word position, probability values for word choices for said word position;

(d) 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

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

12. A sentence reconstruction method as in claim 11, wherein step (b) 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.

13. A sentence reconstruction method as in claim 11, including between steps (b) and (c) 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 (b), 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.

14. A sentence reconstruction method as in claim 11, wherein in step (d) category (i) includes rules based on transitional probabilities of use of particular word pairs.

15. A sentence reconstruction method as in claim 11, including between steps (d) and (e) an additional step as follows:

(y) repeating steps (c) and (d) for any additional word positions having word groups including alternative word choices.

16. A sentence reconstruction method as in claim 11, wherein in step (a) said sentence structure is the stored resultant of one of the following (i) computerized storage of spoken words, (ii) typed input subject to transcription errors, (iii) translation of text provided in a first language into a second language, and step (b) additionally includes generating, by computer use of a stored word list, word groups of alternative word choices for particular word positions by use of predetermined word association techniques.

17. A sentence reconstruction method as in claim 16, wherein said word association techniques comprise one of the following:

phonetic word association, similarly spelled word association, and definitional alternatives of translated words.

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

a memory unit arranged to store

a sentence structure having a sequence of word positions each comprising at least one letter;

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 using at least one letter included for each said word position, (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.

19. A sentence reconstruction system as in claim 18, 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.

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