Friday, 15 September 2017

Algorithms | Find longest Snake sequence in a given matrix

Objective
Given a matrix, write an algorithm to find out the snake sequence which has the maximum length. There could be much snake sequence in the matrix; you need to return the one with the maximum length. Travel is allowed only in two directions; either go right OR goes down.

What is snake sequence?
Snake sequence can be made if num­ber in an adjacent right cell or num­ber in the adjacent down cell is either +1 or –1 from the number in the current cell.

Example
9
6
5
2
8
7
6
5
7
3
1
6
1
1
1
7

Approach
For each cell of the matrix, we keep the maximum length of a snake which ends in the current cell. The maximum length snake sequence will have the maximum value. The maximum value cell will correspond to the tail of the snake. In order to print the snake, we need to backtrack from tail all the way back to snake’s head. So avoid that backtracking, we will store the data solved subproblems(dynamic programming). 

Solution: Dynamic Programming
1. As we can travel only in two directions, either go right or go down. All we need to take care of the condition that we can travel only to the adjacent cells (right or down) only if the number of those cells has the difference of 1 from the current cell.
2. We will use dynamic programming for temporary storage, two-dimensional array to store the results of snake result.
3. Keep tracking of maximum length and at the end print the sequence using the temporary array.
4. We will use the Bottom-up approach of Dynamic programming and store the results of subproblems to reuse them in future.

Dynamic Programming relation is defined as
Let dp[i][i] represent maximum length of a snake which ends at cell (i, j).

dp[i][j] = max(dp[i][j], dp[i][j – 1] + 1) if abs(matrix[i][j] - matrix[i][j – 1]) == 1

dp[i][j] = max(dp[i][j], dp[i – 1][j] + 1) if abs(matrix[i][j] - matrix[i – 1][j]) == 1


Snake problem code in Java:
package com.dp;
import java.util.Stack;

public class SnakeSequence {

            /**
             * This method will return the longest snake sequence.
             * It works on the Dynamic programming concept.
             * @param matrix
             * @return longest snake sequence.
             */
            private static void getLongestSnakeSeq(int[][] matrix, int row, int col) {
                       
                        int[][] dp = new int[row][col];
                        for (int i = 0; i < row; i++) {
                                    for (int j = 0; j < col; j++) {
                                                dp[i][j] = 1;
                                    }
                        }

                        int max_len = -1;
                        int idxI = -1; int idxJ = -1;
                        for (int i = 0; i < row; i++) {
                                    for (int j = 0; j < col; j++) {
                                                if(i>0 && Math.abs(matrix[i][j]-matrix[i-1][j])==1) {
                                                            dp[i][j] = Math.max(dp[i][j], dp[i-1][j]+1);
                                                }

                                                if(j>0 && Math.abs(matrix[i][j]-matrix[i][j-1])==1) {
                                                            dp[i][j] = Math.max(dp[i][j], dp[i][j-1]+1);
                                                }

                                                if(max_len<dp[i][j]) {
                                                            max_len = dp[i][j];
                                                            idxI = i;
                                                            idxJ = j;
                                                }
                                    }
                        }

                        System.out.println("Length of sequence "+max_len + "\nSequence is ");
                        printPath(matrix, dp, max_len, idxI, idxJ);
            }

            /**
             * To print the snake path
             */
            private static void printPath(int[][] matrix, int[][] dp, int maxLen,
                                    int idxI, int idxJ) {

                        Stack<Integer> stack = new Stack<>();
                        while(maxLen >= 1) {
                                    stack.add(matrix[idxI][idxJ]);
                                    if(idxI>0 && Math.abs(dp[idxI-1][idxJ]-dp[idxI][idxJ])==1) {
                                                idxI--;
                                    } else if(idxJ>0 && Math.abs(dp[idxI][idxJ-1]-dp[idxI][idxJ])==1) {
                                                idxJ--;
                                    }
                                    maxLen--;
                        }
                       
                        /** To print the Sequence. */
                        for (Integer integer : stack) {
                                    System.out.print(" " + integer);
                        }
            }

            /**
             * Driver method.
             * @param args
             */
            public static void main(String[] args) {
                        int matrix[][] = {
                                                {9, 6, 5, 2},
                                                {8, 7, 6, 5},
                                                {7, 3, 1, 6},
                                                {1, 1, 1, 7}};

                        getLongestSnakeSeq(matrix, 4, 4);
            }
}

Output:
Length of sequence 7
Sequence is
 7 6 5 6 7 8 9

Tuesday, 12 September 2017

Algorithms | The Rabin-Karp algorithm

