Using a rolling hash to break up binary files - CodeProject

Using a rolling hash to break up binary files - CodeProject
If you've ever had to figure out what changed in a large binary chunk of data, you may have run into a number of the same obstacles I ran into.

I’m presently working on a system that has to back up data on Windows drives.  We store that data in a central repository, and we run the backups frequently.  Backups are often huge.  The first one can be painful, but after that, if we keep some evidence around, subsequent backups are pretty quick.

Some of the evidence comes from the file system.  For example, NTFS keeps a rolling journal of files that have been changed.  If the journal hasn’t rolled off the changes we captured in the last backup, then it has details of all the files that have been changed.

A Possible Solution
A rolling hash is one where you pick a window size…let’s say 64 bytes…and then hash every 64-byte-long segment in the file.  I don't mean a hash for 0-63, 64-127, 128-191, etc…but for 0-63, 1-64, 2-65, etc.

Assuming we do get random-looking hash values, we can take a regular subset of those hashes and arbitrarily declare that these hashes “qualify” as sentinel hashes.

The smaller the subset of qualifying hashes, the larger the distance between hashes we'll find that qualify, and hence the larger average size of the chunks you’re going to get.  The way I figure out if a hash qualifies is:

var matched = ( hash | mask ) == hash;

…where hash is the rolling hash, and mask is a bit mask.  The more 1-bits in the mask, the more hashes we’ll exclude and the bigger our chunks are.  You can use any way you want to get 1-bits into your mask…but an easy, controllable way is to declare it like this:

const long int mask = ( 1 << 16 ) - 1;

…where 16 is the number of 1-bits I want.  Each 1-bit doubles the size of the average chunk.

The hashing algorithm itself was originally described by Richard M. Karp and Michael O.

This function's beauty lies in the fact that it is very efficient to apply to a running-window of bytes.  Unlike a lot of hashes, you can efficiently add or remove a contributing byte from the hash…hence the “rolling” nature of the hash.  It uses only integer addition and multiplication, so it’s fairly processor-friendly.

Cooked down, for a window of bytes w of length n and a constant seed p, the hash is computed:

hash = p^n(w[n]) + p^n-1(w[n-1]) + … + p^0(w[0]);

http://blog.teamleadnet.com/2012/10/rabin-karp-rolling-hash-dynamic-sized.html

public void displayChunks() {

 String filelocation = "file.bin";

 int mask = 1 << 13;

 mask--; // 13 bit of '1's

 

 File f = new File(filelocation);

 FileInputStream fs;

 try {

  fs = new FileInputStream(f);

  BufferedInputStream bis = new BufferedInputStream(fs);

  // BufferedInputStream is faster to read byte-by-byte from

  this.is = bis;

 

  long length = bis.available();

  long curr = length;

 

  // get the initial 1k hash window //

  int hash = inithash(1024);

  ////////////////////////////////////

 

  curr -= bis.available();

 

  while (curr < length) {

   if ((hash & mask) == 0) {

    // window found - hash it,

    // compare it to the other file chunk list

   }

   // next window's hash  //

   hash = nexthash(hash);

   /////////////////////////

   curr++;

  }

  fs.close();

 } catch (Exception e) {

 }

}

http://docslide.us/technology/finding-similar-files-in-large-document-repositories.html
Read full article from Using a rolling hash to break up binary files - CodeProject

Rabin-Karp Multiple substring search in Java

One person's code is another's pain: Multiple substring search in Java
public final class RKPatternMatcher 

{
    private HashMap<Integer, String> patterns;
    private int minPatternLength=Integer.MAX_VALUE;
    
    private int matchIndex=-1;
    private String matchText;
    
    private static final int M = 8300009;
    private static final int B = 257;
    private int E = 1;
    
