DEV Community: Hagar

Rolling Hash Function

Hagar — Sun, 16 Apr 2023 15:30:31 +0000

Hash function

It's a function that can map any kind of data of arbitrary size to fixed-size values, these values are called Hash Values

In our case we will talk about Rolling Hash Function that is used in Rabin-Karp Algorithm

Rolling Hash Function:

Recap:

In Rabin Karp Algorithm, we used to compare the hash values of the pattern and the substring to find the match, by using Rollling Hash Function, we can prevent the rehashing of the whole substring by only using the old hash value.

For simplicity, I used incremental values starting from "1" to encode the english alphabet, we can use ASCII or any other encoding.

In our next iterations, we will use the old hash value, subtract the letter that is no longer inside our window and add the newly added one.

Tips to have a good rolling hash function:

1. Prevent Frequent Collisions:

We can have two equal hash values for two different strings, like having same letters in different order for example.

To prevent collisions we can multiply each character with a constant raised to power of its position.

For simplicity, I chose 10 as our constant raised to power of (n - 1) where n is the position of character from the right.
Same as the previous algorithm except that we are sure that order of characters will definitely affect our hash values.

To prevent hash value collisions, choose a constant that is
greater than the largest value in the alphabet.

And here comes tip #2

2. Prevent Integer overflows:

We will add to our formula (% m), where m is a larger prime number, since the probability of two random strings colliding is about ≈ 1/m.

Pattern Search - Rabin-Karp Algorithm

Hagar — Sun, 20 Feb 2022 21:26:15 +0000

Rabin-Karp is an algorithm used for pattern matching/searching in a string that uses a hash function unlike the naïve algorithms.

How it works

We will iterate through the string with a window with the same length of the pattern.

We will calculate a hash value for the pattern and the window of the string and check if:
The hash value of pattern equals the hash value of window of string, check each character of the window with the pattern as two distinct strings may have the same hash value due to collisions
The hash value of pattern isn't equal to the hash value of window of string, then check hash value of the next window with the hash value of the pattern and so on.

How to calculate the hash function:

The hash function here is used to map a string to an integer value.
To get a useful hash function it should:

be easily calculated
can perform precalculations.
calculating the hash function of any string takes constant time O(1)

Python code:

# q is a prime number -modulus-
def rabin_karp(string, pattern, q):
    d = 256
    n = len(string)
    m = len(pattern)
    s = 0
    p = 0
    h = 1
    i = 0
    j = 0
    for _ in range(m - 1):
        h = (h*d) % q
    for i in range(m):
        p = (d*p + ord(pattern[i])) % q
        s = (d*s + ord(string[i])) % q
    for i in range(n - m + 1):
        if p == s:
            for j in range(m):
                if string[i+j] != pattern[j]:
                    break
            j += 1
            if j == m:
                print("pattern found at index:", i)
        if i < n-m:
            s = (d * (s - ord(string[i])*h) + ord(string[i + m])) % q
        if s < 0:
            s = s + q


string = "ABCDAF"
pattern = "DAF"
q = 113
rabin_karp(string, pattern, q)

Limitations:

Spurious Hit:

A spurious hit occurs when two distinct strings have the same hash value. It increases the time complexity of the algorithm.
To reduce the occurrence of spurious hits, we use modulus.

Time Complexity:

The average case and best case complexity of Rabin-Karp is O(m + n)
The worst case complexity is O(nm), which happens when:

all characters of pattern and text are same as the hash values of all windows of string will match with hash value of pattern.
spurious hit occurs for every window.

However, if we use a good hashing function, the expected complexity would be O(n + k . t), where t is the number of matches.

As a good hashing function would rarely cause collisions. Thus, we would rarely need to compare two substrings when there is no match.

If we only want to check the existence of the pattern, the complexity would be O(n+k), as we can break the loop after the first occurrence.

Pattern Search - Optimized Naïve Search

Hagar — Fri, 17 Dec 2021 22:17:42 +0000