The fundamental string searching (matching) problem is defined as follows: given two strings – a text and a pattern, determine whether the pattern appears in the text. The problem is also known as "the needle in a haystack problem."

The “Naive” Method
Its idea is straightforward — for every position in the text, considers it a starting position of the pattern and sees if you get a match.

Pseudo code for Naïve(Brute force)
function NaiveSearch(string s[1..n], string pattern[1..m])
for i from 1 to n-m+1
   for j from 1 to m
      if s[i+j-1] ≠ pattern[j]
         jump to next iteration of the outer loop
   return i
return not found

The “naive” approach is easy to understand and implement but it can be too slow in some cases. If the length of the text is n and the length of the pattern m, in the worst case it may take as much as (n * m) iterations to complete the task.

It should be noted though, that for most practical purposes, which deal with texts based on human languages, this approach is much faster since the inner loop usually quickly finds a mismatch and breaks. A problem arises when we are faced with different kinds of “texts,” such as the genetic code.

Rabin-Karp Algorithm
This is actually the “naive” approach augmented with a powerful programming technique – the hash function. In order to avoid the comparison between the pattern and the text character by character, we’ll try to compare them at once, so we need a good hash function. With its help, we can hash the pattern and check against hashed sub-strings of the text.

Pseudo code for Rabin-Karp
function RabinKarp(string s[1..n], string pattern[1..m])
hpattern := hash(pattern[1..m]);
for i from 1 to n-m+1
  hs := hash(s[i..i+m-1])
  if hs = hpattern
    if s[i..i+m-1] = pattern[1..m]
       return i
return not found

Java code for Rabin-Karp
package com.algo;

public class RobinKarp {

    private static int WINDOW;

    /** PRIME NUMBER which is required the hash function. */
    private static final int PRIME_NUM = 3;

    /**
     * Compare the pattern to text from a given index.
     *
     * @param text
     * @param pattern
     * @param i
     * @return true/false
     */
    private static boolean compare(char[] text, char[] pattern, int i) {
        for (int j = 0; j < WINDOW; j++) {
            if (text[j + i + 1] != pattern[j]) {
                return false;
            }
        }
        return true;
    }

    /**
     * This method is used to calculate the hash of all window in O(n) time complexity.
     * Approach:
     * 1. Roll out the value of start method
     * 2. Divide by prime to reposition the elements, second position element will start
     *      element as the prime multiplication has been reduced.
     * 3. Include the next element with prime multiplication.
     *
     * @param str
     */
    private static int getRollingHash(char[] array, int s, int hash) {

        /** Rolling out first element of window. */
        hash = hash - (array[s] - 'a' + 1);

        /** Divide by prime number. */
        hash = hash / PRIME_NUM;

        /** Add new element to window. */
        hash = (int) (hash + (array[s + WINDOW] - 'a' + 1) * Math.pow(PRIME_NUM, WINDOW - 1));

        return hash;
    }


    /**
     * This method is used to calculate the hash.
     *
     * @param array
     * @param s
     * @param l
     * @return hash code.
     */
    private static int hash(char[] array, int s, int l) {
        int hash = 0;

        for (int i = s; i < l; i++) {
            hash = hash + (int) ((array[i] - 'a' + 1) * Math.pow(PRIME_NUM, i));
        }

        return hash;
    }

    private static void robinKarp(String text, String pattern) {

        char[] textArray = text.toCharArray();
        char[] patternArray = pattern.toCharArray();

        /* Window size = length of pattern. */
        WINDOW = pattern.length();

        /* Calculate the hash of the pattern. */
        int pHash = hash(pattern.toCharArray(), 0, WINDOW);

        /* Initially calculate the hash of the window size text. */
        int tHash = hash(textArray, 0, WINDOW);

        for (int i = 0; i < text.length() - WINDOW; i++) {

            /**
             * Calculate the Rolling hash code
             **/
            tHash = getRollingHash(textArray, i, tHash);

            /**
             * First compare the rolling hash of text with hash of pattern if matched,
             * compare the Strings else compare next rolling hash.
             **/
            if (tHash == pHash && compare(textArray, patternArray, i)) {
                System.out.println("Pattern occurs with shift " + i);
                break;
            }
        }
    }

    /**
     * Driver method.
     *
     * @param args
     */
    public static void main(String[] args) {
        String text = "abedacda";
        String pattern = "cda";

        /** This method will print the index of pattern in text. */
        robinKarp(text, pattern);
    }
}

Time complexity
The average and best case running time of the Rabin-Karp algorithm is O(n+m), but its worst-case time is O(nm). Worst case of Rabin-Karp algorithm occurs when all characters of pattern and text are same as the hash values of all the substrings of text [] match with the hash value of pattern[].
Example: pattern[] = “AAA” and text[] = “AAAAAAA”.

