Rabin-Karp's Algorithm

Loading...

En provenance du cours de University of California San Diego

Data Structures

1969 notes

University of California San Diego

Data Structures

1969 notes

Cours 2 sur 6 dans Specialization Data Structures and Algorithms

A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will also learn typical use cases for these data structures. A few examples of questions that we are going to cover in this class are the following: 1. What is a good strategy of resizing a dynamic array? 2. How priority queues are implemented in C++, Java, and Python? 3. How to implement a hash table so that the amortized running time of all operations is O(1) on average? 4. What are good strategies to keep a binary tree balanced? You will also learn how services like Dropbox manage to upload some large files instantly and to save a lot of storage space!

À partir de la leçon

Hash Tables

In this module you will learn about very powerful and widely used technique called hashing. Its applications include implementation of programming languages, file systems, pattern search, distributed key-value storage and many more. You will learn how to implement data structures to store and modify sets of objects and mappings from one type of objects to another one. You will see that naive implementations either consume huge amount of memory or are slow, and then you will learn to implement hash tables that use linear memory and work in O(1) on average! In the end, you will learn how hash functions are used in modern disrtibuted systems and how they are used to optimize storage of services like Dropbox, Google Drive and Yandex Disk!

Search Pattern in Text7:09

Rabin-Karp's Algorithm9:45

Optimization: Precomputation9:25

Optimization: Implementation and Analysis5:57

Rencontrer les enseignants

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

Hi, in this video, we'll introduce Rabin-Karp's Algorithm for

finding all occurrences of a pattern in the text.

At first it will have the same running time as the Naive Algorithm

from the previous video.

But then we'll be able to improve it significantly for the practical purposes.

So we need to compare our pattern to all substrings S of text T,

with length the same as the length of the pattern.

And in the Naive algorithm, we just did that by checking character by

character whether pattern is equal to the corresponding substring.

And the idea is we could use hashing to quickly compare P with substrings of T.

So, how to do that?

Well, let's introduce some hash function h and

of course if it is a deterministic hash function.

And we see that the value of hash function on the pattern P is

different from the value of this hash function on some string S.

Then definitely P is not equal to S, because h is deterministic.

However if the value of hash function on P is equal to the value of hash function

on S, P can be equal to S or it can be different from S if there is a collision.

So to exactly check whether P is equal to S or

not we will need to call our function AreEqual(P,S).

And so this doesn't yet save us any time.

But we hope that we could call this function AreEqual

less frequently because there will be only few collisions.

So we'll use polynomial hashing family.

Polygraphic P with index p small with some big prime number p.

And if P pattern is not equal to S substring of text,

then the probability that the value of the hash function on the pattern

is the same as the value of hash function on the sub string is at

most length of the pattern divided by our big prime number p.

And we'll choose, a prime number P big enough, so

that this probability will be very small.

So here is the code, of our algorithm RabinKarp.

It takes its input, text T, and pattern P.

And it starts by initializing the hash function from polynomial family.

We first choose a very big prime number p.

We'll talk later about how to choose it, how big it should be.

And we also choose a random number x between 1 and p- 1.

Choose the specific hash function from the polynomial family.

Initialize all our list of positions where pattern occurs in text with an empty list.

We also precompute the hash value of our pattern, and

we call the PolyHash function to do that.

And then we again need to go through all

possible starting positions of pattern and text.

So we go from i from zero to difference of the length of text and pattern.

And for each i, we take the substring starting in this position i and

of length equal to the lengths of the pattern,

which is t from i to i plus length of the pattern minus 1.

And you compute the hash value of this substring.

And then we'll look at the hash of the pattern and the hash of the substring.

If they are different,

then it means that definitely, P is not equal to this substring.

And so, P doesn't occur in position i and so

we don't need to do anything in this iteration so we just continue to the next

iteration of the loop without calling AreEqual.

However, if has values pHash and tHash aren't equal,

then we need to check if it's true that P is really equal to the substring

of T starting in position i or it is just a collision of our hash function.

And to do that we make a call to AreEqual and

pass there the substring and the pattern.

If AreEqual returns true, it means that pattern is really equal to

the correspondence substring of texts, and then we advance position i to resolve.

Because pattern P occurs in position i in the text T.

Otherwise we just continue to the next situation of our for loop.

So this more or less the same as naive algorithm, but we have an additional

checking of hash value, and so we're not always calling AreEqual.

We are calling AreEqual either if P is equal to the corresponding sub

string of T or if there is a collision.

Let's estimate the running time of this algorithm.

So first we need to talk about false alarms.

We'll call false alarm the event when P is compared with

a substring of T from i to i plus length of P minus 1.

Compared inside the AreEqual procedure, but

pattern P is actually not equal to this substring.

So there's a false alarm in the sense that P doesn't occur in the text T

starting from position i, but we still called the AreEqual function.

And we need to go character by character through P and

the substring to test that they're actually not equal.

So the probability of false alarm as we know from the previous lesson,

is at most length of the pattern over prime number P, which we choose.

So on average, the total number of false alarms will be the number of iterations

of our for loop, multiplied by this probability.

And so this total number of false alarms can be made very small if we

choose prime number P, bigger than the product of length of the text,

and length of the pattern.

Much bigger.

So now let's estimate the running time of everything in our

code except for calls to the AreEqual function.

So the hash value of the pattern is computed in time big O of length of

the pattern.

Hash of the substring corresponding to the pattern is computed

in the same big O of length of the pattern time.

And this is done length of text minus length of the pattern plus 1 times

because that is the number of iterations of the for loop.

So the total time to compute all those hash values

is big O of length of text multiplied by the length of the pattern.

Now what about the running time of all calls to AreEqual?

Each call to AreEqual is computed in big O of length of the pattern because we pass

there are two strings of length equal to length of the pattern.

However, AreEqual is called only when the hash value of the pattern as

the same as the hash value of the corresponding substring of T.

And that means that either P occurs in position i in text T or

there was a false alarm.

And by selecting the prime number to be very big,

much bigger than the product of the length of text, and the length of pattern,

we can make the number of false alarms negligible, at least on average.

So, if q is the number of times that pattern P is actually found,

in different positions in the text T,

then the total time spent in AreEqual, on average, is big O of q.

Which is number of times P is really found, plus the fraction

T minus P plus 1 multiplied by P and divided by prime, p.

Which is the average number of times that a false alarm happens.

So q plus number of false alarms is the number of

times that we need to actually call function AreEqual.

And then the time spent inside the function AreEqual is proportional to

the length of the pattern.

So, this is the same as the O of q multiplied by the length of the pattern,

because the second summoned can be made pretty small,

less than 1 if we choose big enough prime number p.

And we'll only get the first summoned multiplied by the length of the pattern.

And now the total running time of the Rabin-Karp's algorithm in this variant

is big O length of text multiplied by length of pattern plus

q multiplied by the length of pattern.

But, of course we know that the number of times that pattern occurs in text is not

bigger than the number of characters, in text.

Because there are only so many different positions where the pattern could start,

in text.

So, this sum is dominated by the sum of big O of length of text,

multiplied by length of the pattern.

So, this is basically the same running time as our estimate for

the naive algorithm.

So we haven't improved anything yet, but this time can be improved for

this algorithm with a clever trick.

And you will learn it in the next video.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play