Rabin–Karp algorithm: Difference between revisions

Revision as of 06:10, 14 November 2004

Latest revision as of 00:08, 1 April 2025

(354 intermediate revisions by more than 100 users not shown)

Line 1:

{{Short description|String searching algorithm}}

'''Rabin-Karp algorithm''' is a [[string searching algorithm]] that seeks a pattern, i.e. a substring, within a text by using [[hashing]]. It is not widely used for single pattern matching, but is of considerable theoretical importance and is very effective for multiple pattern matching. Historically, it predates the very popular [[Knuth-Morris-Pratt algorithm]]. For text of length n and pattern of length m, its average and best case running time is O(n) (meaning proportional to n), but the worst case scenario is O(n*m), which is one of the reasons why it is not widely used.

{{no footnotes|date=September 2018}}

{{Infobox algorithm

|name = Rabin-Karp algorithm

|class = [[string-searching algorithm|String searching]]

|image = <!-- filename only, no "File:" or "Image:" prefix, and no enclosing [[brackets]] -->

|caption =

|data =

|time = <math>O(mn)</math> plus <math>O(m)</math> preprocessing time

|best-time =

|average-time = <math>O(n)</math>

|space = <math>O(1)</math>

}}

In [[computer science]], the '''Rabin–Karp algorithm''' or '''Karp–Rabin algorithm''' is a [[string-searching algorithm]] created by {{harvs|first1=Richard M.|last1=Karp|author1-link=Richard M. Karp|first2=Michael O.|last2=Rabin|author2-link=Michael O. Rabin|year=1987|txt}} that uses [[Hash function|hashing]] to find an exact match of a pattern string in a text. It uses a [[rolling hash]] to quickly filter out positions of the text that cannot match the pattern, and then checks for a match at the remaining positions. Generalizations of the same idea can be used to find more than one match of a single pattern, or to find matches for more than one pattern.

To find a single match of a single pattern, the [[expected time]] of the algorithm is [[linear time|linear]] in the combined length of the pattern and text,

One of the simplest practical applications of Rabin-Karp is in detection of plagiarism. Say, for example, that a student is writing an English paper on ''[[Moby Dick]]''. A cunning professor might locate a variety of source material on Moby Dick and automatically extract a list of all sentences in those materials. Then, Rabin-Karp can rapidly search through a particular paper for any instance of any of the sentences from the source materials. To avoid easily thwarting the system with minor changes, it can be made to ignore details such as case and punctuation by removing these first.

although its [[Worst-case complexity|worst-case time complexity]] is the product of the two lengths. To find multiple matches, the expected time is linear in the input lengths, plus the combined length of all the matches, which could be greater than linear. In contrast, the [[Aho–Corasick algorithm]] can find all matches of multiple patterns in worst-case time and space linear in the input length and the number of matches (instead of the total length of the matches).

A practical application of the algorithm is [[plagiarism detection|detecting plagiarism]]. Given source material, the algorithm can rapidly search through a paper for instances of sentences from the source material, ignoring details such as case and punctuation. Because of the abundance of the sought strings, single-string searching algorithms are impractical.

== Shifting substrings search and competing algorithms ==

The basic problem the algorithm addresses is finding a pattern (fixed substring) of length m within a text of length n, for example "sun" in "Hello sunshine in this vale of tears." By way of comparison of the algorithms, a naive brute force string searching algorithm involves aligning the first character of the pattern with the first character of the text and checking if the pattern matches the initial substring of equivalent length. If it does not match, the pattern is shifted right by 1 and the procedure is repeated, for a worst case running time of m*n. [[Knuth-Morris-Pratt algorithm]] is an elegant elaboration on this naive algorithm that uses precomputed data to skip forward not by 1 character, but by as many as possible for the search to succeed.

==Overview==

== Use of hashing for shifting substring search ==

A naive string matching algorithm compares the given pattern against all positions in the given text. Each comparison takes time proportional to the length of the pattern,

