From Hashing to Rolling Hashing
A major application is the Rabin-Karp string search algorithm. Another important application is rsync.
The cleverness of a rolling hash is efficient calculation - instead of computing hash values fresh each time, it updates the hash incrementally as new data comes in.
Rolling Hash in Rabin-Karp
This is used in string matching, and plagiarism detection.
Rolling Hash in rsync
This is manifested in the form of a rolling checksum, to check "everything is ok" as the sync operation proceeeds.
Other names for Rolling Hash
Recursive hashing is another name for rolling hash, or rolling checksum, as in the case of rsync.
No comments:
Post a Comment