Assume that all characters of pattern are different, in this case we can slide the pattern by more than 1 when a mismatch occurs.

All characters of pattern are different.
Slide by j.

def optimized_naïve_search(string, pattern):
    n = len(string)
    m = len(pattern)
    i = 0
    while i <= (n - m):
        for j in range(m):
            if string[i + j] != pattern[j]:
                break
            j += 1
        if j == m:
            print("pattern found at index: ", i)
            i = i + m
        elif j == 0:
            i += 1
        else:
            i = i + j


string = "abeabc"
pattern = "abc"
optimized_naïve_search(string, pattern)

Pattern Search - Naïve Algorithm

Hagar — Wed, 15 Dec 2021 21:01:05 +0000

Pattern Searching algorithm is string matching algorithm which is used to find a pattern or a substring in another string.

1) Naïve Algorithm:

Slide the pattern over the string and check for the match.
Once you find the match, start iterating through the pattern to check for the subsequent matches.
Length of pattern has to be less or equal to length of string, if pattern's length is greater than length of string return pattern not found.

def naïve_algorithm(string, pattern):
    n = len(string)
    m = len(pattern)
    if m > n: 
        print("Pattern not found")
        return
    for i in range(n - m + 1):
        j = 0
        while j < m:
            if string[i + j] != pattern[j]:
                break
            j += 1
        if j == map:
            print("Pattern found at index: ", i)

string = "hello"
pattern = "ll"
naïve_algorithm(string, pattern)

Time Complexity:

Complexity	value
Best	O(n)
Worst	*O(m n)**

Where m is the length of pattern and n is the length of string.

Best Case - O(n):

Happens when the string doesn't have the pattern.

Worst Case - O(m * n):

Happens when:
All characters in both string and pattern are the same.
All characters in both string and pattern are the same except for the last character.

Tim Sort.

Hagar — Mon, 15 Nov 2021 15:36:05 +0000

Tim sort is a hybrid, stable sorting algorithm which uses insertion sort to sort small blocks and then merge them using merge function of merge sort, the idea is that insertion sort is typically faster for small arrays.

It is used by sort built-in functions used in python and java languages.
Technically, Tim sort was implemented in 2002 by Tim Peters in to be used in Python.

How it works:

An array is divided to number of blocks known as Runs, the size of a Run is either 32 or 64 depending on the size of the array, if the size of an array is less than the run then the whole array is sorted just by using insertion sort.
Sort each run using insertion sort.
Merge sorted run using merge function of merge sort.
Double the size of merged subarray after each iteration.

What's minimum run?

Minimum run is the smallest size of each run, minimum run shouldn't be:

too big as insertion sort is faster with small array.
too small so that it will give more number of runs that will be merged through merge function of merge sort.

For better results make sure that size of subarrays size of array/minimum run is of power of 2 as merge function of merge sort performs better with this case.

minrun = 32
def min_run(n): 
    run = 0 
    while n >= minrun:
        run |= n & 1 
        n >>= 1 
    return n + run

def insertion_sort(arr, left, right): 
    for i in range(left + 1, right + 1): 
        j = i 
        while j > left and arr[j] < arr[j - 1]: 
            arr[j], arr[j - 1] = arr[j - 1], arr[j]
            j -= 1

def merge(arr, left, mid, right): 
    len_arr1, len_arr2 = mid - left + 1, right - mid
    left_arr, right_arr = [],[]
    for i in range(0, len_arr1): 
        left_arr.append(arr[left + i])
    for i in range(0, len_arr2): 
        right_arr.append(arr[mid + 1 + i])

    i, j, k = 0, 0, left
    while i < len_arr1 and j < len_arr2:
        if left_arr[i] <= right_arr[j]: 
            arr[k] = left_arr[i]
            i += 1
        else: 
            arr[k] = right_arr[j]
            j += 1
        k += 1

    while i < len_arr1: 
        arr[k] = left_arr[i]
        i += 1
        k += 1

    while j < len_arr2:
        arr[k] = right_arr[j]
        j += 1
        k += 1

