Electronic dictionary and method of codifying words therefor

• US 5,297,038 A
• Filed: 01/25/1991
• Issued: 03/22/1994
• Est. Priority Date: 09/27/1985
• Status: Expired due to Term

• Current Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Saito, Keizou
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): CHUNG TRANS, XUONG MY
• Application Number:
  US07/646,358
• Time in Patent Office: 1,152 Days
• Field of Search: 364/419, 400/63
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/90348 by searching ordered data, e.g. alpha-numerically ordered data
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

Even-letter and odd-letter words are separately stored in an electronic dictionary and are codified by using predefined letter weight numbers and position weight numbers corresponding to different letters and letter positions within a word to calculate their hash values. These hash values are arranged sequentially in numerical order and divided into groups according to a predetermined number of higher digits. Numbers of hash values in these groups and the addresses of the first hash values in them are stored. When a letter array is inputted for spell-check, it is codified by the same formula and a corresponding group is identified from its high digits. A sequential comparison is made only with the hash values belonging to this selected group and until the stored hash value in the selected group exceeds the codified number.

Claims

1. A method of using an electronic dictionary, said method comprising the steps of

(a) preliminarily defining letter weight numbers individually corresponding to alphanumeric symbols and position weight numbers individually corresponding to letter positions in any word,

(b) obtaining a word-representing hash value for each of given words to be stored by sequentially calculating letter-representing hash values of individual letters of said each given word from both the letter and position weight numbers respectively corresponding to said individual letters and a predefined divisor and by adding said sequentially calculated letter-representing hash values,

(c) arranging said obtained word-representing hash values sequentially in numerical order separately for even-letter words and odd-letter words,

(d) dividing each of said word-representing hash values into an index section represented by high digits thereof and a data section represented by lower digits thereof,

(e) forming groups of said word-representing hash values according to said index sections separately for even-letter words and odd-letter words,

(f) storing numbers of said word-representing hash values in said groups,

(g) calculating and storing addresses of the first word-representing hash values in said groups.

2. The method of claim 1 wherein said word-representing hash values are N_w -digit numbers where N_w is a plural number and said divisor is a prime number closest to 2**N_w -1.

3. The method of claim 1 wherein

said letter weight numbers and position weight numbers are respectively N_L -digit and N_P -digit numbers where N_L and N_P are plural numbers, and

said letter-representing hash values are calculated by multiplying the first and the second N_L /2 digits of said letter weight number respectively by the first and the second N_P /2 digits of said position weight number, adding the two products together and dividing the sum by said divisor.

4. The method of claim 2 wherein said index section has N_I digits and N_w -N_I =16.

5. The method of claim 1 further comprising the steps of

(h) inputting a letter array for spell check,

(i) obtaining an array-representing hash value corresponding to said letter array as said word-representing hash values are obtained corresponding to said given words as in said Step (b),

(j) selecting a candidate group out of said groups according to higher digits of said array-representing hash value,

(k) retrieving the number of said word-representing hash values and the address of the first of said word-representing hash values in said candidate group, and

(l) sequentially comparing said array-representing hash value with those of said word-representing hash values of said candidate group.

6. The method of claim 5 wherein said Step (1) is stopped when said array-representing hash value becomes greater than the one of said word-representing hash numbers being compared therewith.

7. A word processing system comprising

an electronic dictionary which stores word-representing hash values each corresponding to a word, said electronic dictionary having an even-letter part storing those of said word-representing hash values representing even-letter words and an odd-letter part storing those of said word-representing hash values representing odd-letter words, said word-representing hash values being arranged in numerical order and divided into groups in each of said even-letter and odd-letter parts, first addresses of said word-representing hash values in said groups being stored,

input means for receiving a letter array and determining the number of letters in said letter array,

a letter weight table storing preliminarily defined letter weight numbers individually corresponding to alphanumeric symbols,

a position weight table storing preliminarily defined position weight numbers individually corresponding to letter positions in any word,

retrieving means for sequentially retrieving from said letter and position weight tables one each of said letter and position weight numbers corresponding to each of the letters of said letter array,

calculating means for calculating letter-representing hash values for the letters of said letter array from said letter and position weight numbers retrieved by said retrieving means and by a division by a predefined divisor,

hash-value calculating means for calculating an array-representing hash value corresponding to said letter array by adding said letter-representing hash values obtained by said calculating means, and

control means for selecting one of said groups stored in said electronic dictionary from high digits of said array-representing hash value and determining whether said array-representing hash value coincides with any of said word-presenting hash values in said selected one of said groups in said electronic dictionary.