The Rabin–Karp algorithm

The scenes of this catalogue are written by different authors, and sometimes a function moves from file to file by copying. Let us find all such pieces. Every 60-character window of every file, more than six hundred thousand windows, gets a fingerprint, a polynomial hash, and windows with equal fingerprints in different files are compared letter by letter. On the left is a matrix: how much of each file occurs in each other one. On the right, two files against each other: a dot is a common window, a copied piece is a diagonal. Tap the cells of the matrix, change the window length and the modulus.

Take the pair that opens first: dijkstra.js, the scene of the article on Dijkstra’s algorithm, and dynamic-programming-intro.js, the scene of the introductory article on dynamic programming. Of the first file’s 20,213 windows, 2750 occur in the second; they add up to 32 pieces, 4638 characters in all. The longest, 528 characters, is the function marker, which draws a pin with the letter A or B on a map. The second, 426 characters, places labels on a map so that they do not overlap. The third, 381 characters, is a private toggle seg, although the site’s shared library already has such a function. This is exactly the report of a copy finder: what to move into a shared module.

Look at the counter of false alarms. Even with the modulus 2³¹ − 1 one turned up: two different windows of these files got the same fingerprint. Switch the modulus to 10⁵ + 3: the common windows are just as many, 2750, but there are now 4300 false alarms, different windows with the same fingerprint. The letter check catches each of them, so the answer does not change; only the work does. That is how the whole Rabin–Karp algorithm works: the hash quickly sifts out almost everything, and letters are compared only where it said “maybe”.

The idea

Compare not the window of text with the pattern but its fingerprint, a number. The fingerprint of a window shifted by one letter is obtained from the previous one in three operations: remove the contribution of the letter that left, multiply by the base, add the letter that arrived. Where the fingerprints differ, the window is certainly not the pattern. Where they are equal, the window is very likely the pattern, and that is checked letter by letter. There can be many patterns: their fingerprints go into a hash table, and the same single pass over the text searches for all of them at once.

The fingerprint is a polynomial hash: the window t_s…t_s+m−1 is read as a number in base b and taken modulo a prime p. If h_s is the fingerprint of the window at position s, then

The power b^m−1 modulo p is computed once in advance. A match of h_s with the pattern’s fingerprint is called a hit, and a hit where the letters nevertheless differ is a false alarm.

The window rolls along the text

Below, a six-letter window searches for «Наташа» (Natasha) in a short excerpt of Part One of War and Peace in the original Russian, where the name occurs three times. Under each letter is a bar for the window that starts there. The modulus can be made absurdly small, 13 or 101, so that the false alarms are visible to the eye.

With p = 13 a fingerprint is a number from 0 to 12, and a window gets the fingerprint of «Наташа» in roughly one case in thirteen. The listing below runs the search over the whole of Part One of the novel, 244,495 windows:

           p  found  hash hits  false  expected false
          13     42      18686  18644         18804.1
         101     42       2537   2495          2420.3
       10007     42         54     12            24.4
  2147483647     42         42      0             0.0

There are always 42 occurrences: the letter check makes mistakes impossible. Only the number of false alarms changes, and it follows the formula: about (number of windows − number of occurrences)/p. With the modulus 2³¹ − 1 there is not a single false alarm, and letters are compared only where «Наташа» really is.

Why it is correct and fast

The worst case does not disappear: if the pattern is aaa and the text aaa…a, every window is an occurrence, and the check costs n · m, like naive search. But this work is needed only to confirm occurrences. If the answer “probably yes” is enough for you, the check can be dropped: then the time is always O(n + m), but the answer may be false with a probability the theorem bounds. The first variant is a Las Vegas algorithm, always correct and usually fast; the second is Monte Carlo, always fast and usually correct (more in Las Vegas and Monte Carlo).

Code

First, a search for one pattern with two counters, hits and false alarms. The modulus here is below 2³¹, so the product of two residues fits in a 64-bit integer, and Go does without 128-bit arithmetic.

Now the copies. common_windows puts all the windows of the first file into a dictionary “fingerprint → positions”, rolls the windows of the second past it, and for each hit compares letters. It is the same algorithm, only with twenty-nine thousand patterns instead of one: all the windows of the first file. Neighbouring common windows are joined into pieces. Before comparing, spaces, indentation and line breaks are squeezed into a single space: a copy with different indentation is still a copy.

Many patterns in one pass