def tim_sort(arr): 
    minimum_run = min_run(len(arr))
    for start in range(0, len(arr), minimum_run): 
        end = min(start + minimum_run - 1, len(arr) - 1)
        insertion_sort(arr, start, end)

    size = minimum_run
    while size < len(arr): 
        for left in range(0, len(arr), 2 * size): 
            mid = min(len(arr) - 1, left + size - 1)
            right = min(left + 2 * size -1, n - 1)
            merge(arr, left, mid, right)
        size = 2 * size 

array = [4, 14, 52, 21, 6, 40, 19, 13] 

print("Array:") 
print(array) 

tim_sort(array) 

print("Sorted Array:") 
print(array)

Complexity:

Time Complexity:

Complexity	value
Best	O(n)
Average	O(n log n)
Worst	O(n log n)

Best Case: O(n)

Happens when the array is already sorted.

Worst Case: O(n log n)

Happens when the array is sorted in reverse order.

Space Complexity: O(n)

Pancake Sort

Hagar — Thu, 28 Oct 2021 13:32:31 +0000

Pancake sort is a sorting algorithm that focuses on decreasing number of reversals instead of decreasing the number of comparisons which is done by traditional sorting techniques.

It's called pancake sort as it seems like we are flipping pancakes with a spatula, thus, what we can do to sort an array is to use flip function.

Pancake sort algorithm:

flip():

Reverse all values from the beginning of the unsorted array till the specified index.

find_max():

Find index of maximum number within the specified range of an unsorted array.

pancake_sort():

Iteratively, decrease current_size of the array, knowing for a fact that array is sorted in a bottom-up manner.

Get the index of maximum value in the unsorted array within specified current_size, checks if index of maximum value doesn't equal current_size - 1, then we can flip(index of maximum value) and finally flip(current_size - 1)

def flip(arr, i): 
    start = 0 
    while start < i: 
        arr[start], arr[i] = arr[i], arr[start]
        start += 1 
        i -= 1 

def find_max(arr, current_size): 
    mi = 0 
    for i in range(0, current_size): 
        if arr[i] > arr[mi]: 
            mi = i
    return mi 

def pancake_sort(arr): 
    current_size = len(arr) 
    while current_size > 1: 
        mi = find_max(arr, current_size)
        if mi != current_size - 1: 
            flip(arr, mi)
            flip(arr, current_size - 1)
        current_size -= 1
    return arr


arr = [40, 20, 28, 8, 60, 33]
print(pancake_sort(arr))

Time complexity:

Complexity	value
Best	O(n)
Worst	O(n^2)

Bucket Sort

Hagar — Wed, 06 Oct 2021 16:55:02 +0000

Scatter Sort Gather

Bucket sort, also known as bin sort is a sorting algorithm where elements of an array are distributed into a number of buckets.

How it works

The array is divided into buckets, each bucket is sorted either by any sorting technique or by recursively applying bucket sort itself and at the end the buckets are combined to have the desired sorted array.

When to use bucket sort

Input is floating point numbers
Input is uniformly distributed over a range

Bucket Sort Example

Assume we have an unsorted array of size 7 that contains floating point numbers.

Then we will create another array B, as we have floating point numbers that range from [0,1], thus the best size for the array is 10 where each value will be in its right bucket using this formula:
bucket = Int(value * size of array B)

Then I used the built-in list.sort() method which is tim sorting technique that modifies the list in-place to sort each bucket.

Python code

 def bucket_sort(arr): 
    buckets_arr = []
    output = []
    # create buckets 
    for i in range(10): 
        buckets_arr.append([])

    #Insert elements in buckets - Scatter
    for value in arr: 
        index = int(len(buckets_arr) * value)
        buckets_arr[index].append(value)

    print("buckets before sorting",  buckets_arr, sep='\n')

    #Sorting in each bucket - Sort
    for i in range(len(arr)):
        buckets_arr[i].sort()

    print("buckets after sorting",  buckets_arr, sep='\n')

    #Gather 
    for i in range(len(buckets_arr)):
        for j in range(len(buckets_arr[i])):
            output.append(buckets_arr[i][j])

    return output 