    public RKPatternMatcher(String[] patterns) 
    {
        this.patterns = new HashMap<Integer, String>(patterns.length);
        for(int i=0;i<patterns.length;++i)
        {
            int patternLength = patterns[i].length();
            if(patternLength == 0) throw new IllegalArgumentException("Pattern cannot be an empty string");
            if(patternLength < minPatternLength)
                minPatternLength = patternLength;
        }
        for(int i=0;i<patterns.length;++i)
        {
            this.patterns.put(hash(patterns[i]), patterns[i]);
        }
        if(patterns.length > 0)
        {
            for (int i=0; i<minPatternLength-1; i++) // computing E = B^{m-1} mod M
                E = (E * B) % M;
        }
    }

    private int hash(String pattern)
    {
        // calculate the hash value of the pattern
        int hp = 0;
        for(int i = 0; i < minPatternLength; i++)
        {
            char ch = pattern.charAt(i);
            hp =  (hp * B + ch) % M;
        }
        return hp;
    }
    private boolean checkMatch(char[] text, int startIndex, String pattern)
    {
        int n = pattern.length();
        if(text.length-startIndex < n) return false;
        for(int i=0;i<n;++i)
        {
            int ch = text[startIndex+i];
            if(ch != pattern.charAt(i)) return false;
        }
        matchIndex = startIndex;
        matchText = pattern;
        return true;
    }
    
    public boolean hasMatch(String text)
    {
        return hasMatch(text, 0);
    }
    
    public boolean hasMatch(String text, int fromIndex)
    {
        int n = text.length();
        if(n - fromIndex < minPatternLength) return false;
        char[] chars = text.toCharArray();
        return hasMatch(chars, fromIndex);
    }    
    public boolean hasMatch(char[] chars, int fromIndex)
    {
        matchText = null;
        matchIndex = -1;
        int n = chars.length;
        if(n - fromIndex < minPatternLength) return false;
        // calculate the hash value of the first segment 
        // of the text of minPatternLength  
        int ht = 0;
        for(int i = 0; i < minPatternLength; i++)
        { 
            int ch = chars[fromIndex+i];
            ht = (ht * B + ch) % M;
        }
        String pattern = patterns.get(ht);
        if(pattern!=null)
        {
            if(checkMatch(chars, fromIndex, pattern)) return true;
        }
        //start the "rolling hash" - for every next character in
        // the text calculate the hash value of the new segment
        // of minPatternLength          
        for(int i = minPatternLength + fromIndex; i < n; i++) 
        {
            char ch1 = chars[i - minPatternLength];
            char ch2 = chars[i];
            ht = (B*(ht - ((ch1*E) % M)) + ch2) % M;       
            if (ht < 0) ht += M; 
            pattern = patterns.get(ht);
            if(pattern!=null)
            {
                if(checkMatch(chars, 1 + i - minPatternLength, pattern)) return true;
            }
        }
        return false;
    }

Read full article from One person's code is another's pain: Multiple substring search in Java

Rolling hash, Rabin Karp, palindromes, rsync and others

Rolling hash, Rabin Karp, palindromes, rsync and others

Given a string of length n, count the number of palindromic substring of S. Solve better than O(n²).

Given a string of length n, find the longest substring that is repeated at least k times. Solve in O(n log n)

Given a bitmap, find out the largest square that's repeated in the bitmap.

Given a string S figure out if the string is periodic. (there is a p such that for any i we have that s[i] == s[i + p]) For example abcabcab is periodic with p = 3. O(n log n)

Given two equal length strings, figure out if one is a rotation of the other. O(n)

Given two polygons find out if they are similar polygons. O(n)

Given a string, find it's longest periodic prefix. O(n log n) For aaabaaabcde the answer is aaabaaab

Given a tree T with character labeled nodes and a given string P count how many downward paths match P. O(n)

http://blog.teamleadnet.com/2012/10/rabin-karp-rolling-hash-dynamic-sized.html
Read full article from Rolling hash, Rabin Karp, palindromes, rsync and others

Online algorithm for checking palindrome in a stream - GeeksforGeeks

Online algorithm for checking palindrome in a stream - GeeksforGeeks
Given a stream of characters (characters are received one by one), write a function that prints 'Yes' if a character makes the complete string palindrome, else prints 'No'.

Input: str[] = "abcba"
Output: a Yes   // "a" is palindrome
        b No    // "ab" is not palindrome
        c No    // "abc" is palindrome
        b No    // "abcb" is not palindrome
        a Yes   // "abcba" is palindrome

Rolling Hash used in Rabin Karp algorithm. The idea is to keep track of reverse of first half and second half (we also use first half and reverse of second half) for every index.

1) The first character is always a palindrome, so print yes for 
     first character.

  2) Initialize reverse of first half as "a" and second half as "b".  
     Let the hash value of first half reverse be 'firstr' and that of 
     second half be 'second'.

  3) Iterate through string starting from second character, do following
      for every character str[i], i.e., i varies from 1 to n-1.
     a) If 'firstr' and 'second' are same, then character by character 
        check the substring ending with current character and print 
        "Yes" if palindrome.
        Note that if hash values match, then strings need not be same.
        For example, hash values of "ab" and "ba" are same, but strings
        are different. That is why we check complete string after hash.

     b) Update 'firstr' and 'second' for next iteration.  
           If 'i' is even, then add next character to the beginning of 
                           'firstr' and end of second half and update 
                            hash values.
           If 'i' is odd,  then keep 'firstr' as it is, remove leading 
                           character from second and append a next 
                           character at end.

