Algorithms · Lecture Notes
Chapter 9: String Matching and Compression
Searching for a word with Ctrl+F in a text editor, a virus scanner looking for known signatures, and a gene being located in a DNA sequence are all instances of one problem: find where a short string occurs inside a long text. These notes present four classical solutions. The brute-force algorithm tries every position in turn. The Knuth-Morris-Pratt algorithm stores what it learns from the matched part in a table and never moves backward in the text. The Boyer-Moore algorithm compares the pattern from right to left and skips most of the text without reading it. The Rabin-Karp algorithm compares hash values instead of characters. The second half of the notes is about string compression. Run-length encoding (RLE) writes consecutive repeats as a count. Lempel-Ziv-Welch (LZW) replaces repeated substrings with short codes from a dictionary that grows as it goes. Every algorithm is run step by step on an example, its Java code is traced line by line, and its cost is derived.
Learning outcomes
- Concepts
- Define text, pattern, shift, prefix, and suffix; state the string matching problem formally.
- Matching
- Run the brute-force, KMP, Boyer-Moore, and Rabin-Karp algorithms by hand on an example and trace their Java code.
- Analysis
- Explain the time saved by the LPS table, the bad-character table, and the rolling hash; compare best, average, and worst cases; choose an algorithm to fit the problem.
- Compression
- Compress losslessly with RLE and LZW, decompress the result, handle the special case in LZW decoding, and compute the compression ratio.
9.1The string matching problem
Most of the data computers process is text: e-mail, messages, social media posts, news articles, program source code, log files. The operation performed most often on such text is search. We find where a word occurs, replace one phrase with another, or measure how similar two texts are. Algorithms that do this kind of work are called string algorithms. This chapter has two main topics: finding a pattern in a text (string matching) and storing a text in less space (string compression). This section defines the matching problem and sets up the notation.
9.1.1Text search is everywhere
String matching is built into everyday software. Ctrl+F in a text editor, Unix's grep command, and the indexes of search engines are the best-known examples. There are less visible uses as well. Virus scanners look for the byte sequences (signatures) of known malware inside files. Plagiarism detectors find long passages that two documents share. In bioinformatics, one asks where a gene or a short DNA fragment occurs in a sequence of millions of letters.
Compression is just as common. ZIP archives, GIF and PNG images, PDF documents, and fax machines all rely on string algorithms to store data in fewer bits. Most of these methods are also a kind of search at heart: they find a repeat of something seen earlier and replace it with a short reference.
In these applications the texts are large. A log file can run to gigabytes, and a human genome is about three billion letters long. The number of times an algorithm reads each character therefore determines its running time directly. All the algorithms in this chapter answer the same question. They differ in how many comparisons they need to do so.
9.1.2Basic concepts and notation
Strings are built from a set of characters called the alphabet, written Σ. For lowercase English letters Σ = {a, b, …, z}, for DNA Σ = {A, C, G, T}, and for binary data Σ = {0, 1}. The size of the alphabet is written σ = |Σ|. The speed of some algorithms depends on this number.
The long string being searched is the text, and the short string being sought is the pattern. We write the text as T[0..n−1] and the pattern as P[0..m−1]. So n is the length of the text, m is the length of the pattern, and usually m ≤ n. Indices start at 0, as in Java. In code the text is called t and the pattern p; t.charAt(i) corresponds to T[i].
Aligning the pattern so that its first character lies under position s of the text is called a shift. If T[s..s+m−1] = P, then P occurs in T with shift s, and s is a valid shift. Since the pattern cannot stick out past the end of the text, the possible shifts are 0 ≤ s ≤ n − m; there are n − m + 1 of them in all.
The string matching problem is to find all the shifts (or only the first one) at which P occurs in T.
Most of these algorithms are built on the beginning and the end of the pattern. A piece taken from the start of a string is a prefix, and a piece taken from the end is a suffix. The prefix of P of length k is P[0..k−1], and its suffix of length k is P[m−k..m−1]. The string itself is both a prefix and a suffix of itself. A prefix that is not equal to the whole string is a proper prefix, and a suffix that is not equal to the whole string is a proper suffix.
Let P = "ababd" (m = 5). Its proper prefixes are a, ab, aba, and abab; its proper suffixes are d, bd, abd, and babd. The empty string also counts as both a prefix and a suffix, but it is mostly useless in exercises. This pattern has no nonempty piece that is both a proper prefix and a proper suffix: every suffix ends in d, and no proper prefix does.
If the same pattern is searched for in the text T = "ababcababd" (n = 10), the possible shifts are 0, 1, …, 5. Only at s = 5 does T[5..9] = "ababd" = P hold. The only valid shift is 5.
Comparing two characters has one of two outcomes. If the characters are equal there is a match; if they differ there is a mismatch. In the figures of these notes, matching characters are drawn in green boxes and mismatching ones in red boxes. The cost of an algorithm is usually measured by the total number of character comparisons. This is a countable quantity that does not depend on the machine or the language.
9.1.3A map of the algorithms
The chapter covers six algorithms. The first four are for matching and the last two are for compression:
- Brute force (also called naive): every position in the text is checked separately for a match with the pattern. This method can make the most comparisons.
- Knuth-Morris-Pratt (KMP): before searching, a table (the LPS table) is built from the pattern. During the search the algorithm never moves backward in the text; even in the worst case the running time is linear.
- Boyer-Moore: comparison goes from right to left. The bad-character and good-suffix rules give long jumps, which makes it very effective on long patterns.
- Rabin-Karp: hash values are compared instead of characters. As the window slides, the hash is updated in O(1) time; the algorithm is fast in the expected case.
- Run-length encoding (RLE): consecutive repeated values are stored as one value and a repeat count.
- Lempel-Ziv-Welch (LZW): dictionary-based compression. Repeated substrings are represented by short codes from a dictionary that grows during compression. The GIF format uses this method.
All the matching algorithms produce the same output. What separates them is what they do at a mismatch. Brute force learns nothing from a mismatch and slides the pattern by one position. KMP uses the structure of the part already matched to skip useless shifts. Boyer-Moore looks at where the mismatched text character occurs in the pattern. Rabin-Karp makes the comparison itself cheaper. These four points of view also explain why the same problem has more than one solution.
9.2The brute-force algorithm
The brute-force algorithm is the simplest way to search for a pattern in a text. Its other name, "naive," comes from this simplicity. The algorithm does no preprocessing and uses no extra memory. That makes it both the yardstick against which the other algorithms are compared and a practical method still used for short patterns.
9.2.1How it works
The algorithm tries every possible shift in order, from left to right:
- Alignment. For each shift s = 0, 1, …, n − m, the pattern is placed under the text with its first character under T[s].
- Comparison. P[0] is compared with T[s], P[1] with T[s+1], and so on from left to right. The check of this alignment ends at the first mismatch.
- Decision. If all m characters match, s is reported. Otherwise the pattern is shifted one position to the right and the next shift is tried.
The number of comparisons depends on the text and the pattern. In the worst case all m characters are compared at every alignment: (n − m + 1) · m comparisons, that is, O(n · m). In the best case the first character mismatches at every alignment: n − m + 1 comparisons, that is, O(n).
9.2.2Example: searching for SIMPLE
Figure 9.3 shows the search for the pattern "SIMPLE" (m = 6) in the text "THIS IS A SIMPLE EXAMPLE" (n = 24). Each row is one shift. The space character is shown with the symbol ␣.
The algorithm starts at s = 0. At shifts s = 0, 1, …, 9, either the first character S of the pattern mismatches the text character, or only the S matches. At s = 3, T[3] = S matches, and then T[4] = ␣ mismatches I. The same happens at s = 6: S matches and ␣ mismatches. All other shifts end at the first comparison. At s = 10, all six characters match. Table 9.1 counts the comparisons shift by shift.
| Shift s | Aligned part of the text | Result | Comparisons |
|---|---|---|---|
| 0, 1, 2 | THI…, HIS…, IS␣… | first character ≠ S | 3 × 1 = 3 |
| 3 | S␣IS␣A | S matches, ␣ ≠ I | 2 |
| 4, 5 | ␣IS…, IS␣… | first character ≠ S | 2 × 1 = 2 |
| 6 | S␣A␣SI | S matches, ␣ ≠ I | 2 |
| 7, 8, 9 | ␣A…, A␣…, ␣SI… | first character ≠ S | 3 × 1 = 3 |
| 10 | SIMPLE | 6 characters match: found | 6 |
| Total (11 alignments) | 18 | ||
The total of 18 comparisons is close to the length of the text (24). The reason is that in natural-language text two random characters are usually different, so a mismatch typically occurs at the first character. This observation is why brute force often runs at acceptable speed in practice.
9.2.3Java code and trace
The Java code of the algorithm consists of two nested loops. The outer loop runs over the shifts and the inner loop walks over the characters of one alignment. The method returns the position of the first occurrence, or −1 if the pattern does not occur.
int bruteForce(String t, String p) {
int n = t.length(), m = p.length();
for (int i = 0; i <= n - m; i++) {
int j = 0;
while (j < m &&
t.charAt(i + j) == p.charAt(j))
j++;
if (j == m) return i;
}
return -1;
}The code reads line by line as follows:
- Outer loop:
iis the shift and runs from 0 ton - m. The condition isi <= n - mbecause the last valid shift is n − m. The valuei + jis at most n − m + m − 1 = n − 1, so the code never reads outside the string. - Inner loop:
jis the number of characters matched at this alignment. It increases as long asj < mand the characters are equal. The order of the two conditions matters: the&&operator evaluates the second condition only if the first is true. So whenj == m,p.charAt(m)is never called. - Decision: if the inner loop ended with
j == m, every character matched andiis returned. If it ended earlier, there was a mismatch and the outer loop moves on to the next shift.
Let us trace the code with the call bruteForce("HELLO WORLD", "LO"). Here n = 11 and m = 2, and the shifts are i = 0, 1, …, 9. Table 9.2 lists every comparison in order.
| Step | i | j | Comparison | Result |
|---|---|---|---|---|
| 1 | 0 | 0 | t[0] = 'H' with p[0] = 'L' | mismatch; pattern shifts by 1 |
| 2 | 1 | 0 | t[1] = 'E' with p[0] = 'L' | mismatch; pattern shifts by 1 |
| 3 | 2 | 0 | t[2] = 'L' with p[0] = 'L' | match; j = 1 |
| 4 | 2 | 1 | t[3] = 'L' with p[1] = 'O' | mismatch; pattern shifts by 1 |
| 5 | 3 | 0 | t[3] = 'L' with p[0] = 'L' | match; j = 1 |
| 6 | 3 | 1 | t[4] = 'O' with p[1] = 'O' | match; j = 2 = m |
| 7 | 3 | 2 | — | j == m: returns 3 |
In all, 6 comparisons are made. Look at steps 4 and 5: T[3] = 'L' is read twice. The first time it is compared with the second character of the pattern, and then with the first. This is the basic flaw of brute force: when the pattern shifts, the algorithm goes back in the text and reads the same characters again.
The memory cost is O(1); only i, j, n, and m are stored. If all occurrences are wanted, i is added to a list instead of executing return i, and the loop continues; the complexity does not change.
Writing the outer loop condition as i < n - m. This skips the last shift (s = n − m). For example, in the call bruteForce("kalem", "em") the correct shifts are 0, 1, 2, 3. The faulty condition tries only 0, 1, 2. Since "em" occurs only at s = 3, it is not found and the method returns −1. If the pattern is not at the end of the text the bug stays invisible, so it easily escapes testing.
9.2.4Best, average, and worst case
The number of comparisons in brute force depends on how many characters match at each alignment. Table 9.3 summarizes the three cases.
| Case | When? | Comparisons | Time |
|---|---|---|---|
| Best | P[0] matches no character of the text (e.g. P = "xyz", T = "aaaa…") | n − m + 1 | O(n) |
| Average | Random text, large alphabet: the mismatch usually comes within the first character or two | ≈ (n − m + 1) · σ/(σ − 1) | O(n) |
| Worst | T = "aaaaaaaaaa", P = "aaab": m comparisons at every alignment | (n − m + 1) · m | O(n · m) |
The factor σ/(σ − 1) in the average case comes from a simple probability calculation. Suppose the characters of the text are chosen independently and uniformly from the alphabet. At each alignment the first comparison is always made. The second is made only if the first character matches, which has probability 1/σ. The third requires the first two to match: probability 1/σ2. The expected number of comparisons at one alignment is therefore at most 1 + 1/σ + 1/σ2 + … = σ/(σ − 1). For English letters (σ = 26) this is about 1.04; for the binary alphabet (σ = 2) it is 2. In both cases the work per alignment is constant and the total time is O(n).
Find the number of comparisons brute force makes for T = "aaaaaaaaaa" (n = 10) and P = "aaab" (m = 4).
- Number of alignments. The shifts are 0, 1, …, 6: n − m + 1 = 7 alignments.
- Work per alignment. At every alignment the first three characters "aaa" of the pattern match the a's in the text. The fourth character, b, mismatches the a in the text. Each alignment costs 4 comparisons.
- Total. 7 × 4 = 28 comparisons. The mismatch always comes at the last character and the pattern does not occur in the text.
The same structure gives 9 × 4 = 36 comparisons for n = 12, m = 4. The general formula is (n − m + 1) · m. With m = n/2 this is about n2/4: the running time grows with the square of the text length.
It is worth examining carefully what happens in the worst case. At s = 0 the first three characters have matched. This tells us that T[0..2] = "aaa". When the algorithm moves on to s = 1 it reads T[1] and T[2] again, although these characters were already known. This is the real flaw of brute force: the information learned at a mismatch is thrown away, the algorithm goes back in the text, and the same characters are compared again. The KMP algorithm stores and uses exactly this information.
9.3The Knuth-Morris-Pratt algorithm
The Knuth-Morris-Pratt (KMP) algorithm is the first linear-time matching algorithm; it keeps the information that brute force throws away. James H. Morris and Vaughan Pratt discovered it together in 1970. Donald Knuth reached the same idea independently, from automata theory. The three published their results in a joint paper in 1977. The name of the algorithm comes from the surnames of the three.
9.3.1Not forgetting the matched part
The basic idea of KMP is this: at a mismatch, use what is already known about the part of the pattern that has matched. Suppose that at some alignment P[0..q−1] has matched the text and P[q] has not. Then the last q characters of the text read are exactly P[0..q−1]. There is no need to read them again; we know what they are by looking at the pattern itself.
This knowledge gains two things. First, the text pointer never moves backward. The text is read once, from left to right. Second, alignments that cannot possibly match are never tried. The pattern is shifted directly to the farthest position that the structure of the matched part allows.
Figure 9.5 shows the idea on a small example. Let the text be "ABABABC" and the pattern "ABABC". At s = 0 the first four characters "ABAB" match, and T[4] = A mismatches P[4] = C. Brute force would shift the pattern by one and restart from T[1]. But we know that the last four characters of the text are "ABAB". The suffix "AB" of "ABAB" is also a prefix of the pattern. So if the pattern is shifted by two positions, its leading "AB" already matches the "AB" in the text. The comparison continues between P[2] and T[4]. Indeed, at this alignment the rest of the pattern, "ABC", matches too, and the pattern is found at s = 2.
How far to shift depends only on the pattern, not on the text. So it can be computed in advance for every possible q and written into a table. This table is called the LPS table or the prefix function, and sources also denote it by π.
9.3.2The LPS table
LPS stands for "longest proper prefix which is also a suffix." Each cell of the table is the length of the longest piece of a prefix of the pattern that resembles the prefix itself.
For 0 ≤ q < m, lps[q] is the length of the longest piece of the string P[0..q] that is both a proper prefix and a suffix of it. If there is no such nonempty piece, lps[q] = 0. Since the proper prefix of a single character is the empty string, lps[0] = 0 always.
The word "proper" in the definition matters. The string itself is also both a prefix and a suffix of itself. If the definition did not exclude it, every cell would be q + 1 and the table would carry no information. The properness condition also yields lps[q] ≤ q. This inequality is used in the proof that the algorithm makes progress at every fallback.
Let the text be "ababcababcabababd" and the pattern "ababd". The LPS table of the pattern is given cell by cell, with reasons, in Table 9.4.
| q | P[q] | lps[q] | Reason (P[0..q]) |
|---|---|---|---|
| 0 | a | 0 | "a": no proper prefix |
| 1 | b | 0 | "ab": a ≠ b |
| 2 | a | 1 | "aba": "a" is both prefix and suffix |
| 3 | b | 2 | "abab": "ab" is both prefix and suffix |
| 4 | d | 0 | "ababd": no prefix ends in d |
The result is lps = [0, 0, 1, 2, 0]. In the row q = 3, "aba" may look like a candidate. But "aba" is not a suffix of "abab"; the three-letter suffix of "abab" is "bab". So the value is 2, not 3.
The meaning of the table shows up in the search. Suppose the first q characters of the pattern have matched and the (q + 1)th has not. The matched part is P[0..q−1], and the longest piece of it that resembles its own prefix has length lps[q − 1]. The pattern is shifted so that this piece lies under the same piece in the text. The shift is q − lps[q − 1], and the new pattern position from which comparison continues is lps[q − 1].
Suppose P[0..q−1] has matched the text at shift s and P[q] has mismatched. Then the pattern cannot match the text at any shift strictly between s and s + q − lps[q − 1].
Proof. Suppose the pattern could match at some shift s' with s < s' < s + q. At this alignment the first k = s + q − s' characters of the pattern lie under the part T[s'..s+q−1] of the text. This part is the last k characters of the matched P[0..q−1]. For a match, P[0..k−1] would have to equal this part. That is, P[0..k−1] would be both a proper prefix and a suffix of P[0..q−1] (0 < k < q). By definition such a piece has length at most lps[q − 1]. Hence k ≤ lps[q − 1], that is, s' ≥ s + q − lps[q − 1]. Smaller shifts violate this condition, so they cannot match. ∎
The theorem says that KMP never misses an occurrence. The skipped shifts contain a definite contradiction between the pattern and the text. The correctness of the algorithm rests on this observation.
9.3.3Building the LPS table
The LPS table can be computed straight from the definition: for each q, try all prefix lengths and compare with the suffix. This takes O(m3) time. KMP's way of building the table is cleverer: the table is built by searching the pattern within itself, that is, by KMP itself. The total time is O(m).
int[] buildLps(String p) {
int m = p.length(), k = 0;
int[] lps = new int[m];
for (int q = 1; q < m; q++) {
while (k > 0 &&
p.charAt(k) != p.charAt(q))
k = lps[k - 1];
if (p.charAt(k) == p.charAt(q))
k++;
lps[q] = k;
}
return lps;
}In the code, k is the length of the prefix matched so far. At each step of the loop q increases by one and the character p[q] is processed:
- Fallback: if
k > 0andp[k]differs fromp[q], the prefix of lengthkcannot be extended. The next candidate is the longest piece of this prefix that resembles its own prefix:k = lps[k - 1]. This step is the same as the mismatch step in the search. - Extension: if
p[k] == p[q], the matched prefix grows by one character andkincreases by one. - Writing:
kis the length of the longest proper prefix-suffix of P[0..q], and it is written tolps[q].
Here is why the fallback is lps[k - 1]. The prefix-suffix pieces of P[0..q] must be tried in decreasing order of length. Each of them is a prefix-suffix piece of P[0..q−1] extended by one character. The prefix-suffix pieces of P[0..q−1] form a chain too. The longest is k, the next is lps[k − 1], the next lps[lps[k − 1] − 1], and so on. Each length in the chain is the longest prefix-suffix piece inside the previous piece. The algorithm follows the chain from large to small and stops at the first candidate that can be extended.
Trace the call buildLps("ACABACACD"). The pattern's indices are 0–8. Table 9.5 gives every comparison and the changes in k.
q | k (before) | Comparison | Action | lps[q] |
|---|---|---|---|---|
| 0 | — | — | always 0 | 0 |
| 1 | 0 | p[0] = A, p[1] = C | different; k = 0 stays | 0 |
| 2 | 0 | p[0] = A, p[2] = A | same; k = 1 | 1 |
| 3 | 1 | p[1] = C, p[3] = B | different; fall back: k = lps[0] = 0 | |
| 3 | 0 | p[0] = A, p[3] = B | different; k = 0 stays | 0 |
| 4 | 0 | p[0] = A, p[4] = A | same; k = 1 | 1 |
| 5 | 1 | p[1] = C, p[5] = C | same; k = 2 ("AC") | 2 |
| 6 | 2 | p[2] = A, p[6] = A | same; k = 3 ("ACA") | 3 |
| 7 | 3 | p[3] = B, p[7] = C | different; fall back: k = lps[2] = 1 | |
| 7 | 1 | p[1] = C, p[7] = C | same; k = 2 ("AC") | 2 |
| 8 | 2 | p[2] = A, p[8] = D | different; fall back: k = lps[1] = 0 | |
| 8 | 0 | p[0] = A, p[8] = D | different; k = 0 stays | 0 |
The result is lps = [0, 0, 1, 0, 1, 2, 3, 2, 0]. The most instructive row is q = 7. The longest prefix-suffix piece of "ACABACA" is "ACA" (k = 3). The character after "ACA", P[3] = B, mismatches P[7] = C; "ACAB" and "ACAC" differ. The next candidate is the longest prefix-suffix piece inside "ACA", which is "A": lps[2] = 1. The character after that "A", P[1] = C, matches P[7], and "AC" is found. Three fallbacks were made in all.
The construction takes O(m) time. The reasoning is the same as in the linearity proof for the search: k increases by at most one per step, so the total increase cannot exceed m − 1. Every fallback decreases k by at least one, and k cannot be negative. So the total number of fallbacks cannot exceed m − 1 either. In the example there are 3 fallbacks against 8 opportunities to increase. The table needs O(m) extra memory.
Computing LPS while counting the string itself. For "aaaa" the correct table is [0, 1, 2, 3], not [1, 2, 3, 4]. For example, the longest proper prefix-suffix piece of "aaaa" is "aaa", of length 3. If the table is built wrongly, the fallback never shrinks q and the search loops forever.
9.3.4The three phases of the search
The KMP search works with two pointers. i is the position in the text and q is the position in the pattern; q is also the number of characters matched so far. The behavior of the algorithm can be divided into three phases:
- Looking for the first character. Here q = 0. The pointer i advances until a text character matching the first character of the pattern is found.
- Advancing together. As long as characters match, both pointers advance. If q = m, the end of the pattern has been reached and the position i − m + 1 is returned.
- Falling back with LPS. At a mismatch only the pattern pointer falls back: q = lps[q − 1]. The text pointer i stays where it is. When a match is found, we return to phase 2; if q drops to 0, we return to phase 1.
In none of the phases does i decrease. This is the most important difference from brute force. Brute force pulls the text pointer back to s at every new alignment. In KMP the text is read like a stream: each character arrives once, is processed, and is never requested again.
9.3.5Example: searching for ABCDABD
Let the pattern be "ABCDABD" and the text "ABCABCDABABCDABCDABDE" (m = 7, n = 21). The LPS table of the pattern is [0, 0, 0, 0, 1, 2, 0]: the "A" at the end of "ABCDA" and the "AB" at the end of "ABCDAB" are also prefixes of the pattern. Figure 9.8 shows the five alignments of the search.
- s = 0. "ABC" matches; T[3] = A mismatches P[3] = D. Here q = 3, and q = lps[2] = 0. The pattern shifts by 3; this time T[3] is compared with P[0].
- s = 3. "ABCDAB" matches; T[9] = A mismatches D. Here q = 6, and q = lps[5] = 2. Because the "AB" at the end of the matched "ABCDAB" is a prefix, the pattern shifts by 4.
- s = 7. "AB" is known to match and is not compared again. T[9] = A mismatches P[2] = C; q = lps[1] = 0.
- s = 9. T[9] = A matches P[0]. "ABCDAB" matches; T[15] = C mismatches D. q = 6 → lps[5] = 2; the pattern shifts by 4.
- s = 13. "AB" is known; then "CDABD" matches as well. The pattern is found at position 13.
During the search the text pointer never moves backward. The total number of character comparisons is 24. Twenty characters of the text are read once each. At the three mismatch points (i = 3, 9, 15) the same text character is compared once more with a different character of the pattern. At i = 9 this happens twice. Brute force tries 14 alignments on the same text and makes 37 comparisons.
9.3.6Java code and trace
The Java code of the search is almost identical to the LPS construction code. The only difference is that the comparison is with the text rather than with the pattern itself.
int kmpSearch(String t, String p) {
int n = t.length(), m = p.length();
int[] lps = buildLps(p);
int q = 0; // matched length
for (int i = 0; i < n; i++) {
while (q > 0 &&
p.charAt(q) != t.charAt(i))
q = lps[q - 1];
if (p.charAt(q) == t.charAt(i))
q++;
if (q == m)
return i - m + 1;
}
return -1;
}- Setup: the LPS table is built (O(m)) and
q = 0is set.qis the length of the matched prefix. - Outer loop:
iwalks through the text once, from left to right. No line in the code decreasesi. - The
whileloop: as long as there is a mismatch,qfalls back along the LPS chain. The loop stops whenq == 0; there is nowhere further back to go. - The
if(match): ifp[q]equalst[i], the matched prefix grows by one. if (q == m): the whole pattern has matched. Since the last matched character is ati, the start isi - m + 1.
We trace the code with the call kmpSearch("ababcababcabababd", "ababd"). Here n = 17, m = 5, and lps = [0, 0, 1, 2, 0]. Table 9.6 gives the change in q for each text character.
i | t[i] | q (before) | Fallback | Match | q (after) |
|---|---|---|---|---|---|
| 0–3 | a b a b | 0 → 3 | — | each matches | 4 |
| 4 | c | 4 | d ≠ c: q = lps[3] = 2; a ≠ c: q = lps[1] = 0 | p[0] = a ≠ c | 0 |
| 5–8 | a b a b | 0 → 3 | — | each matches | 4 |
| 9 | c | 4 | d ≠ c: q = 2; a ≠ c: q = 0 | p[0] = a ≠ c | 0 |
| 10–13 | a b a b | 0 → 3 | — | each matches | 4 |
| 14 | a | 4 | d ≠ a: q = lps[3] = 2 | p[2] = a = a | 3 |
| 15 | b | 3 | — | p[3] = b = b | 4 |
| 16 | d | 4 | — | p[4] = d = d | 5 = m |
At i = 16, q == m holds and 16 − 5 + 1 = 12 is returned. The text has been scanned only once. The row i = 14 is the step that best shows the gain of KMP. At the moment of the mismatch the last four characters of the text are "abab". The "ab" at the end of it is a prefix of the pattern; with q = 2 the pattern continues from two positions ahead, and T[14] = a matches at once. At this point brute force would have gone back to T[11].
This trace makes 22 character comparisons in all: each of the 17 text characters is read at least once, and the mismatch points are read several times. On the same search, brute force tries 13 alignments and makes 33 comparisons.
9.3.7Why O(n + m)?
The KMP code has two nested loops. At first glance this looks like O(n · m) time. In fact, the total number of iterations of the while loop is bounded. The kind of analysis in which operations are counted in total rather than one by one is called amortized analysis.
The KMP search makes at most 2n character comparisons and runs in O(n) time. Together with building the LPS table, the total time is O(n + m) and the extra memory is O(m). These bounds hold in the worst case as well.
Proof. Follow the value of q. In each iteration of the outer loop, q increases at most once, by one (q++). Since the outer loop runs n times, the total increase is at most n. Each iteration of the while loop lowers q to lps[q − 1]. Because lps[q − 1] ≤ q − 1, each iteration decreases q by at least one. q starts at 0 and never becomes negative. So the total decrease cannot exceed the total increase. Consequently the while loop runs at most n times over the whole search.
Each while iteration makes one comparison. To these we add the at most one comparison in the if for each i. The total is at most n + n = 2n. The same argument gives O(m) for buildLps. ∎
The idea in the proof can also be told as a bank-account analogy. Each match deposits one lira into the account, and each fallback withdraws one lira. The account can never go negative. So the total withdrawn cannot exceed the total deposited. For a single i the while loop can run many times; in the row i = 4 of Table 9.6 it runs twice. But this is possible only if the same amount of matching was accumulated in earlier steps.
Using lps[q] instead of lps[q - 1] at a mismatch. If q characters have matched, the matched part is P[0..q−1] and its table value is lps[q - 1]. For example, the table for the pattern "abcabd" is [0, 0, 0, 1, 2, 0]. When "abcab" has matched (q = 5), the correct value is lps[4] = 2 and the pattern shifts by 3. If lps[5] = 0 is used, the pattern shifts by 5; if an occurrence lies among the alignments this shift skips, it is missed.
9.3.8Finding all occurrences; pros and cons
The kmpSearch above stops at the first occurrence. If all occurrences are wanted, the position is added to a list when q == m and the search continues. Before continuing, q is set back to lps[m − 1]. This step follows the same logic as the mismatch step: the whole pattern has matched, and the next possible occurrence starts from the longest prefix-suffix piece of the matched pattern. In this way overlapping occurrences are found too.
List<Integer> kmpAll(String t, String p) {
int n = t.length(), m = p.length();
int[] lps = buildLps(p);
List<Integer> positions = new ArrayList<>();
int q = 0;
for (int i = 0; i < n; i++) {
while (q > 0 &&
p.charAt(q) != t.charAt(i))
q = lps[q - 1];
if (p.charAt(q) == t.charAt(i))
q++;
if (q == m) {
positions.add(i - m + 1);
q = lps[q - 1]; // overlapping hits
}
}
return positions;
}The code has been run in Java. The call kmpAll("abababa", "aba") returns [0, 2, 4]. The occurrences overlap: the last a of the "aba" at 0 is the first a of the "aba" at 2. Since the LPS table of "aba" is [0, 0, 1], after every hit q = 1 and that single a is not read again. kmpAll("aaaaa", "aa") gives [0, 1, 2, 3]. If the line q = lps[q − 1] is forgotten, q exceeds m on the next turn and p.charAt(q) reads outside the string.
The strengths and weaknesses of KMP can be summarized as follows:
- Linear even in the worst case. The time is O(n + m) regardless of the structure of the input. The worst input for brute force, T = a…a, P = a…ab, is no problem for KMP.
- Never moves backward in the text. This matters for stream data, where the text arrives piece by piece from a network or a disk. Earlier parts of the text need not be kept in memory.
- Usually slower than Boyer-Moore in practice. KMP reads every character of the text at least once. Boyer-Moore skips many characters without reading them.
- The gain is limited on small alphabets. On four-letter alphabets such as DNA, LPS values can be large and the shifts stay short. The bound is still linear, but the constant factor grows.
9.4The Boyer-Moore algorithm
With the algorithm they published in 1977, Robert S. Boyer and J Strother Moore showed a surprising result: to find a pattern, it is not necessary to read every character of the text. KMP looks at every character of the text at least once. Boyer-Moore, on natural-language text, skips most characters without reading them. The search in text editors and in tools like grep is based on this family of algorithms.
9.4.1Comparing from right to left
The first difference of the algorithm is the direction of comparison. As in brute force, the pattern is slid along the text from left to right. But the characters at one alignment are compared from right to left, starting at the last character of the pattern. The reason for this choice is that a mismatch gives the most information at the right end. If the text character at the right end does not occur in the pattern at all, no alignment covering that character can match. The pattern can be shifted completely beyond this character, that is, by m positions.
The algorithm works in four steps:
- Preprocessing. Shift tables are built from the pattern: the last occurrence of each character in the pattern (the bad-character table) and the shift amount for each suffix (the good-suffix table).
- Search. The pattern is aligned under the text. Comparison starts at the last character of the pattern and moves left.
- Match check. If all characters match, the position is reported.
- Shifting. At a mismatch, two rules each propose a shift: the bad-character rule and the good-suffix rule. The pattern is shifted by the larger of the two.
Both rules are safe: the shifts they propose never skip an alignment at which a match could occur. So taking the larger of the two is safe too.
9.4.2The bad-character rule
Suppose that while comparing from right to left at some alignment a mismatch occurs at position j: P[j] ≠ T[s + j]. The mismatched text character c = T[s + j] is called the bad character. The rule shifts the pattern according to where c occurs in the pattern.
The last-occurrence table holds, for each character c, the value last[c]: the rightmost position of c in the pattern, or −1 if it does not occur. The bad-character rule advances the shift by s ← s + max(1, j − last[c]).
The rule has three cases:
- c occurs in the pattern to the left of j. The pattern is shifted so that the rightmost c comes under the c in the text. The shift is j − last[c].
- c does not occur in the pattern at all. Since last[c] = −1, the shift is j + 1. The pattern moves completely past c.
- The last occurrence of c is to the right of j. Then j − last[c] ≤ 0. The rule shifts by at least 1 to keep the pattern from moving backward.
The safety of the rule follows from the definition of the last occurrence. Since last[c] is the rightmost occurrence, there is no c in the pattern positions between last[c] + 1 and j. Each of the smaller shifts 1, 2, …, j − last[c] − 1 would bring one of these positions under the c in the text. A mismatch there is certain, so those alignments can be skipped.
int[] lastOccurrence(String p) {
int[] last = new int[256];
Arrays.fill(last, -1);
for (int i = 0; i < p.length(); i++)
last[p.charAt(i)] = i;
return last;
}The lastOccurrence method builds an array of 256 cells and sets all of them to −1. The array has one cell for each of the 256 single-byte values (0–255; the first 128 are ASCII). Then the pattern is scanned from left to right and each character's cell is set to the current position. If a character occurs more than once, the last value written, the rightmost position, remains. The time is O(m + σ) and the memory is O(σ), where σ = 256.
Let the text be "GCAATGCCTATGTGACC" and the pattern "TATGTG" (m = 6). Find the first shift using the bad-character rule alone.
- Table. The pattern is T A T G T G. last[T] = 4, last[A] = 1, last[G] = 5; C does not occur in the pattern.
- Comparison. At s = 0, from right to left: P[5] = T[5] = G matches, P[4] = T[4] = T matches. P[3] = G mismatches T[3] = A; j = 3 and the bad character is A.
- Shift. last[A] = 1; the shift is max(1, 3 − 1) = 2. At the new alignment the A of the pattern (position 1) lies under the A of the text (position 3).
If the search continues, at the second alignment (s = 2) the C at the right end is not in the pattern, so the pattern jumps 6 positions. At the third alignment (s = 8) all six characters match. Three alignments and 10 comparisons suffice in all.
Writing the shift as just j - last[c] without max(1, …). If the last occurrence of c is to the right of j, this difference is zero or negative. For example, in "abacab" last[a] = 4; if the mismatch occurs at j = 3, the difference is 3 − 4 = −1. The pattern moves backward or stays in place, and the algorithm may loop forever.
9.4.3The good-suffix rule
The bad-character rule looks only at the mismatched character; it makes no use of the characters matched so far. The second rule fills this gap. The suffix u = P[j+1..m−1] that matched before the mismatch has also been found in the text. This suffix is called the "good suffix." The good-suffix rule shifts the pattern according to another occurrence of u in the pattern:
- Case 1. If u occurs elsewhere in the pattern, preceded by a different character, the pattern is shifted so that this occurrence comes under the u in the text. The preceding character must be different; the same character would repeat the same mismatch.
- Case 2. If there is no such occurrence, the longest prefix of P that equals a suffix of u is aligned.
- Case 3. If neither exists, the pattern is shifted by m positions.
The good-suffix table precomputes this shift for every j. The table is built in O(m) time by a method similar to KMP's LPS idea, this time over suffixes. The details of the construction are long; for this course it is enough to understand the meaning of the rule and to apply it by hand.
Figure 9.12 shows the difference between the two rules. The bad character is A, and last[A] = 3 > j = 2; the bad-character rule proposes a shift of only 1. The good-suffix rule proposes 2. The algorithm picks the larger and shifts the pattern by 2. Full Boyer-Moore uses the two tables together.
On small alphabets the good-suffix rule matters even more. In DNA (σ = 4), each of the four letters almost certainly occurs somewhere near the right end of a long pattern. The bad-character rule therefore usually proposes shifts of only 1–2 positions. The good-suffix rule looks at the structure of the matched part, so it can find long shifts.
9.4.4Example: searching for HELLO
Let the text be "LO LOELLO O HELLO" (n = 17) and the pattern "HELLO" (m = 5). The example is run with the bad-character rule only. The last-occurrence table is given in Table 9.7; since L occurs twice, the rightmost position (3) is recorded.
| c | H | E | L | O | other |
|---|---|---|---|---|---|
| last[c] | 0 | 1 | 3 | 4 | −1 |
| Alignment | s | Right-to-left comparison | Bad character | Shift | Cmp. |
|---|---|---|---|---|---|
| 1 | 0 | O, L match; T[2] = ␣ ≠ P[2] = L | ␣ (absent) | 2 − (−1) = 3 | 3 |
| 2 | 3 | T[7] = L ≠ P[4] = O | L (3) | 4 − 3 = 1 | 1 |
| 3 | 4 | O, L, L, E match; T[4] = O ≠ P[0] = H | O (4) | 0 − 4 < 1 → 1 | 5 |
| 4 | 5 | T[9] = ␣ ≠ P[4] = O | ␣ (absent) | 4 − (−1) = 5 | 1 |
| 5 | 10 | T[14] = L ≠ P[4] = O | L (3) | 1 | 1 |
| 6 | 11 | T[15] = L ≠ P[4] = O | L (3) | 1 | 1 |
| 7 | 12 | all five characters match | — | found | 5 |
| Total | 17 | ||||
The pattern is found at s = 12 after 7 alignments and 17 comparisons. Alignment 3 is noteworthy: after four characters match, the mismatch occurs at the left end. The last occurrence of the bad character O lies to the right of j = 0, so the rule shifts by only 1. At this alignment the good-suffix rule would have proposed more: the matched "ELLO" occurs nowhere else in the pattern and overlaps no prefix, so the shift would be 5. This example shows clearly how the rules complement each other.
9.4.5The Horspool simplification
In 1980 R. Nigel Horspool proposed a simplification of Boyer-Moore that is widely used in practice. The good-suffix table is dropped entirely. The bad-character rule is changed too: the shift is determined by the text character under the last character of the alignment, regardless of where the mismatch occurred.
The Horspool shift table holds, for each character c, the value shift[c] = m − 1 − r, where r is the rightmost position of c in P[0..m−2]. If c does not occur in this part, shift[c] = m. After each alignment the shift becomes s ← s + shift[T[s + m − 1]].
The last character of the pattern is left out of the table. If it were included, the shift for the last character would be m − 1 − (m − 1) = 0 and the pattern would stand still. For "HELLO" the table is: H → 4, E → 3, L → 1, O → 5, other → 5. L occurs twice (positions 2 and 3); the rightmost, 3, is used and the shift is 1. Since O occurs only at the last position, it never enters the table and gets 5, like "other".
| Alignment | s | Comparison | Last character | Shift |
|---|---|---|---|---|
| 1 | 0 | O, L match; T[2] = ␣ ≠ P[2] | T[4] = O | 5 |
| 2 | 5 | T[9] = ␣ ≠ P[4] | T[9] = ␣ | 5 |
| 3 | 10 | T[14] = L ≠ P[4] | T[14] = L | 1 |
| 4 | 11 | T[15] = L ≠ P[4] | T[15] = L | 1 |
| 5 | 12 | all match | — | found |
On the same example, Horspool gets by with 5 alignments and 11 comparisons; the basic bad-character rule needed 7 alignments and 17 comparisons. The difference comes from the first alignment. The basic rule looks at the mismatched space character and shifts by 3. Horspool looks at the last character, O. Since O does not occur in the first four characters of the pattern, the pattern shifts by 5. The simplification does not always do better, but with its single table and short code it is very fast in practice.
int horspool(String t, String p) {
int n = t.length(), m = p.length();
int[] shift = new int[256];
Arrays.fill(shift, m);
for (int i = 0; i < m - 1; i++)
shift[p.charAt(i)] = m - 1 - i;
int s = 0;
while (s <= n - m) {
int j = m - 1;
while (j >= 0 &&
p.charAt(j) == t.charAt(s + j))
j--;
if (j < 0) return s;
s += shift[t.charAt(s + m - 1)];
}
return -1;
}- Table: the 256 cells of the array
shiftare first filled withm. ThenP[0..m−2]is scanned from left to right andm - 1 - iis written for each character. Because the scan goes left to right, the rightmost occurrence is written last and stays. - Comparison:
jstarts at the right end and decreases as characters match. Ifj < 0, all characters have matched andsis returned. - Shift: wherever the mismatch occurred,
sincreases by the table value of the last character of the alignment,t[s + m - 1]. Since this value is at least 1, the pattern never moves backward.
The call horspool("LO LOELLO O HELLO", "HELLO") follows the steps in Table 9.9 exactly and returns 12. The code was run in Java, and the counts of 5 alignments and 11 comparisons were confirmed.
9.4.6Example: all occurrences of abacab
This example shows all the cases of the bad-character rule together. Let the text be "abacaabadcabacabaabb" (n = 20) and the pattern "abacab" (m = 6). The last-occurrence table is a = 4, b = 5, c = 3, and −1 for the others. All occurrences are sought; after a match the pattern is shifted by 1 and the search continues.
| Alignment | s | Mismatch | Shift | Cmp. |
|---|---|---|---|---|
| 1 | 0 | T[5] = a ≠ P[5] = b | 5 − last[a] = 5 − 4 = 1 | 1 |
| 2 | 1 | b, a match; T[4] = a ≠ P[3] = c | last[a] = 4 ≥ j = 3 → 1 | 3 |
| 3 | 2 | T[7] = a ≠ P[5] = b | 1 | 1 |
| 4 | 3 | T[8] = d ≠ P[5] = b | d absent: j + 1 = 6 | 1 |
| 5 | 9 | T[14] = a ≠ P[5] = b | 1 | 1 |
| 6 | 10 | six characters match: occurrence, s = 10 | 1 (search continues) | 6 |
| 7 | 11 | T[16] = a ≠ P[5] = b | 1 | 1 |
| 8 | 12 | T[17] = a ≠ P[5] = b | 1 | 1 |
| 9 | 13 | b, a match; T[16] = a ≠ P[3] = c | last[a] = 4 ≥ 3 → 1 | 3 |
| 10 | 14 | b matches; T[18] = b ≠ P[4] = a | last[b] = 5 ≥ 4 → 1 | 2 |
| Total (the search ends when s = 15 > n − m) | 20 | |||
The search ends after 10 alignments and 20 comparisons; the pattern occurs only at s = 10. Most shifts are 1, because the characters a and b in the text occur near the right end of the pattern. Only d gives a big jump. This table shows that the speed of Boyer-Moore depends on the alphabet and the text: the more frequent the characters absent from the pattern, the longer the jumps.
9.4.7Java code and trace
Boyer-Moore code that uses only the bad-character rule is very similar to the Horspool code. The only difference is the shift line: the shift is computed from the mismatched character rather than from the last character.
int boyerMoore(String t, String p) {
int n = t.length(), m = p.length();
int[] last = lastOccurrence(p);
int s = 0;
while (s <= n - m) {
int j = m - 1;
while (j >= 0 &&
p.charAt(j) == t.charAt(s + j))
j--;
if (j < 0) return s;
s += Math.max(1,
j - last[t.charAt(s + j)]);
}
return -1;
}We trace the code with the call boyerMoore("merhaba naber", "abe"). Here n = 13 and m = 3. The last-occurrence table is a = 0, b = 1, e = 2, and −1 for the others.
s | Alignment | Comparison | Shift |
|---|---|---|---|
| 0 | mer | p[2] = e ≠ t[2] = r | last['r'] = -1: max(1, 2 − (−1)) = 3 |
| 3 | hab | p[2] = e ≠ t[5] = b | last['b'] = 1: max(1, 2 − 1) = 1 |
| 4 | aba | p[2] = e ≠ t[6] = a | last['a'] = 0: max(1, 2 − 0) = 2 |
| 6 | a␣n | p[2] = e ≠ t[8] = n | last['n'] = -1: 3 |
| 9 | abe | e, b, a match; j = -1 | found: 9 is returned |
The search ends after 5 alignments and 7 comparisons. Brute force tries 10 alignments and makes 15 comparisons on the same search. Only 7 of the 13 characters of the text were looked at. The characters at positions 0, 1, 3, 4, 7, and 12 were never read. This is the property that sets Boyer-Moore apart from brute force and from KMP.
9.4.8Analysis
The performance of Boyer-Moore varies over a wide range:
- Best case: none of the characters of the text occurs in the pattern. Each alignment makes a single comparison and the pattern jumps m positions. About n/m comparisons suffice in total: O(n/m). The running time shrinks as the pattern gets longer. In brute force and KMP the opposite happens.
- Average case: in natural-language text over a large alphabet, most mismatches occur at the right end and the shifts are long. The time is sublinear; that is, fewer characters are read than the length of the text.
- Worst case (bad character only): T = aaaa…a, P = baaa…a. At each alignment m − 1 a's match from the right and the b at the left end mismatches. The last occurrence of the bad character a is at the right end, so the shift is 1. The time is O(n · m). For example, with n = 20 and m = 5, each of the 16 alignments makes 5 comparisons, 80 in all.
- Worst case (full algorithm): if the good-suffix rule and the improvement proposed by Zvi Galil in 1979 are used together, the worst case drops to O(n + m).
Let the text be "abccbaabccbaabcbcabbabcabc" (n = 26) and the pattern "abcbcabbabcabc" (m = 14). Find the last-occurrence table and search using the bad-character rule only.
- Table. The pattern is a b c b c a b b a b c a b c. The rightmost a is at position 11, b at position 12, and c at position 13: last[a] = 11, last[b] = 12, last[c] = 13.
- First alignment. At s = 0, P[13] = c mismatches T[13] = b. The shift is max(1, 13 − 12) = 1.
- Later alignments. The search takes 10 alignments. The shifts are 1, 1, 1, 1, 2, 1, 2, 1, 2; none exceeds 2.
- Result. The pattern is found at s = 12. In all, 31 comparisons are made.
The alphabet has three letters and each letter occurs at the right end of the pattern. This is why the bad-character rule stays weak here. The example shows why the good-suffix rule is needed on a small alphabet.
The preprocessing cost of Boyer-Moore is O(m + σ) and its extra memory is O(m + σ). Because the bad-character table keeps one cell for each letter of the alphabet, for large alphabets (e.g. all Unicode characters) a hash table is used instead of an array.
9.5The Rabin-Karp algorithm
The algorithm published by Michael O. Rabin and Richard M. Karp in 1987 approaches the problem from another side. Instead of choosing shifts cleverly, it makes the comparison at each alignment cheaper. The pattern and the windows of the text are turned into numbers; instead of testing two strings for equality, two numbers are tested.
9.5.1Comparing numbers instead of characters
Rabin-Karp computes the hash value of the pattern and of every window of length m in the text. A hash is a function that maps a string to a small integer; it is a kind of digest of the string. Comparing two numbers is a single operation, while comparing two strings can take up to m operations.
This idea has two problems. First, computing the hash of every window from scratch takes O(m), and then nothing is gained. The solution is the rolling hash: when the window slides one position to the right, the new hash is computed from the old one in O(1) time. Second, different strings can have the same hash value. So hash equality does not guarantee a match. A window whose hash comes out equal is only a candidate and must be verified character by character.
The steps of the algorithm are as follows:
- Hash computation. The hash values of the pattern and of the first window of the text are computed.
- Match check. A window whose hash value equals that of the pattern is accepted as a candidate.
- Verification. The candidate window is compared with the pattern character by character.
- Shift and recompute. If there is no match, the window slides one position to the right and the hash is updated.
- Repeat. The steps continue to the end of the text.
9.5.2The sum hash and spurious hits
Let us see the idea with the simplest hash: the sum of the character values. Give the letters the values U = 1, T = 2, S = 3, A = 4, V = 5. We search for "TS" in the text "VUATS"; the hash of the pattern is 2 + 3 = 5.
- "VU": 5 + 1 = 6 ≠ 5. The hash differs; the characters are never looked at.
- "UA": 1 + 4 = 5. The hash is equal, but "UA" ≠ "TS". This is a spurious hit; the verification is wasted.
- "AT": 4 + 2 = 6 ≠ 5. The new hash is obtained from the old one: the value of the outgoing U is subtracted and that of the incoming T is added: 5 − 1 + 2 = 6. The operation is independent of the window length; it is O(1).
- "TS": 2 + 3 = 5. The hash is equal and the character comparison succeeds too: a match at s = 3.
The sum hash shows well what a rolling update is, but it is a weak hash. It is insensitive to the order of the letters: "ST" also gives 5. On long windows the values cluster in a narrow range and many windows give the same sum. Real implementations therefore use a position-weighted polynomial hash and a large prime modulus.
9.5.3Polynomial hash and the rolling update
A polynomial hash reads the string like a number written in base B. The character codes are the digits; the leftmost character is the most significant digit. Since the number can grow very large, the remainder modulo a prime Q is taken.
Let B be the base and Q a prime modulus. The polynomial hash of the window at shift s is
hs = (T[s]·Bm−1 + T[s+1]·Bm−2 + … + T[s+m−1]) mod Q
When the window slides one position to the right, the new value is found with the rolling update formula:
hs+1 = (B · (hs − T[s] · Bm−1) + T[s+m]) mod Q
The formula does three steps in one line. First the contribution of the outgoing character, T[s] · Bm−1, is subtracted. Then the remaining digits are multiplied by B, which shifts them one digit to the left. Finally the incoming character is added in the lowest digit. A decimal analogy shows this clearly: to go from "314" to "141", drop the hundreds digit 3 (14), shift one digit left (140), and add 1 (141).
The value Bm−1 mod Q is needed in every update, and since the window length does not change, it is computed once and stored. The rules of modular arithmetic allow taking remainders at every intermediate step. The values (a + b) mod Q and (a · b) mod Q can also be computed from the remainders of a and b. In this way the numbers never grow.
Let the base be B = 10, Q = 13, and the characters digits. For T = "31415" and m = 3, find the hashes of the windows with the rolling formula.
- Constant. Bm−1 mod Q = 100 mod 13 = 9.
- First window. h("314") = 314 mod 13 = 2 (13 · 24 = 312).
- Second window. h("141") = (10 · (2 − 3 · 9) + 1) mod 13 = (−249) mod 13 = 11. Direct computation: 141 = 13 · 10 + 11 ✓.
- Third window. h("415") = (10 · (11 − 1 · 9) + 5) mod 13 = 25 mod 13 = 12. Direct computation: 415 = 13 · 31 + 12 ✓.
In the second step the intermediate result is negative. In mathematics (−249) mod 13 = 11, because −249 = 13 · (−20) + 11. Java's % operator, however, gives a negative remainder for a negative number: the expression -249 % 13 is −2. Adding 13 to the result gives the correct value, 11.
9.5.4Java code and trace
The code below uses ASCII codes as digits: the base is B = 256 and the modulus is Q = 101. The helper method matchAt(t, p, s) compares the candidate window with the pattern character by character.
int rabinKarp(String t, String p) {
int n = t.length(), m = p.length();
int B = 256, Q = 101, h = 1;
for (int i = 0; i < m - 1; i++)
h = (h * B) % Q; // B^(m-1) mod Q
int ph = 0, th = 0;
for (int i = 0; i < m; i++) {
ph = (B * ph + p.charAt(i)) % Q;
th = (B * th + t.charAt(i)) % Q;
}
for (int s = 0; s <= n - m; s++) {
if (ph == th && matchAt(t, p, s))
return s;
if (s < n - m) {
th = (B * (th - t.charAt(s) * h)
+ t.charAt(s + m)) % Q;
if (th < 0) th += Q;
}
}
return -1;
}- First loop:
h = Bm−1 mod Qis computed. This is the weight of the outgoing character. - Second loop:
ph(the pattern hash) andth(the hash of the first window) are computed with Horner's method: at each step the previous value is multiplied byBand the new character is added. This loop takes O(m). - Main loop: for each shift, the hashes are compared first. Thanks to
&&,matchAtis called only if the hashes are equal. If there is no match and the end of the text has not been reached,this updated with the rolling formula. - The line
if (th < 0) th += Q;fixes Java's negative-remainder problem. The expressionth - t.charAt(s) * his often negative, and the%operator returns a negative remainder.
We trace the code with the call rabinKarp("abracadabra", "cad"). Here n = 11 and m = 3. h = 2562 mod 101 = 88. The pattern hash is ph = (99 · 2562 + 97 · 256 + 100) mod 101 = 11 (c = 99, a = 97, d = 100). The hash of the first window "abr" is 4.
s | Window | th | Decision | Out / in | Raw | % 101 | New th |
|---|---|---|---|---|---|---|---|
| 0 | abr | 4 | 4 ≠ 11, skip | a (97) / a (97) | −2,184,095 | −71 | 30 |
| 1 | bra | 30 | 30 ≠ 11, skip | b (98) / c (99) | −2,199,965 | −84 | 17 |
| 2 | rac | 17 | 17 ≠ 11, skip | r (114) / a (97) | −2,563,743 | −60 | 41 |
| 3 | aca | 41 | 41 ≠ 11, skip | a (97) / d (100) | −2,174,620 | −90 | 11 |
| 4 | cad | 11 | 11 = 11: matchAt verifies | "cad" = "cad": 4 is returned | |||
In the trace, the hashes differ in four windows and the characters are never looked at. A character comparison, over three characters, is made only in the fifth window. All the "raw" values in the table are negative. Java's % operator therefore gives a negative remainder at every step, and the correction line runs at every step. If this line were forgotten, the hash of the second window would be −71 instead of 30. The later hashes would come out wrong too, and the hash of the "cad" window might never equal 11.
Choosing a large Q but staying with the int type. In the code above Q = 101, and the intermediate values do not exceed about ±6.6 · 106; int is enough. To reduce spurious hits one can choose a prime such as Q = 109 + 7. Then even the product B * th reaches 2.56 · 1011, while the int limit is about 2.1 · 109. Overflow is silent; the hashes come out wrong and real matches may be missed. In that case the arithmetic must be done in long.
9.5.5Analysis and multiple patterns
The cost of Rabin-Karp has two parts: the hash computations and the verifications. The hash computations always total O(m) + (n − m) · O(1) = O(n + m). The cost of verification depends on how many windows become candidates.
- Best and average case: if Q is a large prime, the probability that a random window's hash accidentally equals that of the pattern is about 1/Q. The expected number of spurious hits is (n − m + 1)/Q. For n = 106 and Q ≈ 109 this is about 0.001: most likely no spurious hit occurs in the whole text. If there are k real occurrences, the expected time is O(n + m + k · m); for a small number of occurrences, O(n + m).
- Worst case: if a bad Q is chosen, or the input is deliberately crafted to produce collisions, every window becomes a candidate. For example, for T = a…a and P = a…a every window is a real match and each is verified with m characters. The time is O(n · m).
The extra memory is O(1); only a few integers are kept. The real strength of Rabin-Karp shows not with a single pattern but with many patterns. The hashes of k patterns of the same length are put into a set (HashSet). The text is scanned once and the hash of each window is looked up in the set. Since a set lookup is O(1) on average, all the patterns are found in expected O(n + k · m) time. The same job with KMP or Boyer-Moore would require scanning the text k times.
List<Integer> rkMulti(String t, List<String> patterns) {
int n = t.length(), m = patterns.get(0).length();
int B = 256, Q = 101, h = 1;
for (int i = 0; i < m - 1; i++)
h = (h * B) % Q;
Set<Integer> hashes = new HashSet<>();
Set<String> patternSet = new HashSet<>(patterns);
for (String p : patterns) {
int ph = 0;
for (int i = 0; i < m; i++)
ph = (B * ph + p.charAt(i)) % Q;
hashes.add(ph);
}
List<Integer> positions = new ArrayList<>();
int th = 0;
for (int i = 0; i < m; i++)
th = (B * th + t.charAt(i)) % Q;
for (int s = 0; s <= n - m; s++) {
if (hashes.contains(th)
&& patternSet.contains(t.substring(s, s + m)))
positions.add(s);
if (s < n - m) {
th = (B * (th - t.charAt(s) * h)
+ t.charAt(s + m)) % Q;
if (th < 0) th += Q;
}
}
return positions;
}The code was run in Java: the call rkMulti("abracadabra", List.of("cad", "bra", "xyz")) returns [1, 4, 8]. "bra" occurs at 1 and 8, "cad" at 4; "xyz" is not in the text. The verification checks whether the window itself is in the set of patterns. This eliminates windows whose hash collides with that of some pattern but which equal no pattern.
This technique is the basis of plagiarism detection and of document similarity measurement. The hashes of all k-word pieces of one document are extracted and compared with the pieces of another document. The same idea extends to two dimensions: a small image block can be searched for inside an image using row and column hashes.
9.6Comparing the matching algorithms
The four algorithms answer the same question, but each is best under different assumptions. Table 9.13 puts their basic properties side by side.
| Algorithm | Key idea | Preprocessing | Average | Worst | Extra memory |
|---|---|---|---|---|---|
| Brute force | Tries every shift | none | O(n)* | O(n · m) | O(1) |
| KMP | LPS table, never moves back in the text | O(m) | O(n + m) | O(n + m) | O(m) |
| Boyer-Moore | Right to left; bad character and good suffix | O(m + σ) | sublinear | O(n · m)** | O(m + σ) |
| Rabin-Karp | Rolling hash comparison | O(m) | O(n + m) | O(n · m) | O(1) |
* For random text and a large alphabet; on repetitive text it approaches O(n · m). ** With the bad-character rule only; O(n + m) with the good-suffix rule and Galil's improvement.
Asymptotic bounds are only part of the picture. Table 9.14 gives the character comparison counts of the four methods on the examples used in these notes. The counts were obtained by running the algorithms in Python and Java. In KMP each pair of characters is counted once; re-checking the same pair in the if after leaving the while loop on equality is not counted separately. The Boyer-Moore column uses only the bad-character rule.
| Text / pattern | n, m | Brute force | KMP | Boyer-Moore | Horspool |
|---|---|---|---|---|---|
| "THIS IS A SIMPLE EXAMPLE" / "SIMPLE" | 24, 6 | 18 | 18 | 8 | 8 |
| "ABCABCDABABCDABCDABDE" / "ABCDABD" | 21, 7 | 37 | 24 | 12 | 12 |
| "ababcababcabababd" / "ababd" | 17, 5 | 33 | 22 | 8 | 8 |
| "LO LOELLO O HELLO" / "HELLO" | 17, 5 | 17 | 17 | 17 | 11 |
| "merhaba naber" / "abe" | 13, 3 | 15 | 14 | 7 | 7 |
| "aaaaaaaaaa" / "aaab" (no occurrence) | 10, 4 | 28 | 17 | 7 | 7 |
Three observations follow from the table. First, KMP is never worse than brute force. Its gain grows on repetitive texts, where the matched parts are long. On natural-language text (the SIMPLE row) the two methods do almost the same work. Second, Boyer-Moore is far ahead in most rows. In the last row the worst input for brute force is one of the easiest for Boyer-Moore: the b at the right end of the pattern mismatches at the first comparison of every alignment, and the pattern moves ahead each time. Third, no method is best on every input. In the HELLO row the basic bad-character rule is no better than brute force, while Horspool is better.
A rough roadmap for choosing:
- KMP when a guarantee is needed. It is preferred for stream data (data arriving over a network that cannot be read back) or in real-time systems where the worst-case bound matters.
- Boyer-Moore or Horspool for long patterns and natural-language text. This is the fastest option in practice in text editors and command-line tools.
- Rabin-Karp for many patterns. Many patterns of the same length are searched in a single pass: plagiarism checking, virus signatures.
- Brute force for short patterns and short texts. It needs no preprocessing, its code is short, and it needs no extra memory. For patterns of a few characters the setup cost of the other methods can exceed their gain.
9.7String compression
The second topic of the chapter is storing and transmitting text, or data in general, with fewer bits. Compression saves disk space and network bandwidth. If the size of a file is halved, its download time is roughly halved as well. Compression algorithms find the redundancy in data, that is, the repeated or predictable parts, and write them in a shorter form.
9.7.1Lossless and lossy compression
In lossless compression, when the compressed data is decompressed the original data is recovered exactly, bit for bit. In lossy compression, details considered perceptually unimportant are discarded and the decompressed data is only close to the original.
The compression ratio is the ratio of the compressed size to the original size. The smaller the ratio, the better the compression; a ratio above 1 means the data has grown.
Lossy compression is used in JPEG images and MP3 audio. Discarding color transitions in a photograph that the eye cannot notice gives a large saving. For text, however, lossy compression is unsuitable. Changing a single character in a program breaks it; changing a single digit in a contract changes its meaning. This is why text, programs, and PNG and GIF images are compressed losslessly. The two methods in this chapter, RLE and LZW, are lossless.
An example of using the ratio: if a text of 15 characters shrinks to 8 characters, the ratio is 8/15 ≈ 0.53; the data has roughly halved. In some sources the ratio is given the other way round (original / compressed) or as a percentage saving. These notes use the definition given in the slides.
9.7.2No method shrinks every input
Compression has an insurmountable limit. No lossless method can shrink every input. This result rests on a simple counting argument, the pigeonhole principle: if k + 1 pigeons are placed in k holes, at least one hole contains two pigeons.
No lossless compression method can map all inputs of length N bits to shorter bit strings.
Proof. The number of distinct inputs of N bits is 2N. The number of bit strings shorter than N (including the empty string) is 20 + 21 + … + 2N−1 = 2N − 1. If every input were mapped to a shorter string, 2N inputs would be spread over 2N − 1 outputs. By the pigeonhole principle, at least two different inputs would land on the same output. The decompressor could not tell which input an output came from, and the method could not be lossless. ∎
For example, there are 256 distinct 8-bit bytes, but only 255 distinct bit strings shorter than 8 bits. The practical consequence of the theorem is this: compression algorithms target a particular kind of redundancy. They shrink inputs that contain that redundancy and enlarge slightly those that do not. When evaluating RLE and LZW, the question to ask is which redundancy they capture and on which inputs they fail. The fact that compressing an already compressed file gains almost nothing has the same cause.
9.8Run-length encoding (RLE)
Run-length encoding (RLE) is one of the simplest compression methods. The redundancy it captures is the consecutive repetition of the same symbol.
9.8.1Runs
A longest stretch of consecutive repeats of the same character in a string is called a run. RLE replaces each run with a pair consisting of the run's length and the character.
The steps of the method are: scan the text from left to right, count consecutive repeats, write the count and the character side by side for each run, and store the result as the compressed text. Since the text is scanned once, the time is O(n).
The 15-character text "AAAAABBBCCCCDDD" becomes "5A3B4C3D": 8 characters, ratio 8/15 ≈ 0.53. If there are long runs the gain is large: a text of 1000 a's becomes "1000a", that is, 5 characters.
If there is little repetition, RLE does not help and can even hurt. In "ABCD" every run is a single character and the result is "1A1B1C1D": 4 characters grow to 8, a ratio of 2. As the pigeonhole principle predicts, RLE enlarges inputs that contain no runs. An input that is repetitive but has no consecutive repeats, such as "abababab", becomes "1a1b1a1b1a1b1a1b"; 8 characters grow to 16. RLE cannot see this kind of repetition.
The natural uses of RLE are data with long flat regions. Fax machines encode the lines of black-and-white pages with RLE; most of a line is white. Older image formats such as BMP, PCX, and TIFF, and simple icons, also use RLE.
9.8.2Java code and trace
String rleEncode(String s) {
StringBuilder result = new StringBuilder();
int n = s.length();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
int count = 1;
while (i + 1 < n &&
s.charAt(i + 1) == c) {
count++;
i++;
}
result.append(count).append(c);
}
return result.toString();
}- Outer loop:
istops at the first character of each new run.cis this character andcountstarts at 1. - Inner loop: as long as the next character is the same as
c,countandiincrease together. The conditioni + 1 < nis checked first; at the end of the textcharAtdoes not read outside the string. - Writing: when the inner loop finishes,
iis at the last character of the run. The count and the character are appended to the result. Thei++of the outer loop carriesito the start of the next run.
Because the inner loop also increments i, the code is linear despite the nested loops: each character is visited once, either in the outer loop or in the inner loop. The total time is O(n). The result is built with a StringBuilder; String concatenation creates a new object at every append and could lead to O(n2) time.
| Run | i at start | c | Inner iterations | i, count at end | result |
|---|---|---|---|---|---|
| 1 | 0 | A | 4 | 4, 5 | "5A" |
| 2 | 5 | B | 2 | 7, 3 | "5A3B" |
| 3 | 8 | C | 3 | 11, 4 | "5A3B4C" |
| 4 | 12 | D | 2 | 14, 3 | "5A3B4C3D" |
9.8.3Decoding and multi-digit counts
Decoding RLE is the reverse of compression: for each (count, character) pair, the character is written count times. Text-form RLE has one subtlety: counts can have several digits. When decoding "12A3B", if "1" is read alone, the output turns into something meaningless like "one 2". The correct reading is to accumulate the digits until a letter arrives and form a single number.
String rleDecode(String s) {
StringBuilder result = new StringBuilder();
int num = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
} else {
for (int k = 0; k < num; k++)
result.append(c);
num = 0;
}
}
return result.toString();
}In the code, num is the number formed from the digits read so far. Whenever a digit arrives, the old value is multiplied by 10 and the digit added, as in the decimal system: for "12", first 1, then 1 · 10 + 2 = 12. When a letter arrives, it is written num times and num is reset. The code was run in Java: rleDecode("12A3B1C") produces twelve A's, three B's, and one C; rleDecode("5A3B4C3D") returns the original text. The time is linear in the length of the output.
This method has a limit: if the text itself contains digits, counts and characters get mixed up. Twelve repeats of the character "3" would be written "123", and the question "123 of what?" would go unanswered. Byte-level RLE solves this problem by keeping the counts in separate bytes.
9.8.4Byte-level RLE and the flag byte
In real files RLE works on bytes. In its simplest form each run is written in two bytes: first the count, then the code of the character. The count must fit in one byte; runs longer than 255 are split into several runs. This format eliminates the digit problem, but in regions without repetition it doubles every character to two bytes.
RLE with a flag reduces this loss. Only long runs are written, as a three-byte group that starts with a special flag byte: flag, count, character. The characters in short runs are left as they are. When the decoder sees a flag byte it reads the next two bytes as the count and the character; when it sees any other byte it writes it directly to the output.
Let the text be "aaaaaaaaaabbbbbbececececececdddddddddddddddecb" (46 bytes). The flag byte is 255; a = 97, b = 98, c = 99, d = 100, e = 101.
- Runs. 10 a's and 6 b's are followed by twelve single-character runs (e c e c … e c). Then there are 15 d's and the single characters e, c, b: 18 runs in all.
- RLE without a flag. Each run takes 2 bytes: 18 · 2 = 36 bytes. The sequence begins: 10 97 06 98 01 101 01 99 …; every character in the non-repeating region takes 2 bytes.
- RLE with a flag. The three long runs are written in three bytes each: 255 10 97, 255 06 98, and 255 15 100. That is 9 bytes. The remaining 15 single characters stay as they are: 15 bytes. Total 9 + 15 = 24 bytes.
- Ratios. Without a flag 36/46 ≈ 0.78, with a flag 24/46 ≈ 0.52.
The full sequence of the flagged format: 255 10 97 255 06 98 101 99 101 99 101 99 101 99 101 99 101 99 255 15 100 101 99 98.
The value of the flag byte can also occur in the text. If a character with value 255 were written directly, the decoder would mistake it for a flag. So this character too must be written in an escape form, for example as the triple 255 1 255. How long a run must be to count as "long" is also a design decision. The three-byte group pays off only for runs of four or more. For a run of three characters the two ways of writing have the same length; for a run of two, writing the characters as they are is shorter.
9.8.5RLE in images
RLE is most effective on images with large flat areas. In a black-and-white image each row is scanned from left to right and pixels of the same color are counted until the color changes.
The 42-pixel image in Figure 9.22 is written with 18 runs. The rows are encoded separately; the first row becomes "W1B1W3B1W1" and consists of five runs. The run lengths of each row add up to 7. This provides a check: if the decoder does not produce 7 pixels in every row, the data is corrupt.
Since there are only two colors, the color name need not even be written. The runs are assumed to alternate between white and black; if a row starts with black, the first white run is written with length 0. The fax standard uses this idea and additionally compresses the run lengths with variable-length codes. RLE is very effective on images with large flat areas (drawings, text scans). In photographs, however, neighboring pixels are rarely exactly the same color and RLE is ineffective.
In color images, runs are defined at the pixel level. The color of each pixel is a three-byte (R, G, B) triple, and a run consists of consecutive pixels of the same color.
Compare the raw and RLE sizes of the image in Figure 9.23. Each run is written with one count byte and three color bytes.
- Raw size. 64 pixels, 3 bytes each: 64 · 3 = 192 bytes.
- Runs. The pixels are read row by row. If the same color continues at the end of a row, the run spills into the next row. The last two blues of the first row and the first blue of the second row form a single run of "3 blue". The image splits into 33 runs. The first runs are 2 blue, 4 black, 3 blue, 1 black, 4 yellow, 1 black.
- RLE size. 33 · (1 + 3) = 132 bytes. The ratio is 132/192 ≈ 0.69.
If runs were cut at row boundaries, the number of runs would rise to 38 and the RLE size would be 38 · 4 = 152 bytes. On a small, detailed image the gain is limited; if the same face were drawn at 800 × 800 pixels, the runs would be a hundred times longer and the ratio would be much smaller.
9.9Lempel-Ziv-Welch (LZW)
RLE sees only consecutive repetition. In natural-language text, however, repeats are mostly not consecutive: words such as "the", "and", "of", or suffixes such as "-ing" and "-ed" are scattered throughout the text. LZW captures this kind of repetition.
9.9.1The dictionary idea
In 1977 and 1978 Abraham Lempel and Jacob Ziv published two dictionary-based compression methods (LZ77 and LZ78). In 1984 Terry Welch simplified LZ78 and brought it to a form that runs fast in hardware. The resulting method was named LZW and was used in the GIF, TIFF, and PDF formats and in Unix's compress program.
The essence of the method is this: the compressor numbers the strings it has seen before in a dictionary. When it meets the same string again, it writes the string's number in the dictionary, that is, its code, instead of the string itself. The dictionary is dynamic: it grows as compression proceeds. The dictionary is not sent along with the output. The decompressor rebuilds the same dictionary itself, applying the same rules as the compressor.
LZW compression starts with an initial dictionary containing all the single characters of the text. w starts as the empty string. For each character c of the text:
- If w + c is in the dictionary, set w ← w + c; the match is extended.
- Otherwise the code of w is written to the output, w + c is added to the dictionary under the next free code, and w ← c.
When the text ends, if w is not empty, its code is written to the output as well.
The rule is greedy: at each step the compressor writes the longest piece found in the dictionary. Then it adds that piece extended by one character to the dictionary. In this way the strings in the dictionary grow longer over time. Frequently repeated pieces are written with ever longer dictionary entries and a single code.
9.9.2Compression: Java code and trace
List<Integer> lzw(String s) {
Map<String, Integer> dict =
initialDict(s); // A=0, B=1, C=2
String w = "";
List<Integer> codes = new ArrayList<>();
for (char c : s.toCharArray()) {
String wc = w + c;
if (dict.containsKey(wc)) {
w = wc;
} else {
codes.add(dict.get(w));
dict.put(wc, dict.size());
w = "" + c;
}
}
if (!w.isEmpty())
codes.add(dict.get(w));
return codes;
}- Dictionary:
Map<String, Integer>maps each string to its code.initialDict(s)numbers the distinct characters of the text starting from 0; in this example A = 0, B = 1, C = 2. - Extension: if
wc = w + cis in the dictionary, onlywgrows; nothing is written to the output. - Writing and adding: if
wcis not in the dictionary, the code ofwis written.wcis added with the codedict.size(), which is always the next free code.wgoes back to the string consisting ofcalone. - The final
w: when the loop ends,wstill holds a piece that has not been written, and its code is appended.
We trace the code with the call lzw("ABABCABABCA"). Table 9.16 gives the state after each character.
| Step | c | w + c | In dictionary? | Output | Added | New w |
|---|---|---|---|---|---|---|
| 1 | A | A | yes (0) | — | — | A |
| 2 | B | AB | no | 0 | 3 = AB | B |
| 3 | A | BA | no | 1 | 4 = BA | A |
| 4 | B | AB | yes (3) | — | — | AB |
| 5 | C | ABC | no | 3 | 5 = ABC | C |
| 6 | A | CA | no | 2 | 6 = CA | A |
| 7 | B | AB | yes (3) | — | — | AB |
| 8 | A | ABA | no | 3 | 7 = ABA | A |
| 9 | B | AB | yes (3) | — | — | AB |
| 10 | C | ABC | yes (5) | — | — | ABC |
| 11 | A | ABCA | no | 5 | 8 = ABCA | A |
| end | — | — | — | 0 | — | — |
The output is 0 1 3 2 3 5 0: 7 codes instead of 11 symbols. Step 10 shows how the dictionary pays off. The "ABC" added at step 5 is seen again in the second half of the text and is written with a single code (5). In so short a text the dictionary can be used only a few times. In long texts the strings in the dictionary grow longer and the gain increases.
The running time works out as follows: for each character one dictionary lookup and at most one insertion are done. If the dictionary is kept in a hash table, each operation takes O(1) on average and the total time is O(n). There is a subtlety in this count: the string w + c is rebuilt at every step and its hash is computed; the cost is proportional to the length of w. Practical implementations therefore keep the dictionary as a trie, or store each entry as a pair (prefix code, last character). Then each step really takes constant time.
9.9.3Decompression
The decompressor knows only the initial dictionary. It builds the rest of the dictionary itself, in the same order as the compressor, as it reads the codes. The rule is: for each new code k, write e = dict[k] to the output, add w + e[0] to the dictionary, and set w ← e. Here e[0] is the first character of e.
Why the added string is w + e[0] follows from the compressor's behavior. When the compressor wrote w, it added w + c to the dictionary; c was the first character of the next piece. At the moment the decompressor decodes w, it does not yet know the next piece. When it decodes the next code it learns the first character of that piece and completes the missing entry. The decompressor therefore always stays one step behind in the dictionary.
| Code | Output (e) | Added (w + e[0]) |
|---|---|---|
| 0 | A | — |
| 1 | B | 3 = AB |
| 3 | AB | 4 = BA |
| 2 | C | 5 = ABC |
| 3 | AB | 6 = CA |
| 5 | ABC | 7 = ABA |
| 0 | A | 8 = ABCA |
Writing the outputs one after another gives A·B·AB·C·AB·ABC·A = ABABCABABCA; the original text is back. The codes 3–8 built by the decompressor are exactly the same as the compressor's.
In one situation this rule gets stuck. The decompressor can read a code that is not yet in its dictionary. This can happen in only one way: the code is the one the decompressor would add next.
If the decompressor reads a code k that is not yet defined in its dictionary, then k is the next free code and e = w + w[0]. Here w is the decoding of the previous code.
Proof. Because the decompressor is one step behind, the only code that the compressor has defined but the decompressor has not yet is the code the compressor added most recently. The compressor added this code as w + c when it wrote w; c is the first character of the next piece. The next piece is exactly this new code: e = w + c. Since e begins with w, its first character is w[0]. And c is the first character of the next piece, that is, of e. Hence c = e[0] = w[0] and e = w + w[0]. ∎
This case arises when the compressor uses an entry immediately after adding it. For that, the text must contain a piece of the form c · S · c · S · c with cS in the dictionary. Here c is a character and S is a string. For this reason the literature calls it the "cScSc case."
Compress "ABABABA" with the dictionary A = 0, B = 1, and then decompress it.
- Compression. AB is not in the dictionary: 0 is written and 2 = AB is added. BA is not: 1 is written and 3 = BA is added. AB is present but ABA is not: 2 is written, 4 = ABA is added, and w = A. In the last three characters AB and ABA are found in the dictionary; w grows to ABA. When the text ends, the code 4 of the remaining w is written. The output is 0 1 2 4.
- Decompression. 0 → A. 1 → B; 2 = AB is added. 2 → AB; 3 = BA is added.
- The special case. The next code is 4, but the decompressor's dictionary goes only up to 3. By the theorem, e = w + w[0] = AB + A = ABA. ABA is written to the output and 4 = ABA is added.
- Result. A·B·AB·ABA = ABABABA ✓.
9.9.4Example: a DNA sequence
LZW does not depend on the alphabet. For DNA sequences the initial dictionary is the four nucleotides: A = 0, T = 1, G = 2, C = 3. Let the text be "ATGATCATGAG" (11 symbols).
| Code | Added to the dictionary | Output |
|---|---|---|
| 4 | AT | 0 (A) |
| 5 | TG | 1 (T) |
| 6 | GA | 2 (G) |
| 7 | ATC | 4 (AT) |
| 8 | CA | 3 (C) |
| 9 | ATG | 4 (AT) |
| 10 | GAG | 6 (GA) |
| — | (final w = G) | 2 (G) |
The output is 0 1 2 4 3 4 6 2: 8 codes instead of 11 symbols. When "AT" is seen the second and third time, it is written with a single code (4); "GA" is written with a single code (6) when seen the second time. The code (2) of the w = G left after the loop is appended at the very end. In real genomes the repeated sequences are very long, so the dictionary entries grow long too.
9.9.5The ASCII dictionary and the special case
In practice the initial dictionary is all 256 single-byte values (0–255; the first 128 are ASCII); which characters occur in the text is not looked at. For example a = 97, b = 98, c = 99. New strings are numbered from 256. This also removes the need to send the initial dictionary.
| Output | Added to the dictionary |
|---|---|
| 97 (a) | 256 = aa |
| 97 (a) | 257 = ab |
| 98 (b) | 258 = ba |
| 256 (aa) | 259 = aac |
| 99 (c) | 260 = ca |
| 257 (ab) | 261 = aba |
| 261 (aba) | 262 = abac |
| 99 (c) | 263 = cb |
| 98 (b) | (final w = b) |
The text shrinks to 9 codes: 97 97 98 256 99 257 261 99 98. The sixth and seventh rows of the table contain the special case. When "ab" (257) is written, 261 = "aba" is added to the dictionary. The next piece is exactly "aba", and 261 is used immediately. When the decompressor reads 261, its dictionary still has codes only up to 260.
The decompression code handles the special case with a single conditional expression:
String lzwDecode(List<Integer> codes) {
List<String> dict =
initialDict(); // 0..255: byte values
String w = dict.get(codes.get(0));
StringBuilder s = new StringBuilder(w);
for (int i = 1; i < codes.size(); i++) {
int k = codes.get(i);
String e = k < dict.size()
? dict.get(k)
: w + w.charAt(0); // special case
s.append(e);
dict.add(w + e.charAt(0));
w = e;
}
return s.toString();
}- Start: the dictionary is filled with the 256 single-byte values (0–255; the first 128 are ASCII). The first code is always a single character; it is decoded directly and written to the output.
- Decoding: if
k < dict.size(), the code is defined ande = dict.get(k). Otherwise it is the special case ande = w + w.charAt(0). - Adding: at each step
w + e.charAt(0)is appended to the end of the dictionary; in aListthe code of the new entry is automatically the next index.
k | In dictionary? | e | Added (w + e[0]) | Output (cumulative) |
|---|---|---|---|---|
| 97 | ASCII | a | — | a |
| 97 | ASCII | a | 256 = a + a = aa | aa |
| 98 | ASCII | b | 257 = a + b = ab | aab |
| 256 | yes | aa | 258 = b + a = ba | aabaa |
| 99 | ASCII | c | 259 = aa + c = aac | aabaac |
| 257 | yes | ab | 260 = c + a = ca | aabaacab |
| 261 | no (largest is 260) | ab + a = aba | 261 = ab + a = aba | aabaacababa |
| 99 | ASCII | c | 262 = aba + c = abac | aabaacababac |
| 98 | ASCII | b | 263 = c + b = cb | aabaacababacb |
The code was run in Java and the output "aabaacababacb" was confirmed. The time for decompression is linear in the length of the output.
9.9.6Dictionary size and code width
How many bits are used to write the codes depends on the size of the dictionary. The 256 single-byte values (0–255; the first 128 are ASCII) can be written with 8 bits. When new entries are added to the dictionary, the codes no longer fit in 8 bits. So LZW implementations start with 9-bit codes and increase the code width by one bit each time the dictionary passes 512, 1024, and so on.
This calculation shows why a reduction in the number of codes is not directly a gain in bits. In the ASCII example the text is 13 bytes, that is, 104 bits. The 9 codes at 9 bits each take 9 · 9 = 81 bits; the ratio is 81/104 ≈ 0.78. If the "ABABCABABCA" example were encoded with ASCII, 7 codes (63 bits) would be written instead of 11 bytes (88 bits). On short texts the gain is small. On long, repetitive texts a single code stands in for dozens of characters and the gain is large.
As the dictionary grows, two problems arise: the code width (number of bits) increases and the memory taken by the dictionary grows. In practice the dictionary is limited. In GIF the largest code width is 12 bits; the dictionary holds at most 212 = 4096 entries. When the dictionary is full it is either frozen (no new entries are added) or reset and rebuilt. Resetting prevents old entries from taking up space when the content of the text changes (for example, when moving from the text part of a file to a numeric part).
Two mistakes are very common in LZW. The first is forgetting to write the code of the w left after the loop in compression. In the "ABABCABABCA" example this loses the last A (0), and the decompressed text becomes "ABABCABABC". The second is not handling the not-yet-defined code in decompression. dict.get(k) throws an IndexOutOfBoundsException when k == dict.size(). The bug appears only on texts of the cScSc form, so it can slip past simple tests.
9.9.7LZ78: the ancestor of LZW
In LZ78, on which LZW is based, the dictionary starts empty. The output consists not of codes but of (index, character) pairs: the index of the longest match in the dictionary (0 if there is no match) and the character that follows it. Each pair also adds a new entry to the dictionary.
List<String> lz78(String s) {
Map<String, Integer> dict =
new HashMap<>();
List<String> out = new ArrayList<>();
String w = "";
for (char c : s.toCharArray()) {
if (dict.containsKey(w + c)) {
w = w + c; // extend
} else {
int k = w.isEmpty() ? 0
: dict.get(w);
out.add("(" + k + ", " + c + ")");
dict.put(w + c, dict.size() + 1);
w = "";
}
}
if (!w.isEmpty()) // last piece
out.add("(" + dict.get(w) + ")");
return out;
}The code is very similar to the LZW code. The differences are these: if w + c is not in the dictionary, both the index of w and the character c are written; then w goes back to the empty string. Indices start at 1, because 0 is reserved for the empty prefix. When the text ends, w may hold an unwritten piece; this piece is in the dictionary and is written after the loop with its index alone. For example, in the text "aabaacababacb" the final b is entry number 6 in the dictionary and "(6)" is appended to the end of the output. If this line is forgotten, the end of the text is lost. In the example in the table the text ends exactly with a pair, w is left empty, and the last line does not run.
| Position | c | w + c | In dictionary? | Output | Added |
|---|---|---|---|---|---|
| 0 | a | a | no | (0, a) | 1 = a |
| 1 | a | a | yes | — | — |
| 2 | b | ab | no | (1, b) | 2 = ab |
| 3 | a | a | yes | — | — |
| 4 | a | aa | no | (1, a) | 3 = aa |
| 5 | c | c | no | (0, c) | 4 = c |
| 6–7 | a, b | a, ab | yes, yes | — | — |
| 8 | c | abc | no | (2, c) | 5 = abc |
| 9–11 | a, b, c | a, ab, abc | yes ×3 | — | — |
| 12 | b | abcb | no | (5, b) | 6 = abcb |
The text becomes 6 pairs: (0, a) (1, b) (1, a) (0, c) (2, c) (5, b). The pieces are a, ab, aa, c, abc, and abcb; each piece is a piece already in the dictionary extended by one character.
Welch's change comes down to a single idea: start the dictionary with all the single characters. In LZ78, when a character is seen for the first time a pair (0, c) is needed, because it is not in the dictionary. In LZW every single character is in the dictionary from the start. So there is no need to write characters in the output; only codes are written, and the character that follows each code is recovered from the first character of the next code.
Lempel and Ziv's other method, LZ77 from 1977, keeps no dictionary. Instead it looks back in a sliding window of the last few kilobytes and writes repeats as (backward distance, length) pairs. The LZ77 family is the basis of the DEFLATE format used by ZIP and gzip, and of PNG images.
9.9.8Comparing RLE and LZW
| RLE | LZW | |
|---|---|---|
| Redundancy captured | consecutive repeats of the same symbol | repeated strings (even if not consecutive) |
| Extra structure | none | dictionary (hash table or trie) |
| Time | O(n) | O(n) (dictionary access O(1) on average) |
| Worst case | output doubles if there are no repeats | little gain on short or random data, code width grows |
| Use | fax, BMP/PCX, simple graphics | GIF, TIFF, PDF, Unix compress |
Both methods are lossless and both run in linear time; for LZW this requires keeping the dictionary as a trie or a table keyed by (code, character), not with String concatenation. The structure of the data decides the choice. On images with long flat areas RLE stands out for its simplicity. In natural-language text or programs, consecutive repeats are few, but repeated words and patterns are plentiful; here LZW is far more effective. The pigeonhole principle says that both will enlarge some inputs: "abababab" for RLE, and short random data for LZW, are of this kind.
9.10Common mistakes
The mistakes mentioned throughout the chapter are collected here. Each one arises from a small detail in the code, yet produces a wrong result, a crash, or an infinite loop.
- Loop bound. Writing
i < n - min brute force skips the last shift (s = n − m). The correct form isi <= n - m. If the pattern occurs at the very end of the text, it is not found. - Defining LPS wrongly. The pattern itself is not counted: lps("aaaa") = [0, 1, 2, 3], not [1, 2, 3, 4]. In KMP,
lps[q - 1]is used at a mismatch, notlps[q]. - Negative shift. In Boyer-Moore j − last[c] can be zero or negative: this happens when the last occurrence of c is to the right of j. If
max(1, …)is forgotten, the pattern moves backward or the algorithm loops forever. - Including the last character in the Horspool table. If the last character enters the table, its shift is 0 and the pattern stands still. The table is built from P[0..m−2] only.
- Trusting hash equality. In Rabin-Karp, equal hashes do not mean a match; a candidate window must be verified character by character. In Java
%can give a negative result: the lineif (th < 0) th += Q;is needed. With a large Q,intoverflows;longmust be used. - Multi-digit counts in RLE. When decoding "12A", reading the count as a single digit is wrong (one '2'?). Digits must be accumulated until a letter arrives, or the counts must be written in separate bytes.
- The final w and the special case in LZW. Forgetting to write the code of the w left after the loop loses the end of the text; the same line is needed in LZ78. Not handling the not-yet-defined code (w + w[0]) when decoding causes a crash on texts of the cScSc form.
- Miscounting comparisons. A mismatch at an alignment is also a comparison. In brute force every alignment makes at least one comparison; the total is at least n − m + 1.
9.11Summary
- String matching is the problem of finding all shifts at which a pattern P of length m occurs in a text T of length n. The possible shifts are 0 ≤ s ≤ n − m.
- Brute force tries every shift from left to right. It has no preprocessing and no extra memory. It is O(n) on average and O(n · m) in the worst case, with (n − m + 1) · m comparisons. Its flaw is that it throws away what it learns at a mismatch.
- KMP builds, in O(m), the table where lps[q] is the length of the longest proper prefix-suffix of P[0..q]. At a mismatch q = lps[q − 1] is set and the text pointer never moves back. It is O(n + m) even in the worst case; the amortized argument gives at most 2n comparisons.
- Boyer-Moore compares from right to left and shifts by the larger of s += max(1, j − last[c]) (bad character) and the good-suffix rule. It is O(n/m) in the best case and the fastest in practice. Horspool is a one-table simplification that shifts according to the last character of the alignment.
- Rabin-Karp updates a polynomial rolling hash in O(1). If the hashes are equal the window is verified. The expected time is O(n + m) and the worst time O(n · m). It can search for many patterns of the same length in one pass.
- No lossless compression method can shrink every input (the pigeonhole principle). The compression ratio is the compressed size divided by the original size.
- RLE writes each run as a (count, symbol) pair and takes O(n). It doubles the data if there are no repeats; a flag byte reduces this loss. It is effective on images with flat areas.
- In LZW, if w + c is in the dictionary, w is extended; otherwise the code of w is written and w + c is added to the dictionary. The decompressor builds the dictionary itself and stays one step behind. When an undefined code is read, e = w + w[0]. LZ78 differs in that its dictionary starts empty and it writes (index, character) pairs.
9.12Key terms
- string
- alphabet
- substring
- pattern
- string matching
- prefix
- suffix
- brute force (naive)
- Knuth-Morris-Pratt (KMP)
- LPS table
- amortized analysis
- Boyer-Moore algorithm
- bad character rule
- good suffix rule
- Rabin-Karp algorithm
- rolling hash
- compression
- run-length encoding (RLE)
- Lempel-Ziv-Welch (LZW)
Further terms defined in these notes: shift, proper prefix, last-occurrence table, Horspool shift table, spurious hit, polynomial hash, lossless and lossy compression, compression ratio, run, flag byte, LZ78.
9.13Test Yourself
What is the LPS table of the pattern "abaabab"?
Answer
[0, 0, 1, 1, 2, 3, 2]. At q = 3 the longest prefix-suffix piece of "abaa" is "a". At q = 5, "aba" (3) is found for "abaaba". At q = 6, "abaa" and "abab" mismatch; k falls back to lps[2] = 1 and "ab" (2) is found.
What value does
bruteForce("aaaab", "ab")return and how many comparisons does it make? How many comparisons does Boyer-Moore make with the bad-character rule alone?Answer
It returns 3. At s = 0, 1, 2 brute force matches a and mismatches b (3 × 2 = 6), and at s = 3 both characters match (2): 8 in total. At each alignment Boyer-Moore compares the b at the right end with the a in the text; since last[a] = 0, it shifts by 1. That is 1 comparison each at s = 0, 1, 2 and 2 at s = 3: 5 in total.
In a KMP search for the pattern "aabaab", "aabaa" has matched (q = 5) and the next text character is not b. What value does q take, and by how many positions has the pattern shifted?
Answer
The LPS table is [0, 1, 0, 1, 2, 3]. q = lps[4] = 2: the "aa" at the end of "aabaa" is also a prefix. The shift is 5 − 2 = 3. Then the same text character is compared with P[2] = b; if that mismatches too, q = lps[1] = 1.
What is the last-occurrence table of the pattern "ANANAS"? In the text "BANANAS ANANAS", what is the first shift with the bad-character rule alone?
Answer
last[A] = 4, last[N] = 3, last[S] = 5, and −1 for the others. At s = 0, P[5] = S mismatches T[5] = A; the shift is max(1, 5 − 4) = 1. At s = 1 all six characters match: 7 comparisons in total.
What is the Horspool shift table for "ANANAS"? If S lies under the last character of the alignment, by how much does the pattern shift?
Answer
Only P[0..4] = ANANA enters the table: A → 5 − 4 = 1, N → 5 − 3 = 2, other → 6. Since S occurs only at the last position, it is not in the table and shifts by 6.
Let B = 10, Q = 7, and the characters digits. We search for "18" in the text "27182818". Which windows become candidates, and which are spurious hits?
Answer
h("18") = 18 mod 7 = 4. The window hashes are: 27 → 6, 71 → 1, 18 → 4, 82 → 5, 28 → 0, 81 → 4, 18 → 4. The candidates are s = 2, 5, 6. The "81" at s = 5 is a spurious hit; s = 2 and s = 6 are real occurrences.
How is the text "WWWWWWWWWWWWBWWW" (16 characters) written with character RLE? How many bytes do the byte-level formats take, without a flag and with a flag (runs of four or more written with the flag)?
Answer
"12W1B3W": 7 characters, ratio 7/16 ≈ 0.44. Without a flag: 3 runs × 2 = 6 bytes. With a flag: 3 bytes for the 12 W's, and the B and three W's as they are, 4 bytes: 7 bytes. Since this input has no non-repeating region, the format without a flag is shorter.
With the dictionary A = 0, which codes come out when "AAAAAAA" (7 A's) is compressed with LZW? How many times does the decompressor meet the special case when decoding these codes?
Answer
The output is 0 1 2 0; 1 = AA, 2 = AAA, 3 = AAAA are added to the dictionary. When decoding: 0 → A. 1 is undefined: e = A + A = AA. 2 is also undefined: e = AA + A = AAA. 0 → A. The special case arises twice; the output is A·AA·AAA·A = 7 A's.
Into which pairs does LZ78 turn the string "aaaaaaaaaa" of ten a's?
Answer
(0, a) (1, a) (2, a) (3, a). The pieces are a, aa, aaa, aaaa; their lengths sum to 1 + 2 + 3 + 4 = 10. Since the piece lengths grow by one at each step, a run of length n is written with about √(2n) pairs.
In a text of a million characters, a pattern of 10 letters made up of characters that never occur in the text is searched for. About how many comparisons does Boyer-Moore make? What is the minimum number of comparisons for brute force and KMP?
Answer
In Boyer-Moore the character at the right end mismatches at every alignment and the pattern jumps 10 positions: about n/m = 105 comparisons. Brute force and KMP look at every text character at least once: about 106 comparisons. In this best case Boyer-Moore does ten times less work.
9.14Further reading
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapter 32: gives Rabin-Karp, matching with finite automata, and the KMP prefix function with proofs; it also touches on suffix arrays.
- R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Sections 5.3 and 5.5: present the automaton version of KMP, Java code for Boyer-Moore and Rabin-Karp, and RLE, Huffman, and LZW compression.
- D. Gusfield, Algorithms on Strings, Trees, and Sequences (1997): treats in detail how to build the good-suffix table in O(m) time, the Z algorithm, and bioinformatics applications.
- K. Sayood, Introduction to Data Compression (5th ed., 2017): covers dictionary-based methods (LZ77, LZ78, LZW) and the information-theoretic limits of lossless compression.
9.15References
- R. S. Boyer, J S. Moore, “A Fast String Searching Algorithm”, Communications of the ACM 20(10), 1977.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 (Chapter 32: String Matching).
- M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014 (Chapter 13).
- R. N. Horspool, “Practical Fast Searching in Strings”, Software: Practice and Experience 10(6), 1980.
- R. M. Karp, M. O. Rabin, “Efficient Randomized Pattern-Matching Algorithms”, IBM Journal of Research and Development 31(2), 1987.
- D. E. Knuth, J. H. Morris, V. R. Pratt, “Fast Pattern Matching in Strings”, SIAM Journal on Computing 6(2), 1977.
- R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011 (Section 5.3: Substring Search, 5.5: Data Compression).
- T. A. Welch, “A Technique for High-Performance Data Compression”, IEEE Computer 17(6), 1984.
- J. Ziv, A. Lempel, “Compression of Individual Sequences via Variable-Rate Coding”, IEEE Transactions on Information Theory 24(5), 1978.
Related pages: Chapter 9 slides · © Sercan Külcü. All rights reserved.