arr = [0.13, 0.8, 0.77, 0.2, 0.11, 0.97, 0.78]
result = bucket_sort(arr)
print("Sorted array", result, sep='\n')

Github Link

Detect Number of Buckets

If the data is floating point numbers that ranges from [0,1], use 10 buckets so that first bucket contains values from [0,1[ and so on. To know the right index:

bucket_index = Int(value * size of array B)

If the data is numbers between 0 and 1000 for example we can use also 10 buckets or maybe 5 buckets and to know the right index you can use:

bucket_index = Int(value/size of array B)

If data is string, we can have 26 buckets, each bucket represents a character from a to z. To know the right bucket use first characters to know which bucket it matches with.

Time Complexity

It actually depends on the number of elements in each bucket.

Complexity	value
Best	O(n+k)
Average	O(n)
Worst	O(n^2)

Best case - O(n+k)

Happens when elements are uniformly distributed and number of elements in buckets are nearly equal.
O(n) is the complexity of creating buckets and O(k) is the complexity of sorting with a technique that gives linear time complexity at its best.

Worst case - O(n^2)

Happens when elements are close in range where elements are likely placed in the same bucket giving buckets with larger number of elements than the others, so, the complexity here depends on the sorting technique used to sort the buckets.

Space complexity

It depends on size of input array and number of buckets, thus the space complexity of bucket sort if O(nb) where n is number of elements in input array and b is number of buckets.

Algorithms

Hagar — Mon, 19 Apr 2021 15:57:26 +0000

What’s an algorithm?

Algorithm is simply a set of instructions implemented to perform a certain task. The word “algorithm” is derived from the name of Al-Khwarizmi and then was Latinized as “Algoritmi”.

Complexities:

Time and Space Complexities are so important and the gate to understand the whole concept of an algorithm. Furthermore, calculation of time and space complexity is so essential to reach the optimum solution to many problems.
Technically, complexity is used to measure performance of your algorithm and to know the best approach to solve the problem.
Time complexity: amount of time taken to process the set of instructions in terms of length of input.
Space Complexity: amount of space or memory taken by the set of instructions in terms of length of input.
Big O notation: is the upper bound of an algorithm, and is notated by O().
So, if we want to search for an element in an array, the worst case scenario is to find this element at last index in the array, which means traversing the whole array of length (N), having a time complexity of O(N) and space complexity of O(1) as we didn’t use any extra space.
Big 𝛀 notation: big omega is the lower bound of an algorithm, and is notated by 𝛀().
Big 𝚹 notation: big theta is tight bound of an algorithm, and is notated by 𝚹().
The most used notation is Big O notation, because it will give us an upper limit of the execution time i.e. the execution time in the worst case.

DEV Community: Hagar

Rolling Hash Function

Hash function

Rolling Hash Function:

Recap:

Tips to have a good rolling hash function:

1. Prevent Frequent Collisions:

2. Prevent Integer overflows:

Pattern Search - Rabin-Karp Algorithm

How it works

How to calculate the hash function:

Python code:

Limitations:

Spurious Hit:

Time Complexity:

Pattern Search - Optimized Naïve Search

Pattern Search - Naïve Algorithm

1) Naïve Algorithm:

Time Complexity:

Best Case - O(n):

Worst Case - O(m * n):

Tim Sort.

How it works:

What's minimum run?

Complexity:

Time Complexity:

Best Case: O(n)

Worst Case: O(n log n)

Space Complexity: O(n)

Pancake Sort

Pancake sort algorithm:

flip():

find_max():

pancake_sort():

Time complexity:

Bucket Sort

Scatter Sort Gather

How it works

When to use bucket sort

Bucket Sort Example

Python code

Detect Number of Buckets

Time Complexity

Best case - O(n+k)

Worst case - O(n^2)

Space complexity

Algorithms

What’s an algorithm?

Complexities: