STR Strings and text Technique
Polynomial hash
Also known as: polynomial rolling hash · rolling hash · string hashing · prefix hashes · anti-hash test
A string is turned into a number: the value of a polynomial whose coefficients are the letter codes, modulo a large prime. Having computed such numbers for all prefixes of a string, you compare any two pieces in O(1), find the length of the common prefix of two places in a text in O(log n), and roll a window’s hash along the text in one operation per letter. The price is a probability of error: you need to know how to compute it and how to keep it out of an adversary’s hands.
Cut Part One of War and Peace (the Russian original) into all its pieces of 16 consecutive letters: there are 244,485 of them, 238,589 different. Compute the hash of each modulo 10⁹ + 7, the competitive programmers’ favourite modulus. A hash is a number from zero to a billion, and there are four thousand times fewer pieces than possible hashes. Nevertheless, 29 pairs of different pieces got equal hashes. «Мои дети — ce so» and «росилась между к», two arbitrary 16-character pieces, both give 498,024,809. Switch the modulus and the piece length, try another base: the number of collisions hardly depends on the base but depends a great deal on the modulus.
The black mark on each bar is the expectation: if hashes behave like random numbers, among k different pieces there are on average k(k − 1)/(2p) pairs with equal hashes. With p = 10⁹ + 7 that is 28.46, and 29 were found. With p = 65,537, 434,293 and 434,210. The calculation matches the experiment for all moduli: the hash really does scatter the novel’s pieces like a lottery. That is not what is bad; what is bad is that Part One has 28 billion pairs of pieces, and even a billion possible values cannot hold them. With the modulus 2⁶¹ − 1 about one hundred-millionth of a pair is expected, and none was found.
A hash compares strings in one operation but sometimes errs. This article is about how to set it up so that it errs rarely and predictably, and how to stop an adversary from making it err every time.
The idea
Let us read a string as a number written in base b, with the letter codes as digits. Then the number of any piece is obtained from the numbers of two prefixes of the string: from the number of the long prefix subtract the number of the short one, shifted by the right number of digits. To keep the numbers from growing, everything is computed modulo a large prime p. Equal pieces always give equal numbers, different ones almost never.
The polynomial hash of a string s = s₀s₁…sm−1 is
$$h(s) = \bigl(s_0 b^{m-1} + s_1 b^{m-2} + \dots + s_{m-1}\bigr) \bmod p.$$It is convenient to compute it by Horner’s scheme: multiply the accumulated value by b, add the code of the next letter, take the remainder. If the hashes of all prefixes of the string are recorded, with H[i] the hash of the first i letters, then
$$h(s[l..r)) = \bigl(H[r] - H[l]\cdot b^{\,r-l}\bigr) \bmod p.$$This is one line of arithmetic: H[r] is a number of r digits, its top l digits are H[l] shifted by r − l places, and the bottom ones are exactly the piece. The powers of b are needed too, and they are also computed in advance. Check the formula by hand: the modulus here is 1009, the base 31, and under each letter is the hash of the prefix up to and including it.
The two pieces «абра» at the start and end of «абракадабра» (abracadabra in Cyrillic) give 542, although they are computed from quite different numbers: 542 − 0 · 31⁴ and 451 − 229 · 31⁴. Press “Find a collision”: «абракада» and «адабр» both give 99 as well. With the modulus 1009 there are only a thousand hashes, and they repeat even on an eleven-letter word. Switch to 10⁹ + 7, and the collision disappears.
A window moving along the text is updated the same way. To get the hash of the next piece from the hash of s[i..i + m), subtract the contribution of the departing letter si · bm−1, shift by one digit and add the arriving letter: (h − si · bm−1) · b + si+m modulo p. Three operations per letter for any window length: the Rabin–Karp algorithm rests on this.
Why collisions are rare
Let p be a prime larger than the code of any letter, and let the base b be chosen at random with equal probability from 0, 1, …, p − 1. Then two different strings of length L get the same hash with probability at most (L − 1)/p.
The hash of a string is the value of the polynomial s₀xL−1 + … + sL−1 at the point x = b modulo p. The hashes of two strings coincide when the difference of their polynomials vanishes at b. The strings differ and the codes are less than p, so at least one coefficient of the difference is not divisible by p: it is a nonzero polynomial of degree at most L − 1. The residues modulo a prime form a field, and a nonzero polynomial over a field has no more roots than its degree. So there are at most L − 1 “bad” bases out of p.
The same theorem, and the experiment with salt for hash tables, are in the course chapter on hashing. Two consequences matter here.
A single comparison is almost safe. For pieces of a thousand letters and p = 10⁹ + 7 the probability of error is below one in a million. If there are q comparisons, the probability of at least one error is at most q(L − 1)/p: the error probabilities add up.
Many pieces against each other are dangerous. If you need to find equal ones among k pieces, all pairs are compared, and there are k²/2 of them. This is the birthday problem: the expected number of false matches is about k²/(2p). With p = 10⁹ + 7 and ten thousand pieces that is 0.05, with a hundred thousand already 5, and in Part One of the novel, with 238 thousand pieces, 29. For such tasks a modulus of the order of 2⁶¹ or two moduli at once are used; then even a hundred million pieces give 0.002 false pairs on average.
In the work of Karp and Rabin, written in 1981 and published in 1987, it was not the base but the modulus that was random: a binary string was read as a number and taken modulo a random prime. The bound there is different (how many primes can divide the difference of two numbers), but the meaning is the same: the adversary does not know what exactly will be computed. Today it is more common to fix a prime modulus and choose a random base: the bound is simpler and the arithmetic faster.
Code
PrefixHash stores the prefix hashes and the powers of the base, get is the formula from the section above, lcp is a binary search for the length of the common prefix (the next section is about it), and window_hashes is a window rolling along the text. The default modulus is 2⁶¹ − 1. Python computes with long integers and knows no overflow. In Go the product of two residues modulo such a number does not fit in 64 bits: mulmod takes the 128-bit product from bits.Mul64 and the remainder from bits.Div64. C++ has __int128 for this, or a trick for primes of the form 2k − 1: the remainder of x divided by 2⁶¹ − 1 equals (x >> 61) + (x & (2⁶¹ − 1)), with one subtraction of the modulus at the end if the sum came out larger than it.
The first lines of output are the «абракадабра» example, the same numbers as in the scene. Then four moduli on the novel’s pieces, as in the first scene, and the first three pairs of different pieces with equal hashes modulo 10⁹ + 7. The base is 9,873,241, one for all moduli, reduced for the small ones. With another base the pairs will be different, and their number again close to the expected.
How far two places agree
If the first k letters from positions i and j agree, the first k − 1 agree too. Such a condition is checked by binary search: the length of the common prefix is found in log₂ n hash comparisons, each in O(1). In Part One of the novel the phrase «Пьер ничего» occurs at positions 165,602 and 189,222, and the function lcp from the listing replies that 22 letters agree from there: «Пьер ничего не понимал» (Pierre understood nothing). The same phrase twice, more than twenty thousand characters apart.
A lot rests on the common prefix.
- Comparing pieces alphabetically. Find the length of the common prefix and compare the next letter. Sorting all suffixes of a text with this comparison gives a suffix array in O(n log² n).
- Palindromes. Compute prefix hashes for the reversed string too: a piece is a palindrome if its hash equals the hash of the same piece read right to left. The longest palindrome centred at a given point is binary search again.
- Period. A string of length n has period q if its prefix of length n − q equals its suffix of the same length: one hash comparison per candidate.
- How many comparisons brute force makes. The problem “The comparison counter” from the article on naive search needs the length of the common prefix of the pattern with each place in the text; it is solved with the Z-function, but a hash with binary search will do too.
What it costs
| Operation | Time | Probability of error |
|---|---|---|
| prefix hashes and powers | O(n), memory O(n) | — |
| the hash of a piece | O(1) | — |
| are two pieces of length L equal | O(1) | ≤ (L − 1)/p, only a “yes” can be false |
| the length of the common prefix of two places | O(log n) | ≤ (n − 1) log₂ n / p |
| the window moved by one letter | O(1) | — |
The error is always one-sided: different hashes always mean different pieces, and equal hashes almost always mean equal ones. If an error is unacceptable, a match is checked letter by letter. That costs O(L), but only on matches, and there are usually few of them.
The measurement: the text abab… of length n and fifty pairs of positions where it agrees almost to the end. The length of the common prefix, letter by letter and by binary search on hashes.
Letter by letter, the time grows with n, slope 1. Binary search on hashes hardly notices the length: with a text of 65,536 letters it is more than four hundred times faster in Python and about three hundred in Go. On prose the picture is reversed: two random places in the novel diverge at the first or second letter, and the letter comparison finishes before binary search makes its first step. A hash is needed where common pieces are long: repeats, periods, comparing almost identical strings.
Where it breaks: the modulus 2⁶⁴
The most tempting implementation is to take no remainder at all. If you compute in 64-bit unsigned numbers, overflow takes the remainder modulo 2⁶⁴ by itself, and the hash comes out fast and seemingly reliable: 18 quintillion values. But 2⁶⁴ is not a prime, the theorem about roots does not work here, and there is a pair of strings whose hashes coincide for any odd base.
Thue–Morse strings are built by doubling: from S = a and T = b we get S → ST, T → TS: abba and baab, abbabaab and baababba, and so on. Move the length and watch the low bits of the difference of the hashes.
Let Sk and Tk be the Thue–Morse strings of length 2k, and let the base b be odd. Then the difference of their polynomial hashes is divisible by 2 to the power 1 + (k − 1)(k + 4)/2. For k = 10, that is, on strings of 1024 letters, this is 2⁶⁴: the hashes modulo 2⁶⁴ coincide.
The hash of a concatenation XY equals h(X) · b|Y| + h(Y). Denote Dk = h(Sk) − h(Tk) and N = 2k. Then
$$D_{k+1} = h(S_k)\,b^N + h(T_k) - h(T_k)\,b^N - h(S_k) = D_k\,(b^N - 1),$$and D₀ = a − b = −1. So Dk = −(b − 1)(b² − 1)(b⁴ − 1)…(b2k−1 − 1). For odd b the factor b − 1 is even. The square of an odd number leaves remainder 1 when divided by 8, so b² − 1 is divisible by 8. And each next factor is divisible by 2 at least once more than the previous one: b2t − 1 = (bt − 1)(bt + 1), and the second factor is even. In total the power of two in Dk is at least 1 + 3 + 4 + … + (k + 1) = 1 + (k − 1)(k + 4)/2. For k = 10 this is 64.
The listing below checks this for the base 131: the trailing zeros of the difference are 1, 4, 8, 13, 19, 26, 34, 43, 53, and at the tenth step all 64, exactly as estimated. The same 1024-letter strings have equal hashes with the bases 3, 31, 10⁹ + 7 and a random 64-bit odd one, but not modulo 2⁶¹ − 1. A random base does not save you here: the polynomial (x − 1)(x² − 1)…(x⁵¹² − 1) modulo 2⁶⁴ vanishes at every odd point, and the theorem about at most L − 1 roots does not work because 2⁶⁴ is not a prime. An even base is worse still: 256⁸ = 2⁶⁴, and with the base 256 only the last eight letters remain in the hash, so «войнаabcdefgh» and «мирabcdefgh» (“war” and “peace” followed by abcdefgh) coincide.
The same goes for 32-bit hashes. The estimate gives 2³² already at k = 7: any two 128-letter Thue–Morse strings have equal hashes under Java’s String.hashCode and under the hash with which strings.Index in Go searches for long patterns. In Go this is not a bug, just extra work: the search checks a hash match by comparing strings.
In olympiads Thue–Morse strings are the standard test against a hash without a modulus, and a solution with unsigned long long gets a wrong answer on it with any base. If the base and modulus are known in advance, a collision for a prime modulus around 10⁹ is also found quickly: by the birthday problem a few tens of thousands of random strings are enough. This is the problem “Break the hash” below. The defence is a prime modulus of the order of 2⁶¹ or two moduli, and a base the program chooses at random at start-up.
Where it works
- Pattern search. The Rabin–Karp algorithm rolls a window’s hash along the text and compares letters only where the hash matched the pattern’s. In Go
strings.Indexsearches this way when the first-byte filter misfires often: base 16,777,619, modulus 2³², matches checked by comparing strings. - Content-defined chunks. The LBFS network file system (2001) rolled a 48-byte window along a file and declared a chunk boundary where the window’s fingerprint had 13 zero low bits. An insertion at the start of a file changes only the chunk it lands in: the other boundaries stay where they were relative to the content, and the other chunks need not be sent again. The restic backup program uses the same trick. The fingerprint here is a Rabin fingerprint: a polynomial with coefficients 0 and 1 modulo a random irreducible polynomial, that is, the same idea in binary arithmetic without carries.
- Rolling sums. rsync also rolls a window along a file, but instead of a polynomial it has a pair of sums modulo 2¹⁶, a plain sum of bytes and a weighted sum. That is how Andrew Tridgell and Paul Mackerras described it in 1996, modelled on the Adler-32 checksum.
- Olympiads. Comparing substrings, palindromes, periods, common pieces of two strings, repeats: many problems where the honest algorithm is a suffix tree or automaton are solved with hashes faster than the honest algorithm can be written.
History
In 1981 Michael Rabin described “fingerprinting by random polynomials”: a string of bits is read as a polynomial and taken modulo a random irreducible polynomial. In the same year, together with Richard Karp, he wrote a paper on pattern search by fingerprints, published in 1987 in the IBM Journal of Research and Development: a window rolls along the text, the fingerprint is updated in constant time, and the probability of error is bounded via a random choice of modulus. The strings that break a hash modulo a power of two are much older. The sequence of doublings a → ab, b → ba was studied by Eugène Prouhet as early as 1851 in number theory; Axel Thue built a combinatorics of words on it in 1906, and Marston Morse applied it to geometry in 1921.
Problems
In the first problem you must answer hundreds of thousands of questions “are these two pieces of text identical”, and the tests include Thue–Morse strings. In the second the roles are reversed: given a base and a modulus, build two different strings with the same hash.
Equal pieces Break the hashData: War and Peace by Leo Tolstoy, public domain