Device and method for the storage and retrieval of inflection information for electronic reference products

• US 5,229,936 A
• Filed: 01/04/1991
• Issued: 07/20/1993
• Est. Priority Date: 01/04/1991
• Status: Expired due to Term

• Current Assignee: FEP Holding Company
• Original Assignee: Franklin Electronic Publishers Incorporated (Saunders Acquisition Corp.)
• Inventors: Oswalt, Edward, Decker, Joseph E., Justice, David
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): Bodendorf, A.
• Application Number:
  US07/638,067
• Time in Patent Office: 928 Days
• Field of Search: 364/419, 364/900
• US Class Current: 704/10
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique

Abstract

A method and apparatus stores and retrieves inflected forms of words in electronic reference products and, in particular, in electronic dictionaries, electronic bilingual dictionaries, electronic thesauri and an electronic Bible. The method is for providing inflection information related to a given word in an electronic reference device having a memory portion comprises the steps of providing information representing all of the forms of a word whose inflections are to be considered, forming information representing as stem of the word consisting of the longest prefix that is the same in all of the forms of the word, forming information representing a list of all of the allowed endings, designated as ending sets, of the forms of the word, assigning a unique number to each ending set, storing information representing the stem portion of the word in a memory arranged in a predetermined manner, and storing information representing a sequence of characters in a memory portion corresponding to each ending set number followed by a termination character. The sequence includes characters used to specify the part of speech and grammatical information.

Claims

1. A method for providing inflection information related to a given word in an electronic reference device having a memory portion comprising the steps of:

providing information representing all inflected forms of a word which are to be considered, said inflected forms including allowed endings of said word;

forming information representing a stem portion of said word consisting of a prefix which is longest and is the same in all of said inflected forms of the word;

forming information representing a list of all allowed endings, designated as ending sets, of said inflected forms of the word;

assigning a unique number to each ending set;

storing information representing said stem portion of the word in a memory portion arranged in a predetermined manner; and

storing information representing a sequence of characters in a memory portion corresponding to each ending set number followed by a termination character, said sequence including characters used to specify the part of speech and grammatical information.

2. The method of claim 1 wherein the part of speech and grammatical information portion of the stored sequence of characters is encoded by standard computer code.

3. The method of claim 1 wherein the part of speech and grammatical information is encoded by use of symbols representing an address of such information stored in another portion of the memory of the device.

4. The method of claim 1 wherein the part of speech and grammatical information is encoded as an index in a table of such information.

5. The method of claim 1 including the step of storing the sequence of characters in a predetermined order.

6. The method of claim 1 including wherein the sequence uses a separator character between the part of speech and grammatical information.

7. The method of claim 1 wherein said stored sequence includes a character for signifying that no such form of a word exists.

8. The method of claim 1 including repeating said sequence of steps for a multiplicity of words in a first language and a multiplicity of words in a second language.

9. The method of claim 1 including the step of using said stored information for providing inflection information for a given word.

10. The method of claim 8 including using said stored information for providing inflection information for a given word in said first language and in said second language.

11. The method of claim 1 wherein the predetermined manner of the arrangement for storing information representing the stem portion of a word is in a form of a directed acyclic word graph (DAWG).

12. The method of claim 11 including using said stored information for providing inflection information by first performing a depth-first search of the DAWG to determine whether a given path string of letter information is in the DAWG.

13. The method of claim 11 including using said stored information for providing inflection information by first performing a depth-first search of the DAWG to determine whether a given word is in the DAWG.

14. In a method of storage of separately encoded streams of Huffman symbols, the improvement comprising the step of merging elements of said separate streams into a single stream having a certain order in which said order of said symbols depends on a logical order in which said symbols, when decoded, are to be displayed.

15. The method of claim 14 also including the step of decoding the merged stream wherein an appropriate table for decoding a given symbol is determined from a context of the given symbol as encoded.

16. The method of claim 14 wherein one of the separately encoded streams of symbols is a stream of numbers representing stems of words and another separately encoded stream is a stream of numbers representing the ending of these words.

17. The method of claim 14 including an encoded stream representing formatting and/or syntactic information.

18. An electronic reference device for providing inflection information related to a given word comprising:

means for providing information signals representing all inflected forms of a word which are to be considered, said inflected forms including allowed endings of said word;

means for forming information signals representing a stem portion of said word consisting of a prefix which is longest and is the same in all of said forms of the word;

means for forming information signals representing a list of all allowed endings, designated as ending sets, of said forms of the word;

means for assigning a signal representing a unique number to each ending set;

means for storing information signals representing the stem portion of the word in a memory portion arranged in a predetermined manner; and

means, responsive to said assigning means, for storing information signals representing a sequence of characters in a memory portion corresponding to each ending set number followed by a termination character, said sequence including characters used to specify the part of speech and grammatical information.