Rabin-Karp algorithm takes a very different approach. Rather than pursuing more sophisticated skipping, it seeks to speed up the testing of equality of the pattern to the substrings in the text by using [[hash function|hashing]]. Hashing a string means computing a numerical value from the value of its characters using some standard hash function (a very primitive one could involve adding the [[ASCII]] values of all of its characters together). Rabin-Karp exploits the fact that if 2 strings are equal, their hash values are also equal. Note that the converse of this statement is not valid, although good hash functions seek to reduce the number of such hash collisions. Rabin-Karp computes hash value of the pattern, and then goes through the text computing hash values of all of its substrings and checking whether or not the pattern's hash is equal to the substring hash, and advancing by 1 character every time. If the two numbers are indeed discovered to be equal, then the algorithm has to verify that the two string really are equal, rather than this being a fluke of the hashing scheme. It does so using regular string comparison. It is this verification that in the worst case can drag down algorithm performance down to the level of the naive string search. This general approach is sometimes referred to as the use of a virtual hash table.

and the number of positions is proportional to the length of the text. Therefore, the worst-case time for such a method is proportional to the product of the two lengths.

In many practical cases, this time can be significantly reduced by cutting short the comparison at each position as soon as a mismatch is found, but this idea cannot guarantee any speedup.

Several string-matching algorithms, including the [[Knuth–Morris–Pratt algorithm]] and the [[Boyer–Moore string-search algorithm]], reduce the worst-case time for string matching by extracting more information from each mismatch, allowing them to skip over positions of the text that are guaranteed not to match the pattern. The Rabin–Karp algorithm instead achieves its speedup by using a [[hash function]] to quickly perform an approximate check for each position, and then only performing an exact comparison at the positions that pass this approximate check.

A hash function is a function which converts every string into a numeric value, called its ''hash value''; for example, we might have <code>hash("hello")=5</code>. If two strings are equal, their hash values are also equal. For a well-designed hash function, the inverse is true, in an approximate sense: strings that are unequal are very unlikely to have equal hash values. The Rabin–Karp algorithm proceeds by computing, at each position of the text, the hash value of a string starting at that position with the same length as the pattern. If this hash value equals the hash value of the pattern, it performs a full comparison at that position.

In order for this to work well, the hash function should be selected randomly from a family of hash functions that are unlikely to produce many [[false positive]]s, that is, positions of the text which have the same hash value as the pattern but do not actually match the pattern. These positions contribute to the running time of the algorithm unnecessarily, without producing a match. Additionally, the hash function used should be a [[rolling hash]], a hash function whose value can be quickly updated from each position of the text to the next. Recomputing the hash function from scratch at each position would be too slow.

==The algorithm==

The algorithm is as shown:

<syntaxhighlight lang="php" line highlight="7">

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

</syntaxhighlight>

Lines 2, 4, and 6 each require [[Big-O notation|O]](''m'') time. However, line 2 is only executed once, and line 6 is only executed if the hash values match, which is unlikely to happen more than a few times. Line 5 is executed O(''n'') times, but each comparison only requires constant time, so its impact is O(''n''). The issue is line 4.

Naively computing the hash value for the substring <code>s[i+1..i+m]</code> requires O(''m'') time because each character is examined. Since the hash computation is done on each loop, the algorithm with a naive hash computation requires O(''mn'') time, the same complexity as a straightforward string matching algorithm. For speed, the hash must be computed in constant time. The trick is the variable <code>hs</code> already contains the previous hash value of <code>s[i..i+m-1]</code>. If that value can be used to compute the next hash value in constant time, then computing successive hash values will be fast.

The trick can be exploited using a [[rolling hash]]. A rolling hash is a hash function specially designed to enable this operation. A trivial (but not very good) rolling hash function just adds the values of each character in the substring. This rolling hash formula can compute the next hash value from the previous value in constant time:

<pre>

s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

</pre>

This simple function works, but will result in statement 5 being executed more often than other more sophisticated rolling hash functions such as those discussed in the next section.

Good performance requires a good hashing function for the encountered data. If the hashing is poor (such as producing the same hash value for every input), then line 6 would be executed O(''n'') times (i.e. on every iteration of the loop). Because character-by-character comparison of strings with length ''m'' takes O(''m'') time, the whole algorithm then takes a worst-case O(''mn'') time.

== Hash function used ==

{{main | Rabin fingerprint}}

