Compact high speed hashed array for dictionary storage and lookup

• US 4,503,514 A
• Filed: 12/29/1981
• Issued: 03/05/1985
• Est. Priority Date: 12/29/1981
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Urquhart, Robert J.
• Primary Examiner(s): Thomas, James D.
• Assistant Examiner(s): Eng, David Y.
• Application Number:
  US06/335,478
• Time in Patent Office: 1,162 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/737, 364/300, 371/2, 371/25, 371/26, 371/51, 371/54
• US Class Current: 715/202
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

An improved method for storing and rapidly accessing a dictionary file of encoded data for use in verifying the correct spelling of input words. Dictionary words are numerically encoded and hashed into magnitude and unique angle pairs. The hashed pairs are sorted and the magnitudes are mapped into a pointer bit vector containing a binary representation for each possible magnitude value and a binary representation for each actual magnitude value. The pointer bit vector is coordinated with the angle values which are stored as is. The spelling of input words is checked by hashing the input word and using the magnitude as an access to the pointer bit vector which yields pointers to all angles having the same magnitude as the input word. These angles are compared to the angle calculated for the input word and an indicator produced to show the result of the comparison and thereby whether the input word is correctly spelled.

Claims

1. A control system for controlling a text processing machine to verify the presence of an input character string in a dictionary of character strings comprising:

means for calculating a magnitude and angle representation for each of N dictionary character strings;

means for sorting said magnitude and angle representations into numerical order;

a memory buffer of 2N bit locations;

means for activating a binary bit of a first polarity in said memory buffer for each of the possible N magnitude representations;

means for calculating a modulo N value for each of the N magnitude representations;

means for activating a binary bit of a second polarity opposite said first polarity in said memory buffer adjacent each binary bit of said first polarity for each modulo N value calculated;

means for storing said angle representations corresponding to said calculated modulo N values;

means for receiving an input character string and calculating a magnitude and angle representation for said input character string;

means for calculating the modulo N value of the magnitude representation of said input character string;

means for scanning said memory buffer for binary bits of said second polarity adjacent said binary bit of said first polarity representing the modulo N value of the input character string magnitude representation;

means for synchronously scanning the corresponding angle representations;

means for comparing all angle representations corresponding to the binary bit of said second polarity adjacent the binary bit of said first polarity corresponding to the modulo N value of the input word to the input word angle representation; and

means for outputting a signal indicating whether the compare is equal or not equal.

2. The control system of claim 1 wherein said means for activating a binary bit of a first polarity activates a binary 0 and said means for activating a binary bit of a second polarity activates a binary 1.

3. The control system of claim 9 or claim 2 wherein said means for activating a binary bit of a second polarity includes means for calculating a table of address points for said memory buffer based on the relative positioning of said binary signals of second polarity in said memory buffer and means for storing said table of address points.

4. The control system of claim 3 wherein said means for calculating the modulo N value of the magnitude representation of said input character string includes means for accessing said table of address points for the memory buffer address nearest said calculated modulo N value for the input character string.