// d is the number of characters in input alphabet

#define d 256

// q is a prime number used for evaluating Rabin Karp's Rolling hash

#define q 103

void checkPalindromes(char str[])

{

    // Length of input string

    int N = strlen(str);

    // A single character is always a palindrome

    printf("%c Yes\n", str[0]);

    // Return if string has only one character

    if (N == 1) return;

    // Initialize first half reverse and second half for

    // as firstr and second characters

    int firstr  = str[0] % q;

    int second = str[1] % q;

    int h = 1, i, j;

    // Now check for palindromes from second character

    // onward

    for (i=1; i<N; i++)

    {

        // If the hash values of 'firstr' and 'second'

        // match, then only check individual characters

        if (firstr == second)

        {

            /* Check if str[0..i] is palindrome using

               simple character by character match */

            for (j = 0; j < i/2; j++)

            {

                if (str[j] != str[i-j])

                    break;

            }

            (j == i/2)?  printf("%c Yes\n", str[i]):

            printf("%c No\n", str[i]);

        }

        else printf("%c No\n", str[i]);

        // Calculate hash values for next iteration.

        // Don't calculate hash for next characters if

        // this is the last character of string

        if (i != N-1)

        {

            // If i is even (next i is odd)

            if (i%2 == 0)

            {

                // Add next character after first half at beginning

                // of 'firstr'

                h = (h*d) % q;

                firstr  = (firstr + h*str[i/2])%q;

                 

                // Add next character after second half at the end

                // of second half.

                second = (second*d + str[i+1])%q;

            }

            else

            {

                // If next i is odd (next i is even) then we

                // need not to change firstr, we need to remove

                // first character of second and append a

                // character to it.

                second = (d*(second + q - str[(i+1)/2]*h)%q

                          + str[i+1])%q;

            }

        }

    }

}

http://blueocean-penn.blogspot.com/2015/05/rabin-karp-algorithm.html

	public class RabinKarpString { static final int prime = 101;
	static final int base = 103;
	public static void rabinKarp(String s){
	assert(s!=null && !s.isEmpty());
	long leftHash = s.charAt(0);
	long rightHash = s.charAt(0);
	System.out.println("Yes");
	int h = 1;
	for(int i = 1; i < s.length(); i++){
	h = (h*prime)%base;
	leftHash = (leftHash*prime + s.charAt(i))%base;
	rightHash = ( (long) (s.charAt(i)*h + rightHash))%base;
	if(leftHash == rightHash){
	isPali(s, i);
	}else
	System.out.println("No");
	}
	}
	public static void isPali(String s, int i){
	for(int l=0,r=i; l<=r; l++, r--){
	if(s.charAt(l) != s.charAt(r)){
	System.out.println("No");
	}
	}
	System.out.println("Yes");
	}
	}

http://allenlipeng47.com/PersonalPage/index/view/157/nkey
Read full article from Online algorithm for checking palindrome in a stream - GeeksforGeeks