초록 ▼

A machine-implemented process, and apparatus, for performing a set membership test on large sets through the technique of binary hash coding with a known allowable expectation of an error. The present invention does not employ content addressable memory; rather, the present invention performs set me

A machine-implemented process, and apparatus, for performing a set membership test on large sets through the technique of binary hash coding with a known allowable expectation of an error. The present invention does not employ content addressable memory; rather, the present invention performs set membership testing by utilizing a hash function, which produces a randomized plurality of simple address locations within a bulk memory, for each item in the set. A testing for membership comprises employing a logical AND operation upon all values of binary indicators at memory locations addressed by hash values of a test item, to determine whether each and every hash value generated for the test item exactly matches with previously loaded indicators at those address locations in the bulk memory, which in the pereferred embodiment is of the CCD type. The present invention is a machine-implemented process, and employs a known algorithm as part of the overall process. The present invention also essentially comprises synergistic interaction of a hardware item called a “hash board”, and a bulk memory. The hash board generates a large number of hash addresses for any given item, using minimal computation time. The expected error rate is a function of the vocabulary size and the total number of indicators in the bulk memory. The bulk memory allows a low error rate for large vocabularies without exceeding the statistically ideal loading density of 50 percent. The hashing technique, together with its hardware implementation, allows a black box approach to general set membership testing. Information stored in the bulk memory can be said to be encrypted because the randomizing process makes it impossible to retrieve the original set of items. A preferred embodiment of the machine-implemented process, and apparatus is for on-line spelling checking of each word which appears in daily newspaper production, against a selective 20,000-word vocabulary, previously stored as a randomized set of simple bit addresses.

대표청구항 ▼

A process for performing a set membership test by the technique of binary hash coding with allowable errors, comprising the steps of: a. receiving a source listing of a number of discrete items which define a set, and generating a number of representations for each of said items; and b. randomizing

A process for performing a set membership test by the technique of binary hash coding with allowable errors, comprising the steps of: a. receiving a source listing of a number of discrete items which define a set, and generating a number of representations for each of said items; and b. randomizing each of the number of representations through a hash step in order to yield a plurality of simple and randomly distributed hash address locations for each item of said set regardless of any variation in length for each item comprising the given set, wherein the number of address locations so generated is chosen as a function of the acceptable probability of an erroneous true when testing an item for membership; and c. storing a binary indicator (a single binary value, i.e., 0 to 1) at each of the plurality of hash address locations generated for each item of the set within a bulk storage memory device, without the ability to reconstruct the items of the set given the storage locations; and d. receiving a new item and examining said new item for set membership by repeating said generating and hashing steps upon said new item to thereby generate an equal number of new item hash address locations, and performing an AND operation upon all of the indicator values at said new item hash address locations to determine if there is a match with the set of previously stored indicators; and e. outputing whether there is or is not a match between all the indicators at the new item locations and the previously stored indicators defining the set.