Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

What is Harrison hashing and what are its applications in web searching? Can some one give me some relevant information?

Update:

I found it here , and is a part of M.Tech syllabus of a friend of mine. I need to explain him this concept and then see how it can be applied in web applications. Many thanks for spending your precious time.

share|improve this question
    
Where have you looked? –  vonbrand Feb 26 '13 at 15:22
    
I can't find anything about Harrison hashing on the web –  rrenaud Feb 26 '13 at 16:10
    
Where did the term come up? Note that while hashing techniques are ontopic here, webapplications are not. –  Raphael Feb 26 '13 at 16:56
    
Do you mean visual hashing ? –  Vor Feb 26 '13 at 17:10

2 Answers 2

up vote 4 down vote accepted

I think you are looking for Implementation of the Substring Test by Hashing by Malcolm C. Harrison. It describes a fast implementation, which determines if one string contains a specified substring. This technique is appropriate in searching of large static text files.

Also you can find in String Searching Algorithms By Graham A. Stephen.

share|improve this answer
    
@Raza Thanks for sending the link! –  gpuguy Feb 27 '13 at 5:34

Harrison 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. 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 Harrison 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 Harrison 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.