<PERSON> hashing is a rapid technique for determining if a given substring COULD POSSIBLY be contained in a larger string. The first step is to create SIGNATURES of all the strings in the file to be searched using the hashing algorithm. These signatures are then stored along with the actual file. Typically the file being dealt with consists of individual text lines, because the search technique will only work within a single line. Then using the same hashing algorithm one constructs the signature of the substring being searched for. One then applies a simple Boolean test to determine if the substring is possibly contained in the string. If the answer is affirmative then one must examine the actual string and substring to see if there is indeed a match. But if the answer is negative it is impossible for the substring to be contained in the string and that particular string in the file does not have to be examined further.
The signatures are constructed by examining all pairs of consecutive characters in the string. Thus for the string "abcdef" the pairs would be "ab","bc","cd","de","ef". Depending on the nature of the data and the computer being used, one picks a bit size for the signature, perhaps 32 or 64 bits, but different sizes are possible. Next you have to develop a hash function that will map any pair of characters into one of the bits in the signature. 904
A simple hash function would be to multiply the values of the characters together, divide by the bit size of the signature, and use the remainder. In practice some tweaking is necessary to get a good distribution of the bits set across all of the character pairs. You then calculate the hash for each of the character pairs and set the corresponding bit in the signature. When different pairs hash to the same bit the bit stays set, that is you keep ORing in the bit to set in the signature. You build a table of all of the signatures for all lines in the original source file.
To search for a substring you calculate the signature of the substring itself. If the substring is contained in the string then ALL OF THE SET BITS IN THE SIGNATURE OF THE SUBSTRING MUST BE SET IN THE SIGNATURE OF THE STRING. This should be self evident, for if the substring contained a pair of characters which hashed to say 17, but bit 17 wasn't set in the signature of the string, then clearly that pair of characters could not be in the string, because if it were that bit would have been set.
If the signature is contained in a single computer word then all that is necessary to determine if all the bits of the substring are in the string is to exclusive or (XOR) the signatures of the string and the substring, and then and (AND) that result with the signature of the substring. If the result is non zero, then there exists at least one pair of characters in the substring that is not in the string, and hence the substring cannot be contained in the string. Since only two logical operations are required to totally test any string in the file the program can operate very quickly. In practice the <PERSON> hashing test will eliminate most of the file from consideration and the program will only have to perform the full substring search on a very small portion of the file.
I explained the algorithm using pairs of characters, but another variant is to use three consecutive characters.
Professor <PERSON> was one of my teachers at the Courant Institute of Mathematical Sciences and I have used this algorithm in a number of text editing programs. It is a truly brilliant observation. 904