For a single pattern Rabin–Karp is rarely the best choice: KMP is linear without any probabilities, and the built-in search with its filters is faster than both. But if there are a thousand patterns, other methods search for them one by one, passing over the text a thousand times. Rabin–Karp needs one pass: at each window it checks whether its fingerprint is in the hash table of the patterns’ fingerprints, and that costs O(1) however many patterns there are.

The measurement: Part One of the novel, from one to ten thousand patterns of 16 letters each, each taken from the same text. One series is Rabin–Karp with a table of fingerprints, the other the built-in search called for each pattern in turn (str.count and strings.Count).

The built-in search grows more expensive in step with the number of patterns. A Rabin–Karp pass costs almost the same for one pattern and for ten thousand. In Python the loop over letters is slow, and the built-in search, written in C, wins while there are fewer than a few thousand patterns; at ten thousand the Rabin–Karp pass is already three times faster. In Go the break-even point is about ten patterns.

There is a limitation: a window of one length finds patterns of only that length. If the lengths differ, there are as many passes as distinct lengths, or you need the Aho–Corasick automaton, which finds patterns of any length in one pass without any probabilities.

How copies are found

Programs that find copied code work like the second scene, only more carefully. PMD CPD, the copy detector from the PMD analyser suite, has gone through three algorithms: first Michael Wise’s greedy string tiling, then the Burrows–Wheeler transform, and Steve Hawkins built the current version on the Karp–Rabin algorithm. jscpd splits files into tokens by the rules of each language and looks for repeated token sequences with a Rabin–Karp rolling hash. Tokens instead of characters give something important: code can be compared ignoring spaces and comments, and if you like, variable names too, and then copies in which everything was renamed are found.

The dot plot from the scene is an old way of seeing repeats. Biologists draw the comparison of two DNA sequences this way, and the book “Object-Oriented Reengineering Patterns” recommends the same picture for finding copied code: a diagonal of dots is a copied piece. Short parallel segments off the diagonal are common idioms, for example identical import lines.

If you need to compare not two files but every new submission against a whole archive, keeping the fingerprints of all windows is expensive. Then a sample of fingerprints is kept, chosen so that any common piece longer than a threshold leaves at least one common fingerprint: this is the winnowing of Schleimer, Wilkerson and Aiken from 2003, on which MOSS, the system for detecting copying in programs, runs. How it works is in the course chapter “A needle in a haystack”. And if what you need are not exact copies but nearly identical documents, window fingerprints are compared as sets: that is MinHash.

What it costs

Memory is O(1) for one pattern and O(k) for the table of fingerprints. The worst case is when almost every window has to be compared letter by letter: either there are very many occurrences, or an adversary has picked strings with the same fingerprint. A random base and a prime modulus protect against the second; nothing protects against the first, but then the answer itself consists of n occurrences. The last row of the table is the problem below: if there is a common piece of length L, there is one of length L − 1 too, so the length is found by binary search on the answer, and each check is done by Rabin–Karp.

Where else it works

• Go’s standard library. strings.Index searches for long patterns with a first-byte filter, and if the filter misfires often it switches to Rabin–Karp: base 16,777,619, modulus 2³², hits checked by comparing strings. On Russian text this happens almost at once, since every Cyrillic letter in UTF-8 has the first byte D0 or D1; see the article on naive search.
• Two-dimensional search. Karp and Rabin noticed at once that the method carries over to pictures: the fingerprint of a window’s row rolls along the row, and the fingerprints of rows are combined into the fingerprint of a rectangle by the same trick along the columns.
• Comparing large files. Fingerprints of pieces are cheaper to send and store than the pieces themselves: systems that find identical fragments in archives and backups rely on this; more in the article on the polynomial hash.

History

Richard Karp and Michael Rabin described fingerprint search in a technical report in 1981, and the journal paper appeared in 1987 in the IBM Journal of Research and Development under the title “Efficient randomized pattern-matching algorithms”. They read a string of bits as a number and took the remainder modulo a random prime; the probability of error depended on the choice of prime. In those years Rabin worked a great deal on algorithms that use randomness: the probabilistic primality test, the Miller–Rabin test, was published in 1980. By then both authors had already received the Turing Award: Rabin in 1976 together with Dana Scott for nondeterministic automata, Karp in 1985 for work on algorithms and NP-completeness.

Problems

The problem asks for the longest piece common to two texts, for example to two scenes of this catalogue. For one length it is Rabin–Karp with a table of fingerprints, and binary search finds the length.