Multiple pattern searches
The Rabin–Karp algorithm is inferior for single pattern searching to Knuth–Morris–Pratt algorithm, Boyer–Moore string search algorithm and other faster single pattern string searching algorithms because of its slow worst-case behavior. However, it is an algorithm of choice for multiple pattern searches.

That is, if we want to find any of a large number, say k, fixed length patterns in a text, we can create a simple variant of the Rabin–Karp algorithm that uses a Bloom filter or a set data structure to check whether the hash of a given string belongs to a set of hash values of patterns we are looking for:

function RabinKarpSet(string s[1..n], set of string subs, m):
    set hsubs := emptySet
    foreach sub in subs
        insert hash(sub[1..m]) into hsubs
    hs := hash(s[1..m])
    for i from 1 to n-m+1
        if hs  hsubs and s[i..i+m-1]  subs
            return i
        hs := hash(s[i+1..i+m])
    return not found
We assume all the substrings have a fixed length m.

A naïve way to search for k patterns is to repeat a single-pattern search taking O(n+m) time, totaling in O((n+m)k) time. In contrast, the variant algorithm above can find all k patterns in O(n+km) time in expectation, because a hash table checks whether a substring hash equals any of the pattern hashes in O(1) time.

Java code for Rabin-Karp Multiple search
package com.algo;
import java.util.HashMap;
import java.util.Map;

public class RobinKarp {

    private static int WINDOW;

    /** PRIME NUMBER which is required the hash function. */
    private static final int PRIME_NUM = 3;

    /**
     * Compare the pattern to text from a given index.
     *
     * @param text
     * @param pattern
     * @param i
     * @return true/false
     */
    private static boolean compare(char[] text, char[] pattern, int i) {
        for (int j = 0; j < WINDOW; j++) {
            if (text[j + i + 1] != pattern[j]) {
                return false;
            }
        }
        return true;
    }

    /**
     * This method is used to calculate the hash of all window in O(n) time complexity.
     * Approach:
     * 1. Roll out the value of start method
     * 2. Divide by prime to reposition the elements, second position element will be
     *     start element as the prime multiplication has been reduced.
     * 3. Include the next element with prime multiplication.
     *
     * @param str
     */
    private static int getRollingHash(char[] array, int s, int hash) {

        /** Rolling out first element of window. */
        hash = hash - (array[s] - 'a' + 1);

        /** Divide by prime number. */
        hash = hash / PRIME_NUM;

        /** Add new element to window. */
        hash = (int) (hash + (array[s + WINDOW] - 'a' + 1) * Math.pow(PRIME_NUM, WINDOW - 1));

        return hash;
    }


    /**
     * This method is used to calculate the hash.
     *
     * @param array
     * @param s
     * @param l
     * @return hash code.
     */
    private static int hash(char[] array, int s, int l) {
        int hash = 0;

        for (int i = s; i < l; i++) {
            hash = hash + (int) ((array[i] - 'a' + 1) * Math.pow(PRIME_NUM, i));
        }

        return hash;
    }

    private static void robinKarp(String text, String[] pattern) {
        char[] textArray = text.toCharArray();
        Map<Integer, String> hsubs = new HashMap<Integer, String>();

        /**
         * Calculate the hash of the pattern all pattern and Store it into the map. .
         */
        for (int i = 0; i < pattern.length; i++) {
            /* Window size = length of pattern. */
            WINDOW = pattern[i].length();

            int pHash = hash(pattern[i].toCharArray(), 0, WINDOW);
            /* Put the pattern hash into the map. */
            hsubs.put(pHash, pattern[i]);
        }


        /* Initially calculate the hash of the window size text. */
        int tHash = hash(textArray, 0, WINDOW);

        for (int i = 0; i < text.length() - WINDOW; i++) {

            /**
             * Calculate the Rolling hash code
             **/
            tHash = getRollingHash(textArray, i, tHash);

            /**
             * First compare the rolling hash of text with hash of pattern if matched,
             * compare the Strings else compare next rolling hash.
             **/
            if (hsubs.containsKey(tHash) && compare(textArray, hsubs.get(tHash).toCharArray(), i)) {
                System.out.println("Pattern occurs with shift " + i);
                break;
            }
        }
    }

    /**
     * Driver method.
     *
     * @param args
     */
    public static void main(String[] args) {
        String text = "abedacda";
        String[] pattern = { "cda", "da" };

        /** This method will print the index of pattern in text. */
        robinKarp(text, pattern);
    }
}
Related Posts Plugin for WordPress, Blogger...