Method for organizing incremental search dictionary

• US 5,671,426 A
• Filed: 06/22/1993
• Issued: 09/23/1997
• Est. Priority Date: 06/22/1993
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: Kurzweil Applied Intelligence, Inc. (Intel Corporation)
• Inventors: Armstrong, John III
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Hughet, William N.
• Application Number:
  US08/080,940
• Time in Patent Office: 1,554 Days
• Field of Search: 364/419.04, 364/419.05, 364/419.11, 364/419.19, 364/419.07, 364/419.12, 364/419.01, 395/751, 395/754, 395/755, 395/760, 395/795
• US Class Current: 704/10
• CPC Class Codes: G06F 16/90348 by searching ordered data, e.g. alpha-numerically ordered data
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms

Abstract

The electronic dictionary disclosed herein is organized for expeditious search based on partial spelling by assigning words to blocks having a predetermined maximum size, the blocks being represented by respective partial spelling sequencer. The words are assigned to blocks by progressing through successive possible sequences in order and, for each sequence, determining the number of words in the set of words corresponding to that sequence. If the number of words is less than the maximum, all of the words in the set are assigned to a corresponding terminal block. Otherwise words up to a preselected number are assigned to a non-terminal block and the partial spelling sequence is extended. As a result of the organization only one call to the dictionary needs to be made for each extension of the sequence.

Claims

1. A method of organizing an electronic dictionary for expeditious search based on partial spelling by assigning words in the dictionary to blocks having a predetermined maximum size, said blocks being represented by respective partial spelling sequences, the assignment to blocks being in accordance with the method which comprises:

progressing through successive possible sequences in character order and, for each such sequence;

determining the number of words in the set of words incorporating the current sequence as initial characters;

if the number of words in the set incorporating the current sequence is less than said maximum size, assigning all of the words in the set to a corresponding terminal block;

otherwise, assigning words in the set up to a preselected number to a corresponding non-terminal block and extending the current sequence,

whereby a user of the dictionary is provided with a listing of candidate words on the basis of a partial spelling which correspondingly identifies a block of words.

2. A method of organizing an electronic dictionary for expeditious search based on partial spelling where a likelihood of occurrence value is associated with each word in the dictionary by assigning words in the dictionary to terminal blocks having a predetermined maximum size and non-terminal blocks comprising a preselected number of words, said blocks being represented by respective partial spelling sequences, the assignment to blocks being in accordance with the method which comprises:

progressing through successive possible sequences in character order and, for each such sequences;

determining the number of words in the set of words incorporating the current sequence as initial characters;

if the number of words in the set incorporating the current sequence is less than said maximum size, assigning all of the words in the set to a corresponding terminal block;

otherwise, assigning the words having the highest likelihood values in the set, up to said preselected number, to a corresponding non-terminal block and extending the current sequence

whereby a user of the dictionary is provided with a listing of candidate words on the basis of a partial spelling which correspondingly identifies a block of words.

3. A method as set forth in claim 2 wherein the words in each terminal block are ordered in accordance with the respective likelihood of occurrence values.

4. A method of organizing an electronic dictionary for expeditious search based on partial spelling where a likelihood of occurrence value is associated with each word in the dictionary by assigning words in the dictionary to terminal blocks having a predetermined maximum size and non-terminal blocks comprising a preselected number of words, and generating a list of partial spelling sequences which represent respective blocks and are associated with pointers which specify the location of the respective blocks, the assignments being in accordance with the method which comprises:

progressing through successive possible sequences in character order and, for each sequence for which there are words in the dictionary;

determining the number of words in the set of words corresponding to that sequence;

if the number of words in the current set is less than said maximum size, assigning all of the words in the set to a corresponding terminal block and putting a corresponding entry into said list;

otherwise, assigning the most likely to occur words in the set up to said preselected number to a corresponding non-terminal block, putting a corresponding entry into said list, and extending the partial spelling sequence

whereby a user of the dictionary can be provided with a listing of candidate words on the basis of a partial spelling which, based on said list, correspondingly identifies a block of words.

5. A method of locating, on the basis of a partial spelling, a desired word in an electronic data-stored dictionary, said method comprising:

providing a collection of stored data blocks containing words from said dictionary, said data blocks being of at least two types;

(A) terminal blocks having a predetermined maximum size and

(B) non-terminal blocks which comprise a preselected number of words,

said blocks being represented by respective unique partial spelling sequences, said terminal blocks comprising all words from the dictionary having the respective partial spelling sequence, said non-terminal blocks comprising said preselected number of words having the respective partial spelling sequence;

providing also an index listing the partial spelling sequences in association with location information for locating the respective stored data block;

using an input partial spelling to access said index thereby to locate a corresponding data block whose partial spelling sequence is the longest which is an initial portion of the input partial spelling.

6. A method of locating, on the basis of a partial spelling, a desired word in an electronic data-stored dictionary, where a likelihood of occurrence value is associated with each word in the dictionary, said method comprising:

providing a collection of stored data blocks containing words from said dictionary, said data blocks being of at least two types;

(A) terminal blocks having a predetermined maximum size and

(B) non-terminal blocks which comprise a preselected number of words,

said blocks being represented by respective partial spelling sequences, said terminal blocks comprising all words from the dictionary having the respective partial spelling sequence, said non-terminal blocks comprising said preselected number of the most likely to occur of the words having the respective partial spelling sequence;

providing also an index listing the partial spelling sequences in association with information for locating the respective stored data block;

using an input partial spelling to locate a corresponding data block whose partial spelling sequence is the longest which is an initial portion of the input partial spelling.

7. A method as set forth in claim 6 wherein the words in said blocks are ordered in accordance with the respective likelihood of occurrence values.

8. A method as set forth in claim 7 further comprising scanning the located block to identify words for which said input partial spelling is a partial spelling sequence.