The key to Rabin-Karp performance is the efficient computation of [[hash value]]s of the successive substrings of the text. Rabin-Karp achieves this by treating every substring as a number in some base, the base being usually a big [[prime]]. For example, if the substring is "hi" and the base is 101, the hash value would be 104 * 101^1 + 105 * 101^0 = 10609 ([[ASCII]] of 'h' is 104 and of 'i' is 105). Technically, this algorithm is only similar to the true number in a non-decimal system representation, since for example we could have the "base" less than one of the "digits". See [[hash function]] for much more detailed discussion. The essential benefit achieved by such representation is that it is possible to compute the hash value of the next substring from the previous one by doing only a finite number of operations, independent of the substrings' length. For example, if we have text "abracadabra" and we are searching for a pattern of length 3, we can compute the hash of "bra" from the hash for "abr" (the previous substring) by subtracting the number added for the first 'a' of "abr", i.e. 97 * 101^2 (97 is ASCII for 'a' and 101 is the base we are using), multiplying by the base and adding for the last a of "bra", i.e. 97 * 101^0 = 97. If the substrings in question are long, this algorithm achieves great savings compared with many other hashing schemes. Theoretically, there exist other algorithms that could provide convenient recomputation, e.g. multiplying together ASCII values of all characters so that shifting substring would only entail dividing by the first character and multiplying by the last. The limitation, however, is the limited of the size of integer [[data type]] and the necessity of using [[modular arithmetic]] to scale down the hash results, for which see [[hash function]] article; meanwhile, those naive hash functions that would not produce large numbers quickly, like just adding ASCII values, are likely to cause many [[hash collision]]s and hence slow down the algorithm. Hence the number in arbitrary base hash function is the preferred one in Rabin-Karp.

The key to the Rabin–Karp algorithm's performance is the efficient computation of [[hash value]]s of the successive substrings of the text. The [[Rabin fingerprint]] is a popular and effective rolling hash function. The hash function described here is not a Rabin fingerprint, but it works equally well. It treats every substring as a number in some base, the base being usually the size of the character set.

For example, if the substring is "hi", the base is 256, and prime modulus is 101, then the hash value would be

[(104 &times; 256 ) %{{efn|name=mod}} 101 + 105] % 101 = 65

([[ASCII]] of 'h' is 104 and of 'i' is 105)

Technically, this algorithm is only similar to the true number in a non-decimal system representation, since for example we could have the "base" less than one of the "digits". See [[hash function]] for a much more detailed discussion. The essential benefit achieved by using a [[rolling hash]] such as the Rabin fingerprint is that it is possible to compute the hash value of the next substring from the previous one by doing only a constant number of operations, independent of the substrings' lengths.

For example, if we have text "abracadabra" and we are searching for a pattern of length 3, the hash of the first substring, "abr", using 256 as the base, and 101 as the prime modulus is:

// ASCII a = 97, b = 98, r = 114.

hash("abr") = [ ( [ ( [ (97 &times; 256) % 101 + 98 ] % 101 ) &times; 256 ] % 101 ) + 114 ] % 101 = 4

We can then compute the hash of the next substring, "bra", from the hash of "abr" by subtracting the number added for the first 'a' of "abr", i.e. 97 &times; 256², multiplying by the base and adding for the last a of "bra", i.e. 97 &times; 256⁰. Like so:

{{pre|style=font-size:95%|1=

// ''old hash (-ve avoider){{efn|name=ua}} old 'a' left base offset base shift new 'a''' prime modulus

hash("bra") = [ ( 4 + 101 - 97 * [(256%101)*256] % 101{{efn|name=mod101}} ) * 256{{efn|name=times256}} + 97 ] % 101 = 30

}}

If we are matching the search string "bra", using similar calculation of hash("abr"),

hash'("bra") = [ ( [ ( [ ( 98 &times; 256) %101 + 114] % 101 ) &times; 256 ] % 101) + 97 ] % 101 = 30

If the substrings in question are long, this algorithm achieves great savings compared with many other hashing schemes.

Theoretically, there exist other algorithms that could provide convenient recomputation, e.g. multiplying together ASCII values of all characters so that shifting substring would only entail dividing the previous hash by the first character value, then multiplying by the new last character's value. The limitation, however, is the limited size of the integer [[data type]] and the necessity of using [[modular arithmetic]] to scale down the hash results.{{efn|See [[hash function]] article.}} Meanwhile, naive hash functions do not produce large numbers quickly, but, just like adding ASCII values, are likely to cause many [[hash collision]]s and hence slow down the algorithm. Hence the described hash function is typically the preferred one in the Rabin–Karp algorithm.

