The Rabin-Karp rolling hash algorithm is excellent at finding a pattern in a large file or stream, but there is an even more interesting use case: creating content based chunks of a file to detect the changed blocks without doing a full byte-by-byte comparison. The traditional computation of the hashes of interleaving windows generally works like this: Input: [a,b,c,d,e] Window size: 3 Hash#1: hash([a,b,c]) Hash#2: hash([b,c,d]) Hash#3: hash([c,d,e]) The Rabin-Karp implementation is very efficiently reuses the previous hash to calculate the new one: Hash#1 = hash([a,b,c]) Hash#2 = Hash#1 – hash(a) + hash(d) Hash#3 = Hash#2 – hash(b) + hash(e) So, to calculate the next window’s hash all we need to do is to remove the window’s first element's ‘hash value’ from the current hash and add the new to it. Even though a simple mathematical addition would do fine, it’s usually not preferred because it can cause high collision rate among the hash values: a+b+c = a+
Showing posts from October, 2012
- Other Apps
Do you want the application 'iTunes.app' to accept incoming network connections? It's quite common to run into the problem that a signed app on Mac OS X thinks it's been modified so the firewall will keep asking whether you want to allow this app to accept connections. The fix is quite easy, all we need to do is find out why the firewall thinks that the app is damaged. To check, go to terminal and run: $ codesign -vvv /Applications/iTunes.app it will show something like this: /Applications/iTunes.app: a sealed resource is missing or invalid In architecture: i386 resource added: /Applications/iTunes.app/Contents/Resources/English.lproj/DevicePrefsMobileMe.nib/objects.xib resource added: /Applications/iTunes.app/Contents/Resources/English.lproj/Localized.rsrc resource added: /Applications/iTunes.app/Contents/Resources/English.lproj/SmartPlaylist.nib/objects.xib resource added: /Applications/iTunes.app/Contents/Resources/iTunesASUHelper resource
- Other Apps
When you try to run you Android app in Eclipse using the keyboard shortcuts and you face the " The active editor does not contain a main type " error then simply go ahead and uninstall Android ADT form Eclipse (About / Installation Details, uninstall Android Development Tools), then re-install it from the original source (https://dl-ssl.google.com/android/eclipse/). All other settings, like run configuration and source location, did not help me.