== Multiple pattern search ==

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 algorithm]]s because of its slow worst case behavior. However, it is a useful algorithm for [[String searching algorithm#Algorithms using a finite set of patterns|multiple pattern search]].

To find any of a large number, say ''k'', fixed length patterns in a text, a simple variant of the Rabin–Karp algorithm 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:

<syntaxhighlight lang="php" line>

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

</syntaxhighlight>

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 above algorithm can find all ''k'' patterns in O(''n''+''km'') expected time, assuming that a hash table check works in O(1) expected time.

==Notes==

{{notelist|refs=

{{efn|name=mod|{{char|%}} is 'mod' or [[modulo]], or remainder after integer division, operator.}}

{{efn|name=ua|1=(-ve avoider) = "underflow avoider". Necessary if using unsigned integers for calculations. Because we know all hashes <math>h \leq p</math> for prime modulus {{mvar|p}}, we can ensure no underflow by adding {{mvar|p}} to the old hash before subtracting the value corresponding to the old 'a' (mod {{mvar|p}}).}}

{{efn|name=times256|the last {{code|* 256}} is the shift of the subtracted hash to the left.}}

{{efn|name=mod101|although {{code|((256%101)*256)%101}} is the same as 256² mod 101, to avoid overflowing integer maximums when the pattern string is longer (e.g. 'Rabin-Karp' is 10 characters, 256⁹ is the offset without modulation ), the pattern length base offset is pre-calculated in a loop, modulating the result each iteration.}}

}}

==References==

{{Reflist}}

===Sources===

== Rabin-Karp and multiple pattern search ==

* {{cite book| first1 = K. Selçuk | last1 = Candan | first2 = Maria Luisa | last2 = Sapino|title=Data Management for Multimedia Retrieval|url=https://books.google.com/books?id=Uk9tyXgQME8C&pg=PA205| date = 2010|publisher=Cambridge University Press|isbn=978-0-521-88739-7|pages=205–206}} (for the Bloom filter extension)

Rabin-Karp is inferior to [[Knuth-Morris-Pratt algorithm]], [[Boyer-Moore string searching algorithm]] and other faster single pattern [[string searching algorithm]]s because of its slow worst case behavior. However, Rabin-Karp is an algorithm of choice for multiple pattern search. That is, if we want to find any of a large number, say k, fixed length patterns in a text, a variant Rabin-Karp that uses a [[hash table]] to check whether the hash of a given string belongs to a set of hash values of patterns we are looking for. Other algorithms can search for a single pattern in time order O(n), hence they will search for k patterns in time order O(n*k). The variant Rabin-Karp will still work in time order O(n) in the best and average case because a hash table allows to check whether or not substring hash equals any of the pattern hashes in time order of O(1).

* {{Cite book | last1 = Cormen | first1 = Thomas H. | author-link1 = Thomas H. Cormen | author-link2 = Charles E. Leiserson | last2 = Leiserson | first2 = Charles E. | author-link3 = Ronald L. Rivest | last3 = Rivest | first3 = Ronald L. | author-link4 = Clifford Stein | last4 = Stein | first4 = Clifford |title=[[Introduction to Algorithms]] |orig-year=1990 |edition=2nd |date=2001-09-01 |publisher=MIT Press |___location=[[Cambridge, Massachusetts]] |isbn=978-0-262-03293-3 |pages=911–916 |chapter=The Rabin–Karp algorithm}}

* {{Cite journal |last1=Karp|first1= Richard M. | author-link=Richard Karp | last2=Rabin|first2=Michael O.|author2-link=Michael O. Rabin | title=Efficient randomized pattern-matching algorithms |date=March 1987 |journal=IBM Journal of Research and Development |volume=31 |issue=2|pages=249–260|doi=10.1147/rd.312.0249 |citeseerx = 10.1.1.86.9502}}

==External links==

*{{cite web | url = http://courses.csail.mit.edu/6.006/spring11/rec/rec06.pdf | work = MIT 6.006: Introduction to Algorithms 2011- Lecture Notes | title = Rabin–Karp Algorithm/Rolling Hash | publisher = MIT }}

{{Strings}}

* [http://www.research.ibm.com/journal/rd/312/ibmrd3102P.pdf Karp and Rabin's original paper]

{{DEFAULTSORT:Rabin-Karp String Search Algorithm}}

[[Category:Algorithms on strings]]

[[Category:String matching algorithms]]

[[Category:Hashing]]