Algorithms · Lecture Notes
Chapter 10: Advanced String Algorithms
Text is among the data types computers process most. A dictionary's words are put in order, and an email address typed into a form is validated. A spell checker suggests the correct word closest to a misspelled one. A compression program rearranges the letters of a file before shrinking it. All of these tasks rest on algorithms that work on strings. These notes take up four families of problems in turn. The first is sorting: the lexicographic order of strings, comparison-based sorting, and the LSD and MSD radix sorts, which make no comparisons at all. The second is parsing: regular expressions and their theoretical counterpart, finite state machines. The third is similarity: the Levenshtein distance, its dynamic programming table, and other measures such as the Hamming distance and the longest common subsequence. The fourth is transformation: the suffix array and the Burrows–Wheeler transform. For each algorithm the notes give Java code, a step-by-step trace, and a cost analysis.
Learning outcomes
- Sorting
- Compare strings in lexicographic order; carry out LSD and MSD radix sort step by step and explain the O(W · (N + R)) cost.
- Parsing
- Write and read regular expressions; design and draw a deterministic finite automaton (DFA) and run it on an input.
- Similarity
- Compute the Levenshtein distance with a dynamic programming table and read the edit sequence back from the table; compare it with the Hamming distance, the LCS, and the longest common substring.
- Transformation
- Build a suffix array and use it for searching; compute the Burrows–Wheeler transform and invert it.
10.1Four families of problems
A string is a finite sequence of characters drawn from an alphabet. The alphabet is the set of characters that may be used and is written Σ. For binary strings Σ = {0, 1}, and for DNA sequences Σ = {A, C, G, T}. In Java, each character of a String is a 16-bit char value. The size of the alphabet is written R: R = 128 for ASCII, or R = 256 for its extended form.
The problems posed on strings are many and varied, but most fall into one of four families. Each family answers a different question and uses a different algorithmic technique.
| Family | Question | Algorithms | Core technique |
|---|---|---|---|
| Sorting | In what order should the strings be arranged? | lexicographic comparison, LSD and MSD radix sort | comparison, counting |
| Parsing | Does the string fit a given format? What parts does it consist of? | regular expressions, finite state machines | automaton |
| Similarity | How close are two strings to each other? | Levenshtein, Hamming, LCS, longest common substring | dynamic programming |
| Transformation | How can a string be brought into a form that makes searching or compression easier? | suffix array, Burrows–Wheeler transform | sorting, binary search |
In the sorting family, strings are arranged as in a dictionary. Methods that compare strings character by character are general-purpose. Radix sort makes no comparisons at all; it treats each character as a digit and distributes the strings into groups. In the parsing family, a search pattern is written as a regular expression, and a finite state machine that recognizes this expression reads the input character by character. In the similarity family, the difference between two strings is measured by a number. The best known is the Levenshtein distance, the minimum number of single-character edits that turn one string into the other. In the transformation family, the string is rearranged: the suffix array speeds up searching by keeping all suffixes in sorted order, while the Burrows–Wheeler transform gathers equal letters together and so prepares the text for compression.
The four families share one thing: all of them exploit the structure of a string. Lexicographic order uses the left-to-right significance of the characters. A finite state machine summarizes the part of the input read so far in a single state. The Levenshtein distance is built from the distances between prefixes of the two strings. The suffix array and the BWT rest on the order that appears when all suffixes or rotations of a string are sorted. The terms prefix, suffix, and substring occur often in these notes. A prefix is a part taken from the beginning of a string and a suffix a part taken from its end. A substring is any part made of consecutive characters. For “banana”, for example, “ban” is a prefix, “ana” is a suffix, and “nan” is a substring.
10.2Lexicographic order
In a dictionary, words are arranged in a fixed order: “armut” comes before “elma”, and “elma” before “elmas”. The rule is simple, and computers use it unchanged. The only difference is that the computer learns the order of the letters not from a memorized alphabet but from character codes.
10.2.1The comparison rule
Let a and b be two strings. We say a is lexicographically smaller than b (a < b) if one of two cases holds. (1) The first position where the strings differ is some k, and a[k] < b[k]. (2) The strings are equal up to the end of a, and a is shorter than b; that is, a is a prefix of b. This order is called the lexicographic order.
The rule starts the comparison with the first characters. If they are equal, it looks at the second characters, and if those are equal, at the third. The first differing character decides the result, and no later character is examined. If one string runs out, the shorter one comes first. Table 10.2 shows what decides the outcome in four comparisons.
| Comparison | Decided by | Result |
|---|---|---|
| apple · banana | a < b (1st character) | apple first |
| apple · apricot | p < r (3rd character) | apple first |
| car · cart | “car” ran out | car first |
| Zebra · apple | 'Z' (90) < 'a' (97) | Zebra first |
The last row is surprising at first glance: a person would write “apple” before “Zebra”. The computer, however, finds the code of capital Z (90) smaller than the code of lowercase a (97) and takes no separate account of whether a letter is upper or lower case.
Lexicographic order is a total order: of any two different strings, one is smaller than the other, and the order is transitive. Strings can therefore be sorted like integers, and every sorting algorithm works on strings too. Only the cost of a comparison is no longer constant. Two integers are compared in a single operation. Two strings, in the worst case, require as many character comparisons as the length of the shorter one.
10.2.2Code trace: apple and apricot
A Java method that applies the rule directly is shown below. If the method returns a negative number, a comes first; if it returns a positive number, b comes first; zero means the two strings are equal. Java's String.compareTo works the same way.
int compare(String a, String b) {
int n = Math.min(a.length(), b.length());
for (int k = 0; k < n; k++) {
char x = a.charAt(k), y = b.charAt(k);
if (x != y)
return x - y; // first difference
}
return a.length() - b.length();
}n is the length of the shorter string, so the loop can compare at most that many characters. On each iteration, the k-th characters of the two strings are read as x and y. If the characters differ, x - y is returned. Subtracting two char values in Java yields the difference of their character codes, and the sign tells which character comes first. If the loop ends without finding a difference, the shorter string is a prefix of the longer one. In that case a.length() - b.length() is returned: the shorter string comes first, and the result is zero if the lengths are equal.
compare("apple", "apricot"). n = min(5, 7) = 5, so at most five characters can be compared.k | x | y | Comparison | Result |
|---|---|---|---|---|
| 0 | 'a' (97) | 'a' (97) | equal | move on to the next character |
| 1 | 'p' (112) | 'p' (112) | equal | move on to the next character |
| 2 | 'p' (112) | 'r' (114) | different | return 112 − 114 = −2 |
Because the result is negative, “apple” comes before “apricot”. The comparison ended after three characters; the last two letters of “apple” and the last four letters of “apricot” were never examined. The same method returns the following values on other inputs. For compare("car", "cart") the first three characters are equal and the shorter string runs out, so the result is 3 − 4 = −1. compare("Zebra", "apple") returns 90 − 97 = −7 at the first character. compare("kale", "kaba") returns 108 − 98 = 10 at the third character; the positive result shows that “kaba” comes first.
The cost of the method is proportional to the number of characters read up to the first differing one. In the worst case the two strings share a long common prefix and the cost is O(min(|a|, |b|)). No extra memory is used.
Assuming the return value can only be −1, 0, or 1. compareTo and compare return the difference of character codes or the difference of lengths: values such as −2, −7, or 10 are perfectly normal. The result should therefore be tested with < 0, not with == -1.
10.2.3Character codes and Turkish
To a computer, the “alphabet” is the table formed by character codes: ASCII, or Unicode, which contains it. In this table all capital letters (A = 65 … Z = 90) come before all lowercase letters (a = 97 … z = 122). Digits (0 = 48 … 9 = 57) come even before the letters. The Turkish letters ç, ğ, ı, ö, ş, ü have codes outside the ASCII table: for example ç = 231, ğ = 287, ı = 305, ş = 351. Sorted by code, they therefore all come after z.
As a result, sorting with compareTo differs from Turkish dictionary order. When “şeker” is compared with “zeytin”, 'ş' (351) is greater than 'z' (122), so “zeytin” comes first. In a Turkish dictionary, ş comes before z. Likewise “Zebra” comes before “apple”, and “Çorum” comes after “Zonguldak”. When Turkish dictionary order is needed, Java's java.text.Collator class is used with the Turkish locale (Collator.getInstance(new Locale("tr", "TR"))). This class takes the difference between upper and lower case and the position of the Turkish letters in the alphabet into account. To remove only the upper/lower-case difference, compareToIgnoreCase is enough, but that method does not fix the position of the Turkish letters.
Taking code order for alphabetical order. When the array {"b2", "B10", "ab", "Ab", "a"} is sorted with Arrays.sort, the result is Ab, B10, a, ab, b2: strings that start with a capital letter jump to the front. “a” comes before “ab” because it is a prefix of it. For an order that matches the human alphabet, a Collator or a normalization that first puts the letters into the same case is needed.
10.2.4Words and numbers
For two words with a long common prefix, a comparison can take several characters. Figure 10.3 compares the words “EDUCATIVE” and “EDUCATED”. The first six letters (EDUCAT) are equal. At the seventh letter, 'I' (73) meets 'E' (69); because 'E' is smaller, “EDUCATED” comes first. The length of the words does not affect the result: “EDUCATIVE” has nine letters and “EDUCATED” has eight, but the decision is made at the seventh letter.
When numbers are stored as strings, lexicographic order departs from numeric order. The comparison is again done from left to right, character by character. When “11” is compared with “2”, the first characters are '1' and '2'; because '1' is smaller, “11” comes first. The number of digits is not taken into account at all. Figure 10.4 shows the primes between 2 and 29 in two orders.
For the same reason, the strings “123”, “45”, “6”, “789” are in exactly this order lexicographically: their first characters satisfy 1 < 4 < 6 < 7. If numeric order is wanted, there are two ways. The first is to convert the strings to integers and sort them as numbers. The second is to pad all the numbers on the left with zeros to the same length: then “02” < “11”, because now the first characters are '0' and '1'. This is why file names take the form “image01, image02, …, image10”.
Sort the strings “10”, “9”, “100”, “2” in lexicographic order. The first characters are '1', '9', '1', '2'. “10” and “100”, which start with '1', come first. Of these two, “10” is a prefix of “100” and comes first. Next comes “2”, which starts with '2', and last “9”, which starts with '9'. The result: “10” < “100” < “2” < “9”. The numeric order is 2, 9, 10, 100.
10.2.5Comparison-based string sorting
Now that lexicographic comparison is available, any known sorting algorithm can be applied to strings. The example in the slides uses the simplest method: for each position, the lexicographically smallest of the remaining strings is brought there by swaps.
void lexSort(String[] a) {
int n = a.length;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (a[i].compareTo(a[j]) > 0) {
String tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}The outer loop moves position i from left to right. For each j after i, the inner loop compares a[i] with a[j]. If a[i].compareTo(a[j]) > 0, then a[j] is smaller and the two items are swapped. When the inner loop finishes, position i holds the smallest of the remaining items. The method resembles selection sort; the difference is that it swaps every time it finds a smaller item, not once at the end. Table 10.4 gives the output of the code on two inputs.
| Input | Output |
|---|---|
| eabcdf, abcde, bcdea, cdeab, deabcg | abcde, bcdea, cdeab, deabcg, eabcdf |
| banana, orange, grape, apple, kiwi | apple, banana, grape, kiwi, orange |
The cost has two factors. The two nested loops make N(N − 1)/2 comparisons, which is O(N2). Each compareTo call reads at most W characters, where W is the length of the longest string. The total time is O(N2 · W). Swaps only exchange references; the characters of the strings are not copied. A swap therefore takes constant time, and the extra memory is O(1).
A better comparison sort, such as merge sort, makes O(N log N) comparisons. For strings that means O(W · N log N) time. Java's Arrays.sort(String[]) also uses a variant of merge sort and is stable. Every sort based on comparisons must make at least Ω(N log N) comparisons in the worst case. The reason for this lower bound is the number of yes/no questions needed to distinguish each of the N! possible orders: log2(N!) ≈ N log2 N. Radix sort does not compare characters; it counts them. The lower bound therefore does not apply to it.
A numerical example makes the difference concrete. Take N = 106 strings of W = 10 characters each. Merge sort makes about N log2 N ≈ 2 · 107 comparisons; if each comparison reads at most 10 characters, the upper bound is 2 · 108 character operations. LSD radix sort finishes in W · (N + R) = 10 · (106 + 256) ≈ 107 steps. These figures give only orders of magnitude; constant factors and cache behavior change the real running time.
10.3Radix sort
A comparison sort compares two strings from the beginning every time. For strings with long common prefixes, the same characters are read over and over. Radix sort takes a different route: it handles the string character by character and uses each character as a digit of a number. In each pass, the strings are distributed into buckets by a single character position. The distribution is done by counting, not by comparison.
There are two directions. LSD (least significant digit) starts from the right, that is, from the last character, and moves left. MSD (most significant digit) starts from the left, from the first character, and sorts each bucket separately. Both methods use the same subroutine in each pass: a stable counting sort on a single character position.
10.3.1Counting sort and stability
Counting sort sorts items whose keys are small integers. Here the key is the d-th character of the string, a code between 0 and 255. The method has three steps: count how many times each key occurs, turn the counts into positions with a prefix sum, and place the items at those positions.
A sorting method is stable if it preserves, in the output, the relative order that items with equal keys had in the input. For example, if x and y have equal keys and appear in this order in the input, then x also comes before y in the output.
The LSD code in the slides consists of three methods. lsdSort manages the passes, countingSort performs a stable counting sort on a single character position, and key reads the d-th character of a string safely:
void lsdSort(String[] a) {
int W = maxLen(a); // longest string
for (int d = W - 1; d >= 0; d--)
countingSort(a, d); // right to left
}
void countingSort(String[] a, int d) {
int[] count = new int[256]; // ASCII
for (String s : a) count[key(s, d)]++;
for (int r = 1; r < 256; r++) count[r] += count[r - 1];
String[] aux = new String[a.length];
for (int i = a.length - 1; i >= 0; i--) // stable
aux[--count[key(a[i], d)]] = a[i];
System.arraycopy(aux, 0, a, 0, a.length);
}
int key(String s, int d) { // short string → 0
return d < s.length() ? s.charAt(d) : 0;
}The lines of countingSort do the following, in order.
- Counting. The
countarray has 256 cells; each cell corresponds to one character code. The linefor (String s : a) count[key(s, d)]++;writes intocount[c]the number of strings whosed-th character is c. - Prefix sum. After the loop
count[r] += count[r - 1],count[c]is the total number of strings whose key is less than or equal to c. This number gives the position where bucket c ends in the output array: bucket c starts atcount[c − 1]and ends atcount[c] − 1. - Placement. The array is scanned from back to front. Each string is written into the last free cell of its own bucket:
aux[--count[key(a[i], d)]] = a[i]. The counter is decremented first, and then the item is written at that position. - Copying back.
System.arraycopycopies the sortedauxarray intoa.
Placing items from back to front is what guarantees stability. Of the strings in a bucket, the one that comes last in the input is written to the very end of the bucket. The one before it is written to the previous cell. The order within the bucket thus stays the same as in the input. The key method returns 0 if d exceeds the length of the string. Since 0 is smaller than the code of every letter, a short string goes ahead of the strings that have a character at that position. So “car” comes before “cart”; this corresponds to the rule “a prefix comes first” in lexicographic order.
Given ten strings: cab, dab, bad, dad, fad, ace, bee, bed, add, ebb. All have three characters, so W = 3. The first pass of LSD is countingSort(a, 2), that is, a sort on the last character.
- Counting. The last characters are b, b, d, d, d, e, e, d, d, b in turn.
count['b'] = 3,count['d'] = 5,count['e'] = 2; the other cells are 0. - Prefix sum.
count['b'] = 3,count['c'] = 3,count['d'] = 8,count['e'] = 10. Bucket b occupies positions 0–2, bucket d positions 3–7, and bucket e positions 8–9. - Placement (back to front).
i = 9: ebb, bucket b →count['b']drops to 2,aux[2] = ebb.i = 8: add →aux[7].i = 7: bed →aux[6].i = 6: bee →aux[9].i = 5: ace →aux[8].i = 4: fad →aux[5].i = 3: dad →aux[4].i = 2: bad →aux[3].i = 1: dab →aux[1].i = 0: cab →aux[0]. - Result.
cab, dab, ebb, bad, dad, fad, bed, add, ace, bee. In each bucket the strings keep their input order: cab, dab, ebb in bucket b; bad, dad, fad, bed, add in bucket d.
The cost of a single pass is easy to see. The counting and placement loops take N steps and the prefix-sum loop takes R = 256 steps. A pass uses O(N + R) time and O(N + R) extra memory for the aux and count arrays.
10.3.2LSD: right to left
lsdSort calls countingSort W times, lowering d from W − 1 to 0. It sorts first by the last character, then by the middle character, and finally by the first character. In each pass, strings with equal keys keep the order established by the previous pass. The figures show the three passes of the previous example.
| Pass | Key | Array |
|---|---|---|
| input | — | cab, dab, bad, dad, fad, ace, bee, bed, add, ebb |
1 (d = 2) | 3rd character | cab, dab, ebb, bad, dad, fad, bed, add, ace, bee |
2 (d = 1) | 2nd character | cab, dab, bad, dad, fad, ebb, ace, add, bed, bee |
3 (d = 0) | 1st character | ace, add, bad, bed, bee, cab, dab, dad, ebb, fad |
It is worth looking closely at the result of the second pass. The array is now sorted by the last two characters: first those ending in “ab” (cab, dab), then those ending in “ad” (bad, dad, fad), then “bb”, “ce”, “dd”, “ed”, “ee”. The third pass groups by the first character. Strings with the same first letter, for example bad, bed, and bee, stay in the order left by the second pass. That order is already correct with respect to the last two characters.
If the strings have different lengths, key returns 0 for missing positions, and a short string behaves as if the smallest character had been appended to it. For car, cart, ca, cat, for example, W = 4. In the first pass, on the fourth character, the keys of “car”, “ca”, and “cat” are 0 and that of “cart” is 't'; the array becomes car, ca, cat, cart. In the pass on the third character, the key of “ca” is 0 and it moves to the front: ca, car, cart, cat. The remaining two passes do not change this order. The result is the lexicographic order.
10.3.3Why is LSD correct?
It seems backwards at first that LSD starts from the least significant character. The key to its correctness is an invariant: after every pass, the array is sorted by the last characters processed so far.
Apply LSD to strings of W characters each, and let every pass be stable. After k passes, the array is lexicographically sorted by the suffixes of the strings consisting of their last k characters. When k = W, the array is completely sorted.
The proof is by induction on k. For k = 1, the first pass sorts by the last character, so the claim holds. Assume the claim holds after k − 1 passes. Pass k sorts by the k-th character from the end. Take two strings x and y. If their characters at this position differ, the pass puts them in the correct order by this character; this character also decides the order of the length-k suffixes. If their characters at this position are equal, the order of the length-k suffixes is decided by the remaining k − 1 characters. By the assumption, x and y are in the correct order by those k − 1 characters in the input to this pass. Since the pass is stable, the relative order of x and y, whose keys are equal, does not change. In both cases x and y are in the correct order by their last k characters. □
The proof also shows why stability is indispensable. The last pass does not decide the order of two strings with equal keys; the earlier passes decided it. An unstable subsort ruins that decision. If the placement loop wrote from front to back instead of back to front, for example, every bucket would be filled in reverse. On the ten strings from the slides, this broken version produces add, ace, bed, bee, bad, cab, dab, dad, ebb, fad. The first letters are in the right order, but strings with the same first letter are scrambled.
Using an unstable method such as quicksort or heapsort as the subsort in LSD. Even if each pass sorts correctly by its own key, the order established by earlier passes is destroyed; “bed” and “bee” may swap places in the last pass. In counting sort, the placement must run from back to front.
10.3.4MSD: left to right
MSD radix sort starts from the first character. All strings are first split into buckets by their first characters. Then each bucket is sorted separately and recursively by the next character. The recursion stops at a bucket with a single item or when the end of a string is reached. In the slides' notation the end of a string is marked with the character \0 and is considered smaller than every letter.
The nine words in Figure 10.8 are split by first character into buckets B, C, M, and W. Bucket M holds only MIDNIGHT; a bucket with one item finishes immediately, and a single character suffices for MIDNIGHT. Bucket B holds BADGE and BANNER. Their second characters are the same (A), so the third character is examined: D < N. Three characters are read for these words. Bucket C holds COFFEE, COMPARISON, and COMPUTER. COFFEE separates at the third character (F < M). COMPARISON and COMPUTER separate only at the fifth character (A < U); both need five characters. In bucket W, WORKER separates at the second character (O), and WANDER and WARDROBE at the third (N < R).
The total number of characters read is the number of green cells: 3 + 3 + 3 + 5 + 5 + 1 + 3 + 3 + 2 = 28. The nine words have 63 characters in total. MSD finishes the sort having read fewer than half of the characters. LSD, by contrast, would process every word as many times as the length of the longest word, that is, 10 times. This is the real advantage of MSD: it examines only the distinguishing prefixes.
The slides do not give code for MSD; they leave the recursive version as an exercise. The version below applies the slides' idea directly. msdKey returns 0 if the string has ended and the character code plus one otherwise. Bucket 0 thus means “the string ended here”, and this bucket falls at the very front of the sorted order.
void msdSort(String[] a) {
String[] aux = new String[a.length];
msdSort(a, aux, 0, a.length - 1, 0);
}
int msdKey(String s, int d) { // 0 past the end, else code + 1
return d < s.length() ? s.charAt(d) + 1 : 0;
}
void msdSort(String[] a, String[] aux, int lo, int hi, int d) {
if (lo >= hi) return; // bucket of 0 or 1 items
int[] count = new int[258];
for (int i = lo; i <= hi; i++) count[msdKey(a[i], d) + 1]++;
for (int r = 0; r < 257; r++) count[r + 1] += count[r];
for (int i = lo; i <= hi; i++) aux[count[msdKey(a[i], d)]++] = a[i];
for (int i = lo; i <= hi; i++) a[i] = aux[i - lo];
for (int r = 0; r < 256; r++) /* each bucket on the next char */
msdSort(a, aux, lo + count[r], lo + count[r + 1] - 1, d + 1);
}The code performs LSD's counting step on a subarray (lo–hi). The count array has 258 cells: one bucket for the end of the string, 256 buckets for the 256 characters, and one extra cell for the prefix sum. After the prefix sum, count[r] is the starting position of bucket r within the subarray. The distribution step writes the items into the auxiliary array and copies them back. The last loop sorts each character bucket recursively with d + 1. Bucket 0 (finished strings) is not sorted again; its members are equal to one another. The code puts the nine words from the slides in the order BADGE, BANNER, COFFEE, COMPARISON, COMPUTER, MIDNIGHT, WANDER, WARDROBE, WORKER. It also sorts the input car, cart, ca, cat, a, "" as "", a, ca, car, cart, cat.
MSD has weaknesses too. Every recursive call creates and scans a count array of 258 cells. For small buckets of a few items, this scan is much more expensive than the items themselves. Real implementations therefore switch to insertion sort for small subarrays (say, below 15 items). The second weakness is strings with long common prefixes. If all strings start with the same long prefix, MSD also has to read all of those characters. In a list of URLs, for example, the prefix “https://www.” is shared by every string.
10.3.5Complexity and choosing a method
LSD makes W passes, where W is the length of the longest string. Each pass handles N strings and R buckets. The total time is O(W · (N + R)). If the alphabet is fixed (R = 256) and N is much larger than R, the cost drops to O(W · N): the length of the longest string times the number of items. That is the same order as the total number of characters in the input. Since even reading the input takes this long, nothing better can be expected.
| Method | Time | Extra memory | Stable |
|---|---|---|---|
Exchange-based sort + compareTo | O(N2 · W) | O(1) | no |
Merge sort + compareTo | O(W · N log N) | O(N) | yes |
| LSD radix sort | O(W · (N + R)) | O(N + R) | yes |
| MSD radix sort | O(N · W) worst case | O(N + W · R) | yes |
The W · R term in the extra memory of MSD comes from the recursion. The recursion depth is at most W, and one count array is alive at each level. The time of MSD is O(N · W) in the worst case, but on random strings it is much less, because only the distinguishing prefixes are read. For small buckets when R is large, however, the cost of the counting array dominates.
The choice depends on the structure of the keys. LSD is ideal when the keys are short and of fixed length: license plates, postal codes, IP addresses, three-letter airport codes. For example, N = 106 three-letter codes are sorted by LSD in 3 · (106 + 256) ≈ 3 · 106 steps, whereas merge sort makes about 2 · 107 comparisons. For strings of very different lengths, LSD processes every string as many times as the longest one and does needless work. In that case MSD or a comparison sort is preferred.
Believing that radix sort is faster than comparison sorting in every case. O(W · N) is good when W is small. When W is larger than log N, for example a few hundred strings of a thousand characters each, a comparison sort may do less work. And when R is large (say R = 65,536 for all of Unicode), the O(R) term in each pass dominates the cost on small arrays.
10.4Regular expressions
You may need to find all the dates in a text, check whether a phone number typed into a form has the right format, or pick the error lines out of a log file. Writing a separate loop for each of these jobs is tiring and error-prone. Regular expressions let you describe such patterns with a short string.
10.4.1What is a regular expression?
A regular expression (regex for short) is a string that describes a search pattern. A regular expression describes a set of strings: all strings that “match” the expression are elements of this set.
Regular expressions are used to find parts of a text that match a pattern, to verify that a whole string matches a pattern, to extract parts, or to replace them with other text. Log analysis, form validation, data cleaning, and the lexer in a compiler are foremost among these uses. The lexer is the first compiler stage; it splits source code into pieces such as keywords, variable names, and numbers.
Regular expressions also have a theoretical foundation. Kleene's theorem says that every regular expression has an equivalent finite state machine and that the converse also holds. The sets of strings that can be described by regular expressions are called regular languages. This link explains how regular expressions are run quickly: the expression is first converted into an automaton, and then the text is scanned with that automaton.
| Pattern | Text | Matches |
|---|---|---|
colou?r | color colour | color, colour |
gr(a|e)y | gray grey groy | gray, grey |
\d+ | 20.99 TL, 5 items | 20, 99, 5 |
\bkod\b | kod kodlama | only “kod” |
In the first row, u? says the letter u may or may not be present; American and British spellings are caught together. In the second row, (a|e) requires one of two alternatives; “groy” does not match. In the third row, \d+ finds every part made of one or more digits. Since the period is not a digit, “20.99” is split into two separate parts. In the fourth row, \b is a word boundary; the “kod” inside “kodlama” is not taken because it is not a whole word.
In Java, regular expressions are used through the Pattern and Matcher classes of the java.util.regex package. The matches, replaceAll, and split methods of the String class also take regular expressions. Because the backslash is an escape character in a Java string, every backslash in a regular expression is written twice: the expression \d+ appears in code as "\\d+".
10.4.2Basic operators
Ordinary characters in a regular expression match themselves: abc matches only the substring “abc”. Some characters, however, have special meanings. Table 10.8 gives the most commonly used operators with an example of each. The last two columns of the table show whether the given string contains a part that matches the pattern; this is the behavior of Matcher.find in Java.
| Op. | Meaning | Example | Found in | Not found in |
|---|---|---|---|---|
. | any single character (except newline) | a.c | abc, a7c | ac |
* | 0 or more repetitions of the previous item | ab*c | ac, abbc | adc |
+ | 1 or more repetitions of the previous item | ab+c | abc, abbc | ac |
? | the previous item occurs 0 or 1 times | ab?c | ac, abc | abbc |
[ ] | one of the characters in the set | [ck]ar | car, kar | bar |
^ | start of the string | ^ab | abc | cab |
$ | end of the string | ab$ | cab | abc |
( ) | grouping; defines a subexpression | ^(ab)+$ | ab, abab | aba |
*, +, and ? apply only to the item immediately before them. This item can be a single character, a set, or a group built with parentheses. In the expression ab*c, the star belongs only to b: an a, then zero or more b's, then a c. So “ac” (zero b's) and “abbc” match, while “adc” does not. If a whole part is to be repeated, the part is grouped: (ab)+ matches “ab”, “abab”, “ababab”, and so on.
^ and $ specify a position, not a character. ^ab matches only an “ab” at the very beginning of the string; the “ab” inside “cab” is not taken because it is not at the start. ^(ab)+$ accepts strings made up entirely of repetitions of “ab” from start to end. “aba” has an extra a at the end and does not match.
Assuming that ab?c will find a match in “abbc”. ? allows only one b. In “abbc” there are two b's between the a and the c, and there is no part in which a c follows an a directly. So find finds no match.
10.4.3Special characters and escaping
Besides the basic operators, there are a few commonly used shorthands. These shorthands begin with a backslash and define a character class or a position.
| Expression | Meaning |
|---|---|
a | a single 'a' character |
abc | exactly “abc” |
{ } | a specific number of repetitions: \d{4} is four digits |
| | alternatives: kedi|köpek |
\b | word boundary (start or end of a word) |
\d | a digit: [0-9] |
\w | a word character: [a-zA-Z0-9_] |
\s | a whitespace character: space, tab, newline |
The upper-case forms of the shorthands are complements. \D matches a non-digit, \W a non-word character, and \S a non-whitespace character. \w is a single character; to match a whole word, write \w+.
If you are searching for a character that itself has a special meaning, a backslash is put in front of it. This is called escaping. \. matches a real period, \+ a plus sign, and \( an opening parenthesis. If the escape is forgotten, the expression catches more than expected: a.b also matches “a+b”, because the dot means any character.
One detail in Java matters for Turkish text. By default \w covers only ASCII letters. When \w+ is applied to the word “şeker”, the first match is “eker”; 'ş' is not counted as a word character. For a letter class that also covers Turkish letters, the Unicode property \p{L} is used: \p{L}+ matches all of “şeker”. Another way is to compile the pattern with the Pattern.UNICODE_CHARACTER_CLASS flag, which extends \w to Unicode as well.
10.4.4Character classes
Characters written inside square brackets form a character class. The class matches any one of the characters inside it. A hyphen (-) declares a range: [a-z] matches every lowercase letter whose code lies between a and z.
| Class | Characters matched |
|---|---|
[abc] | 'a', 'b', or 'c' |
[a-z] | any lowercase letter (ASCII) |
[A-Z] | any uppercase letter (ASCII) |
[0-9] | any digit |
[a-zA-Z_] | a letter or underscore |
[^abc] | any character other than 'a', 'b', 'c' |
[^0-9] | a non-digit character |
[^0-9]+ | “ab” and “cd” in “ab12cd” |
The ^ sign has two different meanings. Inside square brackets, at the start, it means “not”; outside, it marks the start of the string. Inside a set, ., *, and + are not special: [.+] matches a period or a plus. Because a hyphen declares a range, it is written at the start or end of the set when it is itself being searched for: [-+].
Assuming that the class [a-z] also covers Turkish lowercase letters. The range is based on character codes; ç, ğ, ı, ö, ş, ü lie outside it. When [a-z]+ is applied to the word “çiçek”, only the parts “i” and “ek” are found. For Turkish letters, either add them to the set explicitly ([a-zçğıöşü]) or use \p{L}.
10.4.5Quantifiers and grouping
Operators that state how many times an item is repeated are called quantifiers. *, +, and ? are the shortest quantifiers. Curly braces allow finer control.
| Expression | Meaning |
|---|---|
a* | zero or more 'a' |
a+ | one or more 'a' |
a? | zero or one 'a' |
a{3} | exactly three 'a' |
a{2,4} | between two and four 'a' |
a{2,} | at least two 'a' |
(abc) | exactly “abc”; captured as a group |
(a|b|c) | 'a', 'b', or 'c'; captured as a group |
(ab)+ | “ab”, “abab”, … |
Parentheses have two jobs. The first is to let a quantifier apply to a whole part. The second is to capture the matched part: after a match is found, the text that fell inside the parentheses can be read separately. Groups are numbered from left to right, in the order of their opening parentheses. In Java, group 1 is read with m.group(1), and the whole match with m.group() or m.group(0).
Quantifiers are greedy by default: they take as long a part as possible. In “aaaaa”, a{2,4} takes the longest possible part, “aaaa”. If a ? is written after the quantifier, the quantifier becomes lazy and picks as short a part as possible. The difference is best seen with HTML tags.
Let the text be <b>x</b>. The greedy <.+> starts at the first <; .+ takes everything up to the end of the line. Then it backs off to find a > and stops at the last >. The first match is the whole text: <b>x</b>. The lazy <.+?>, on the other hand, first takes a single character (b) with .+? and then checks whether a > follows. It does; the first match is <b>. If find continues the search, the second match is </b>. In both patterns the match starts at the leftmost suitable position (0). Laziness affects only the length of a match, not its start.
10.4.6Lookahead and lookbehind
Sometimes we look for a part that occurs only in a particular context, but the context itself must not be part of the match. For example, we may want the numbers that come before “TL”, but “TL” must not appear in the result. Lookaround expressions do this job.
| Pattern | Name | Match condition | “ab ac ba” |
|---|---|---|---|
a(?=b) | lookahead | 'a' if followed by 'b' | 0 |
a(?!b) | negative lookahead | 'a' if not followed by 'b' | 3, 7 |
(?<=b)a | lookbehind | 'a' if preceded by 'b' | 7 |
(?<!b)a | negative lookbehind | 'a' if not preceded by 'b' | 0, 3 |
The text “ab ac ba” has three a's, at positions 0, 3, and 7. The a at 0 is followed by b; the lookahead selects this a. The a at 3 is followed by c and the a at 7 by the end of the text; the negative lookahead selects these two. The a at 7 is preceded by b; the lookbehind selects only that one. The other two a's are preceded by a space or by the start of the text.
Lookaround expressions test a position and consume no characters. The text of a match of a(?=b) is just “a”; the b does not take part in the match and can be used again in the next search. So in the text “abacab”, a(?=b) matches twice, at positions 0 and 4, each time as “a”.
The most common use of lookaround is to test several conditions at once. The expression ^(?=.*\d)(?=.*[A-Z]).{8,}$ checks a password rule. The first lookahead tests that there is a digit somewhere in the string; the second, that there is an uppercase letter. Because neither consumes characters, the position is still at the start of the string. The last part, .{8,}$, demands that the string have at least 8 characters. “Parola12” satisfies all three conditions. “parola12” has no uppercase letter and “PAROLAXY” has no digit; “Pa1” is too short.
10.4.7Validation expressions
Regular expressions are written most often to check the format of data coming from users. Table 10.13 gives three examples. All begin with ^ and end with $; the whole string, not just a part of it, is required to fit the format.
| Purpose | Regular expression | Matches | Does not match |
|---|---|---|---|
^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$ | ali.veli@giresun.edu.tr | ali@tr; a b@x.com | |
| Phone | ^(\+\d{1,3}[- ]?)?\d{10}$ | +90 5321234567; 5321234567 | 0532 123 45 67 |
| URL | ^https?:\/\/[^\s/$.?#].[^\s]*$ | https://giresun.edu.tr | ftp://x.com; http:// x |
The email expression has three parts. [a-zA-Z0-9._%+-]+ is the user name: a part of at least one character made of letters, digits, and a few symbols. Then comes the @. [a-zA-Z0-9.-]+ is the domain name. \.[a-zA-Z]{2,} is a real period and an extension of at least two letters. “ali@tr” does not match because there is no period and extension after the @. “a b@x.com” does not match because the space is not in the user-name set.
In the phone expression, (\+\d{1,3}[- ]?)? is the optional country code. The group consists of a plus, one to three digits, and an optional hyphen or space; the ? at the end makes the whole group optional. Exactly 10 digits must then follow. “0532 123 45 67” does not match: it has 11 digits and also has spaces inserted.
In the URL expression, s? accepts both “http” and “https”. Then comes :\/\/. In Java the slash is not special and needs no escaping; this spelling, which comes from other languages, is harmless all the same. [^\s/$.?#] says that the first character cannot be a space or one of these symbols. The last part is any sequence of characters containing no whitespace. “ftp://x.com” does not match because the scheme is neither http nor https. “http:// x” does not match because the first character after // is a space.
These expressions are practical approximations; they do not cover the full standards. The complete syntax of email addresses is defined in RFC 5322 and the URI syntax in RFC 3986, and both are much broader. In real applications the regular expression does a first filter; the real validation, such as sending a confirmation message to the address, is done by other means.
10.4.8Grammars and parse trees
Another way to describe the structure of a string is to write a grammar. A grammar uses rules to say what smaller parts a larger structure consists of. As an example, consider addresses of the form http://didit.csail.mit.edu:4949/:
url ::= 'http://' host
':' port '/'
host ::= word '.' host
| word
word ::= [a-z]+
port ::= [0-9]+The first rule says that a url consists of “http://”, a host, a colon, a port, and a slash. The second rule is recursive: a host is either of the form “word . host” or a single word. The last two rules define the word and the port with character classes. Applying the grammar to a string produces a parse tree.
http://didit.csail.mit.edu:4949/. The root is url; the host rule is expanded recursively three times and produces the words didit, csail, mit, edu.Although the grammar looks recursive, the recursion is at the very end of the rule; it is tail recursion. Such a recursion can be turned into a loop. The same language can therefore also be described by a regular expression: http://([a-z]+\.)*[a-z]+:[0-9]+/. This expression does indeed match the example address.
This is not possible for every structure. Balanced parentheses, that is, strings such as “(())()” in which everything opened is closed, cannot be described by a regular expression. The only memory of a finite state machine is its current state, and it cannot count parentheses nested to unbounded depth. Nested structures need a context-free grammar and a parser that processes it. Compilers for programming languages use this pair: the lexer works with regular expressions, the parser with a context-free grammar.
Trying to parse nested structures such as HTML or JSON with regular expressions alone. Because <.*> is greedy, it swallows the whole line “<b>x</b> <i>y</i>” as a single match. The lazy version finds the tags one by one, but it cannot tell which of the nested tags closes which. A parser is used for this job.
10.4.9Pattern and Matcher in Java
In Java, a regular expression is first compiled with Pattern.compile. Compilation turns the expression into an automaton-like structure internally; if the same expression will be applied to many texts, the compiled object is stored and reused. From the compiled pattern, the matcher method yields a Matcher for a specific text.
String input = "Name: Ali Veli, Age: 30, Email: ali.veli@example.com";
Pattern p = Pattern.compile("Age: (\\d+),"); // compile
Matcher m = p.matcher(input);
if (m.find()) { // find first match
int age = Integer.parseInt(m.group(1)); // group 1: "30"
System.out.println("Age: " + age);
}The code extracts the age from a one-line record. The pattern "Age: (\\d+)," looks for the text “Age: ”, then one or more digits, then a comma. Because the digits are in parentheses, they are captured as group 1. m.find() looks for the first match in the text and returns true if it finds one. m.group(1) gives the string “30”; Integer.parseInt converts it to a number. The code prints Age: 30.
| Pattern | group(1) | Explanation |
|---|---|---|
| Name: (.*?), | Ali Veli | lazy .*?: stops at the first comma |
Age: (\d+), | 30 | one or more digits |
Email: (.*?)$ | ali.veli@example.com | up to the end of the line |
The laziness in the first row matters. If the greedy Name: (.*), were written, .* would stretch to the last comma and the group would be “Ali Veli, Age: 30”. In the third row, although .*? is lazy, $ forces it to go to the end of the line.
The two basic methods of Matcher answer different questions. find() searches for a part of the text; each call moves on to the next match. matches(), on the other hand, tries to match the whole text; it behaves as if ^ had been put at the start of the expression and $ at the end. String.matches is of this second kind. For example, "abc123".matches("\\d+") returns false because the string does not start with a digit. With the same pattern, find() finds the part “123” and returns true. Similarly, "2024".matches("\\d{4}") is true and "20245".matches("\\d{4}") is false: the fifth digit is extra.
The same job can also be done without a regular expression. The start marker (e.g., “Age: ”) is found with indexOf, and the part up to the end marker (“,”) is cut out with substring. For a simple extraction, this route can be faster and more readable. As the pattern becomes more complicated, for example as optional parts and alternatives multiply, the regular expression stays shorter and more reliable.
Using nested quantifiers carelessly. When Java's regular expression engine fails to find a match, it goes back (backtracking) and tries other options. In an expression such as (a+)+$, there is an exponential number of ways to split the text “aaaa…ab”. Backtracking engines may try all of these ways in the worst case, and the program appears to hang. This is called catastrophic backtracking. Avoiding nested + and *, and not forgetting the escape character, is enough in most cases.
10.5Finite state machines
Imagine a turnstile. When it is locked, dropping in a token unlocks it; when it is unlocked, someone passing through locks it again. How many tokens the turnstile has swallowed in the past does not matter; its behavior is determined only by its current state, locked or unlocked. A finite state machine is the mathematical form of this idea and the simplest model for processing strings character by character.
10.5.1Formal definition
A finite state machine (FSM) is defined by five elements: M = (Q, Σ, δ, q0, F). Q is a finite set of states. Σ is the input alphabet. δ is the transition function: δ(q, c) gives the state the machine goes to when it reads the symbol c while in state q. q0 ∈ Q is the start state. F ⊆ Q is the set of accepting states. The machine processes a string by reading it one symbol at a time from left to right; when the string ends, it accepts the string if it is in a state in F and rejects it otherwise.
The machine's only memory is its current state. Because the number of states is finite, the machine can keep only a bounded summary of the input it has read. At first glance this restriction looks like a weakness. Even so, many real problems, such as lexical analysis, network protocols, and pattern search, are solved with this much memory. And because the machine does a single operation per character, it is very fast.
In a state diagram, each state is a circle and each transition a labeled arrow. An arrow comes in from outside to the start state; accepting states are drawn with a double ring. In the machine of Figure 10.10, δ(q0, 0) = q0, δ(q0, 1) = q1, δ(q1, 1) = q1, and δ(q1, 0) = q0. The meaning of the states is clear: q1 says “the last symbol read was 1”, and q0 says “the last symbol read was 0, or nothing has been read yet”.
Run the machine on the input “0101”. The start is q0. Read 0: stay in q0. Read 1: move to q1. Read 0: return to q0. Read 1: move to q1. The input is finished and q1 ∈ F, so the string is accepted. The string “0110”, on the other hand, ends in q0 after its final 0 and is rejected.
10.5.2DFA, NFA, and ε-NFA
There are three common kinds of finite state machines. They differ in how many targets the transition function can give for a (state, symbol) pair.
- Deterministic finite automaton (DFA): for every (state, symbol) pair there is exactly one transition. The machine is in a single state at any moment. It is simple to run, and an input of length n is processed in O(n) time.
- Nondeterministic finite automaton (NFA): for a (state, symbol) pair, zero, one, or several transitions may be defined. The machine is in a set of states at the same time. If the set contains an accepting state when the input ends, the string is accepted.
- ε-NFA: an NFA that also allows empty transitions (epsilon, ε) made without reading a symbol. It can be built directly from a regular expression, piece by piece. This construction is called Thompson's construction.
DFAs, NFAs, ε-NFAs, and regular expressions recognize the same class of languages, namely the regular languages. Every NFA can be converted by the subset construction into a DFA that recognizes the same language; the number of states of the DFA obtained from an NFA with n states is 2n in the worst case.
The idea of the subset construction also supplies the proof. An NFA is in a set of states at any moment. Let each state of the DFA correspond to a set of states of the NFA. The start state of the DFA is {q0}. When the DFA is in a set S and reads c, it moves to the union of the states that each state in S can reach on c. This transition is unique for every (set, symbol) pair, so the resulting machine is a DFA. The state of the DFA is the exact set of states the NFA could be in after each prefix of the input. The DFA therefore accepts the strings the NFA accepts, and only those. Since a set with n elements has 2n subsets, the number of states cannot exceed this bound. □
The exponential growth can indeed occur. The NFA that recognizes the strings over {a, b} whose third symbol from the end is a has four states. The start state stays in itself on every symbol, or moves to the state “a seen” when it reads an a. Two more symbols are then read and the accepting state is reached. A DFA recognizing this language, however, has to remember all of the last three symbols and needs 23 = 8 states. For “the k-th symbol from the end”, the NFA has k + 1 states and the DFA 2k. In practice this blow-up is rarely seen. grep, lex/flex, and the lexers of compilers use the chain in Figure 10.11: they convert the regular expression to an NFA and, if needed, to a DFA, and scan the text with that automaton.
10.5.3Simulating a DFA
Running a DFA takes three steps. Move to the start state. For each character, update the state from the transition table. When the string ends, check whether the final state is an accepting state. The transition function is stored in a table: rows are states and columns are symbols. States are numbered from 0, and 0 is the start state.
boolean accepts(int[][] next, boolean[] accept,
String s) {
int state = 0; // start state
for (char c : s.toCharArray())
state = next[state][c - '0']; // one transition
return accept[state]; // final state accepting?
}The next table has size int[|Q|][|Σ|]. In this example the alphabet is {0, 1}; the expression c - '0' turns the character '0' into 0 and '1' into 1 and is used as the column index. The accept array records whether each state is an accepting state. The loop does a single table read per character. A string of length n is processed in O(n) time without backing up; the only extra memory is the state variable. The table itself takes O(|Q| · |Σ|) space.
Never backing up is an important property. Some regular expression engines backtrack, as in the (a+)+$ example, and can spend exponential time in bad cases. A DFA reads each character exactly once; it runs in linear time even in the worst case.
10.5.4Example: a recognizer for “nice”
A machine that recognizes one specific word is the simplest example of a finite state machine. The machine in Figure 10.12 accepts only the string “nice”.
Each state represents the prefix read so far: 1 the empty prefix (ε), 2 “n”, 3 “ni”, 4 “nic”, and 7 “nice”. If the expected character arrives, the machine moves to the next state. If it does not, for example if a character other than i is read in state 2, the machine goes to the Error state. There is no exit from the Error state; every character keeps the machine there. Such a state is called a trap state. In the diagram the trap state's self-loops are not drawn, but they are assumed to exist so that the machine is a DFA. Likewise, if one more character arrives after the Success state, the machine moves to Error; “nicer” is rejected.
The input “nice” follows the path 1 → 2 → 3 → 4 → 7 and is accepted. The input “nine” follows 1 → 2 → 3 and then reads 'n' as its third character. The expected character is 'c'; the machine goes to 6 and the fourth character keeps it there. The result is rejection.
10.5.5Example: a DFA over the binary alphabet
A larger DFA has six states: A, B, C, D, E, and F. The start state is A and the only accepting state is D. The transitions are given in Table 10.15 and Figure 10.13. Each cell of the table holds a single state, so the machine is a DFA.
| δ | 0 | 1 |
|---|---|---|
| → A | E | B |
| B | B | C |
| C | B | D |
| D * | D | A |
| E | E | F |
| F | F | A |
Let the input be “10011”.
- Start: A.
- Symbol 1 is 1: δ(A, 1) = B.
- Symbol 2 is 0: δ(B, 0) = B.
- Symbol 3 is 0: δ(B, 0) = B.
- Symbol 4 is 1: δ(B, 1) = C.
- Symbol 5 is 1: δ(C, 1) = D. The input is finished; D is an accepting state and the string is accepted.
The accept decision depends only on the final state. The input “1011010” reaches D after the path A → B → B → C → D, but the input is not finished. The next 0 keeps the machine in D, the 1 takes it to A, and the final 0 takes it to E. Since E is not an accepting state, the string is rejected. Having passed through an accepting state along the way changes nothing. Similarly, “111” is accepted via A → B → C → D, while “11” ends in C and is rejected.
The table is easy to give to the accepts method: number the states A–F as 0–5, so the table becomes {{4, 1}, {1, 2}, {1, 3}, {3, 0}, {4, 5}, {5, 0}}, and in the accept array only cell 3 is true. The method returns true for “10011” and false for “1011010”.
10.5.6The pattern-matching automaton
Finite state machines are also used to search for a pattern inside a text. Let the pattern be “ACACAGA”. While the text is read from left to right, the state of the machine shows which prefix of the pattern the end of the text read so far agrees with.
For a pattern P of length m, the states of the pattern-matching automaton are 0, 1, …, m. After the first i characters of the text have been read, the state q is the length of the longest prefix of P that is a suffix of the text read. Reaching state q = m means that the pattern ends at that point in the text.
The forward transitions are easy: in state q, if the q-th character of the pattern (counting from 0) is read, the machine moves to q + 1. The interesting part is the backward transitions. For example, in state 5 (the last five characters read are “ACACA”), let C be read. The expected character is G; the match is broken. But the end of the text read is now “ACACAC”, and its suffix “ACAC” is a prefix of the pattern of length 4. The machine returns not to 0 but to 4; part of the match is preserved. All the nonzero backward transitions in the automaton are: from states 1, 3, 5, and 7 on A to 1; from 5 on C to 4; from 7 on C to 2.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| text | G | A | C | A | C | A | C | A | G | A |
| state | 0 | 1 | 2 | 3 | 4 | 5 | 4 | 5 | 6 | 7 |
This idea is the automaton form of the prefix function in the Knuth–Morris–Pratt (KMP) algorithm. On a mismatch, KMP reads from the prefix function how far to shift the pattern. The automaton instead precomputes this information for every (state, character) pair and writes it into a table. Building the table takes O(m · |Σ|) and the search takes O(n). The slides do not show how the automaton is built; the method below does this construction:
int[][] buildDfa(String p) { // pattern DFA, O(m · 256)
int m = p.length();
int[][] dfa = new int[m + 1][256];
dfa[0][p.charAt(0)] = 1;
for (int x = 0, j = 1; j <= m; j++) {
for (int c = 0; c < 256; c++)
dfa[j][c] = dfa[x][c]; // mismatch: as in state x
if (j < m) {
dfa[j][p.charAt(j)] = j + 1; // match: advance
x = dfa[x][p.charAt(j)]; // restart state
}
}
return dfa;
}The key to the method is the variable x: it is the state reached when the part p[1..j−1] of the pattern is fed to the automaton. When there is a mismatch in state j, the machine knows that “what was read last is the j-character prefix of the pattern, followed by the new character”. The longest matching prefix is the state reached from the state obtained by dropping the first character of this text, that is, from x, on the new character. So row j is first copied from row x. Then the match transition is written over it as j + 1, and x is advanced by one step. For “ACACAGA” the method produces exactly the transitions in Figure 10.15.
10.5.7Code trace: dfaSearch
Once the automaton is built, the search is a few lines:
int dfaSearch(int[][] dfa, String t, int m) {
int q = 0; // state
for (int i = 0; i < t.length(); i++) {
q = dfa[q][t.charAt(i)];
if (q == m)
return i - m + 1; // match
}
return -1;
}The rows of the dfa table are states and its columns are character codes; dfa[q][t.charAt(i)] gives the next state directly. When q == m, the last character of the pattern is at position i of the text. The pattern starts at position i − m + 1, and this value is returned. If the loop ends without finding a match, -1 is returned. Let us trace the code with the call dfaSearch(dfa, "GACACACAGA", 7).
q = 0.i | t[i] | q | Explanation |
|---|---|---|---|
| 0 | G | 0 → 0 | G does not continue any prefix of the pattern |
| 1 | A | 0 → 1 | next character of the pattern |
| 2 | C | 1 → 2 | next character of the pattern |
| 3 | A | 2 → 3 | next character of the pattern |
| 4 | C | 3 → 4 | next character of the pattern |
| 5 | A | 4 → 5 | next character of the pattern |
| 6 | C | 5 → 4 | not the expected G; the end of “ACACAC”, “ACAC”, is a prefix |
| 7 | A | 4 → 5 | next character of the pattern |
| 8 | G | 5 → 6 | next character of the pattern |
| 9 | A | 6 → 7 | q == m: return 9 − 7 + 1 = 3 |
t[6] = 'C': the expected character is not G, but q is not reset; the transition 5 → 4 is made. There is no going back in the text.t[9] = 'A', 6 → 7 = m: the pattern is found and 9 − 7 + 1 = 3 is returned.The pattern starts at position 3 of the text: t[3..9] = “ACACAGA”. The remarkable step is i = 6. A naive search method would shift the pattern by one here and go back in the text to compare again. The automaton instead moves to state 4 and never reads any character of the text a second time. A total of ten characters is processed with ten table reads.
Always returning to state 0 on a mismatch. Let the automaton that searches for the pattern “abab” read the text “abaa”. The first three characters bring it to state 3. The fourth character a is not the expected b. But the longest suffix of “abaa” that is a prefix of “abab” is “a”; the correct state is 1. A machine that returned to 0 would miss the match starting at 3 in a text such as “abaabab”.
10.5.8Parsing numbers with an FSM
Finite state machines are also used to extract parts from a text. The method below finds and prints the decimal numbers in a text. The machine has three states: START (we are not inside a number), DIGIT (the integer part is being read), and DECIMAL (a dot has been seen and the fractional part is being read). The characters of the number being read are accumulated in a StringBuilder buffer.
void findNumbers(String s) {
State st = State.START;
StringBuilder buf = new StringBuilder();
for (char c : s.toCharArray()) {
boolean digit = Character.isDigit(c);
if (digit) {
if (st == State.START) st = State.DIGIT;
buf.append(c);
} else if (c == '.' && st != State.DECIMAL) {
st = State.DECIMAL;
buf.append(c);
} else if (st != State.START) { // number ended
System.out.println(buf);
buf.setLength(0);
st = State.START;
}
}
if (st != State.START) System.out.println(buf);
}For each character, the loop applies one of three conditions. If the character is a digit and the machine is in START, it moves to DIGIT; in every case the digit is added to the buffer. If the character is a dot and the machine is not yet in DECIMAL, it moves to DECIMAL and the dot is also added to the buffer. If neither condition holds and the machine is inside a number (anything other than START), the number has ended: the buffer is printed, emptied, and the machine returns to START. After the loop, if the machine is still inside a number, that is, the input ends with a number, the last number is printed too.
| Character | Branch taken | State | Buffer | Output |
|---|---|---|---|---|
| $ | none (START) | START | “” | |
| 2 | digit | DIGIT | “2” | |
| 0 | digit | DIGIT | “20” | |
| . | dot | DECIMAL | “20.” | |
| 9 | digit | DECIMAL | “20.9” | |
| 9 | digit | DECIMAL | “20.99” | |
| ␣ | number ended | START | “” | 20.99 |
| o, r, ␣ | none (START) | START | “” | |
| 5 | digit | DIGIT | “5” | |
| . | dot | DECIMAL | “5.” | |
| (end) | if after the loop | — | “5.” | 5. |
The method prints two lines: “20.99” and “5.”. The second is a flaw: the period at the end of the sentence has been taken for part of the number. The cause of the flaw is that the machine enters the DECIMAL state without knowing whether a digit will follow the dot. The same design gives unexpected results on other inputs too. In the input “v1.2.3 and 7”, when the second dot arrives the machine is already in DECIMAL. The dot condition does not hold and the third branch runs: “1.2” is printed, the dot is discarded, and the machine returns to START. Then “3” and “7” are printed as separate numbers. The version number has been split into two numbers.
The flaw can be fixed in two ways. The first is to delete the last character if the buffer ends with a dot before printing. The second is to include the dot in the number only if a digit follows it; for that, a new state is added to the machine meaning “dot seen but no fractional digit yet”. The version below follows the first way and accepts the dot only after a digit:
void findNumbersFixed(String s) {
State st = State.START;
StringBuilder buf = new StringBuilder();
for (char c : (s + " ").toCharArray()) { // append a separator
if (Character.isDigit(c)) {
if (st == State.START) st = State.DIGIT;
buf.append(c);
} else if (c == '.' && st == State.DIGIT) { // dot only after a digit
st = State.DECIMAL;
buf.append(c);
} else if (st != State.START) {
if (buf.charAt(buf.length() - 1) == '.')
buf.setLength(buf.length() - 1); // trailing dot is not part of the number
System.out.println(buf);
buf.setLength(0);
st = State.START;
}
}
}Appending a space to the end of the input makes the separate if after the loop unnecessary: the last number also ends with the space and is printed in the same branch. The corrected method prints “20.99” and “5” for “$20.99 or 5.”. For “v1.2.3 and 7” the behavior does not change: “1.2”, “3”, and “7”. Accepting the dot only after a digit has a side effect: a number written without its leading zero, such as “.5”, is read as “5”. Which behavior is right depends on the rules of the application. That is the real benefit of FSM design: every rule corresponds to a state or a transition and is plainly visible.
10.6Edit distance
Someone types “algortima” into a search box and the search engine suggests “algoritma”. For this, a number that measures how close two words are to each other is needed. An equality check says only “same” or “different”; it does not distinguish “one letter missing” from “a completely different word”. The edit distance makes this distinction.
10.6.1The Levenshtein distance
The Levenshtein distance between two strings is the minimum number of single-character edits needed to transform the first string into the second. Three edits are allowed, and each counts as 1: insertion, deletion, and substitution.
The measure takes its name from the Soviet mathematician Vladimir Levenshtein, who defined the concept in 1965; the English translation of his paper appeared in 1966. Its general name is edit distance. This name also covers the variants in which the edits are given different costs. The areas of use are wide: spell checking and autocorrection, predictive typing on keyboards, comparison of DNA sequences, and fuzzy search, which tolerates small spelling differences.
An example can be given for each of the three edits. “sittin” → “sitting”: a g is inserted at the end. “shine” → “shin”: the final e is deleted. “kitten” → “sitten”: k is substituted by s. Using these three operations one after another, “kitten” is transformed into “sitting” in three steps: kitten → sitten (k → s) → sittin (e → i) → sitting (+g).
There is no transformation shorter than three. To see this, there is no need to try every possibility; the dynamic programming table proves it. Still, a short argument can be given. “sitting” is one letter longer than “kitten”, so at least one insertion is needed. The first letters (k and s) differ and cannot be fixed by aligning them with other letters; one more substitution is needed. The e/i difference in the middle requires a third operation.
The Levenshtein distance is a metric in the mathematical sense. It has three properties. The distance of a string to itself is zero: d(a, a) = 0, and the distance is positive for different strings. The distance is symmetric: d(a, b) = d(b, a), because every insertion becomes a deletion when reversed, and every substitution becomes a substitution again. The triangle inequality holds: d(a, c) ≤ d(a, b) + d(b, c); applying the edits from a to b and then those from b to c one after the other gets from a to c.
10.6.2Edit examples
The easiest way to see a transformation is to align the two strings one under the other. Equal letters are written in the same column. A gap is placed opposite a letter that is in one string but not in the other. In Figure 10.23, the letters H, N, D, A of HONDA are aligned with their counterparts in HYUNDAI. O is substituted by Y; there is a gap opposite U and I, so these two letters are inserted. A total of three edits is made.
(a) and (b) are inverses of each other. From “rain” to “shine” takes two substitutions and one insertion; going back from “shine” to “rain” makes the same two substitutions in reverse and the insertion becomes a deletion. Both directions take 3 edits; this is a concrete example of symmetry. In (c), “shine” and “train” have the same length, but the distance is 4: t is inserted, s → r and h → a are substituted, and the final e is deleted.
10.6.3The dynamic programming recurrence
It is impossible to try all edit sequences; their number grows exponentially with the string length. The solution is to split the problem into small subproblems on prefixes. Let string a have m characters and string b have n characters.
D[i][j] is the minimum cost of transforming the first i characters of a into the first j characters of b (0 ≤ i ≤ m, 0 ≤ j ≤ n). The distance sought is D[m][n].
D[i][0] = i and D[0][j] = j
if ai = bj then D[i][j] = D[i−1][j−1]
otherwise D[i][j] = 1 + min( D[i−1][j], D[i][j−1], D[i−1][j−1] )
Here ai is the i-th character of a (counting from 1). The three terms of the minimum correspond to deletion, insertion, and substitution, in that order.
The boundary values are clear: from a prefix of i characters to the empty string takes i deletions, and from the empty string to a prefix of j characters takes j insertions. In the general case we look at what the best transformation does with the last characters. There are three possibilities. (1) ai is deleted; the remaining work is to turn the first i − 1 characters of a into the first j characters of b: cost 1 + D[i−1][j]. (2) bj is inserted at the end; the remaining work is to turn the first i characters into the first j − 1 characters: 1 + D[i][j−1]. (3) ai is aligned opposite bj. If the characters are equal, this step is free and the cost is D[i−1][j−1]. If they differ, a substitution is needed: 1 + D[i−1][j−1]. The best transformation uses one of these three options, so the value is the smallest of the options. It can also be shown that when the characters are equal, the free diagonal is always the best: since neighboring cells of D differ by at most 1, the other two options cannot give a value smaller than D[i−1][j−1]. □
This is a typical example of the dynamic programming (DP) method. Each subproblem is solved once and stored in a table of size (m + 1) × (n + 1); the answer is in the bottom-right corner of the table. Because a cell depends only on its upper, left, and upper-left neighbors, the table can be filled row by row, left to right within each row. A constant amount of work is done per cell. The time is O(m · n) and the memory is O(m · n). If only the distance is needed, the memory can be reduced to two rows, that is, O(min(m, n)).
10.6.4The DP table: CARS → PAIRS
Write a = CARS along the rows and b = PAIRS along the columns. Row 0 and column 0 of the table correspond to the empty prefix (ε).
- Initialization. The first row is 0, 1, 2, 3, 4, 5: the number of insertions from the empty string to the prefixes P, PA, …. The first column is 0, 1, 2, 3, 4: the number of deletions from the prefixes C, CA, … to the empty string.
- Row 1 (C). C equals none of the letters of PAIRS. D[1][1] = 1 + min(0, 1, 1) = 1: C is substituted by P. The rest of the row grows by one at each step: 1, 2, 3, 4, 5.
- Row 2 (A). D[2][1] = 1 + min(1, 2, 1) = 2. Since A = A, D[2][2] = D[1][1] = 1; no cost is added. A ≠ I: D[2][3] = 1 + min(above 3, left 1, upper left 2) = 2. The row becomes 2, 1, 2, 3, 4.
- Row 3 (R). Since R = R, D[3][4] = D[2][3] = 2. The row becomes 3, 2, 2, 2, 3.
- Row 4 (S). Since S = S, D[4][5] = D[3][4] = 2. The row becomes 4, 3, 3, 3, 2.
| ε | P | A | I | R | S | |
|---|---|---|---|---|---|---|
| ε | 0 | 1 | 2 | 3 | 4 | 5 |
| C | 1 | 1 | 2 | 3 | 4 | 5 |
| A | 2 | 2 | 1 | 2 | 3 | 4 |
| R | 3 | 3 | 2 | 2 | 2 | 3 |
| S | 4 | 4 | 3 | 3 | 3 | 2 |
The table gives not only the distance but also the edit sequence. Start at the bottom-right corner and walk back to the upper-left corner, looking at each cell to see which neighbor the value came from. This process is called traceback. D[4][5] = 2 comes from the diagonal because S = S. D[3][4] = 2 again comes from the diagonal because R = R. D[2][3] = 2 comes from D[2][2] = 1 on the left by an insertion: I is inserted. D[2][2] = 1 comes from the diagonal with A = A; D[1][1] = 1 comes from the diagonal with the substitution C → P. The bold cells show this path. The result: substitute C → P, A matches, insert I, R and S match. The transformation is CARS → PARS → PAIRS.
Confusing the table index with the string index. The table has size (m + 1) × (n + 1) because row 0 and column 0 are for the empty prefix. When D[i][j] is computed, the characters compared are a.charAt(i − 1) and b.charAt(j − 1). Forgetting to initialize the first row and column also spoils the result: since Java initializes the array with zeros, the borders stay 0 and the distance comes out too small.
10.6.5Java code and trace
The recurrence translates directly into code:
int levenshtein(String a, String b) {
int m = a.length(), n = b.length();
int[][] D = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) D[i][0] = i; // deletion
for (int j = 0; j <= n; j++) D[0][j] = j; // insertion
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (a.charAt(i - 1) == b.charAt(j - 1))
D[i][j] = D[i - 1][j - 1]; // equal
else
D[i][j] = 1 + Math.min(D[i - 1][j - 1], // substitute
Math.min(D[i][j - 1], // insert
D[i - 1][j])); // delete
return D[m][n];
}The first two loops fill the borders of the table. The two nested loops fill the remaining cells row by row. If the characters are equal, the upper-left value is copied; otherwise 1 is added to the smallest of the three neighbors. On the examples in the slides the code gives these values: kitten → sitting = 3, ercan → sercan = 1 (the initial s is inserted), apple → banana = 5. Let us trace the code with the call “kar” → “ark”. Write a = “kar” along the rows and b = “ark” along the columns.
levenshtein("kar", "ark"): the borders are filled. Column 0 shows i deletions and row 0 shows j insertions.| Cell | Characters | Computation | Value |
|---|---|---|---|
| D[1][1] | k ≠ a | 1 + min(substitute 0, insert 1, delete 1) | 1 |
| D[1][2] | k ≠ r | 1 + min(substitute 1, insert 1, delete 2) | 2 |
| D[1][3] | k = k | upper left | 2 |
| D[2][1] | a = a | upper left | 1 |
| D[2][2] | a ≠ r | 1 + min(substitute 1, insert 1, delete 2) | 2 |
| D[2][3] | a ≠ k | 1 + min(substitute 2, insert 2, delete 2) | 3 |
| D[3][1] | r ≠ a | 1 + min(substitute 2, insert 3, delete 1) | 2 |
| D[3][2] | r = r | upper left | 1 |
| D[3][3] | r ≠ k | 1 + min(substitute 2, insert 1, delete 3) | 2 |
a[0] = b[2] = 'k': no cost; D[1][3] takes the 2 from the upper left.The result is 2. Traceback starts at D[3][3]. The value came from D[3][2] = 1 on the left by an insertion: a k is inserted at the end. D[3][2] comes from D[2][1] with r = r, and that from D[1][0] = 1 with a = a. D[1][0] is the deletion of k. With substitutions alone, three edits would be needed (k → a, a → r, r → k); because the last two letters of “kar” equal the first two letters of “ark”, the delete–insert path is shorter.
This example also reminds us that the Levenshtein distance does not count a swap of letters as a single operation. In the transformation “saat” → “asat”, the first two letters have exchanged places; the distance is 2. The measure that counts a swap of two adjacent letters as one operation is called the Damerau–Levenshtein distance. Because a significant share of spelling errors are swaps of adjacent letters, spell checkers often use this variant.
10.6.6Two-row memory
Filling a row requires only the previous row. If only the distance is wanted, storing the whole table is unnecessary. Two arrays suffice: prev and curr. When each row is finished, the two arrays swap places.
int levenshteinTwoRows(String a, String b) {
if (a.length() < b.length()) { String t = a; a = b; b = t; } // b is the shorter
int n = b.length();
int[] prev = new int[n + 1], curr = new int[n + 1];
for (int j = 0; j <= n; j++) prev[j] = j;
for (int i = 1; i <= a.length(); i++) {
curr[0] = i;
for (int j = 1; j <= n; j++)
if (a.charAt(i - 1) == b.charAt(j - 1))
curr[j] = prev[j - 1];
else
curr[j] = 1 + Math.min(prev[j - 1], Math.min(curr[j - 1], prev[j]));
int[] t = prev; prev = curr; curr = t; // swap the rows
}
return prev[n];
}The method first makes the shorter string b; the length of the arrays is then min(m, n) + 1. curr[0] = i is the boundary value. The inner loop applies the same recurrence: the upper left is prev[j − 1], the upper is prev[j], and the left is curr[j − 1]. When a row is finished, the references are swapped and the new row becomes prev. After the loop the answer is in prev[n]. On all the examples in the slides, the method gives the same result as the full table.
The saving is large. Let each of two strings have 10,000 characters. The full table holds 10,0012 ≈ 108 integers, about 400 MB. The two-row version uses 2 · 10,001 integers, about 80 KB. The time is still O(m · n). The price is that traceback is no longer possible; if the edit sequence is also wanted, the full table or a more advanced technique (Hirschberg's algorithm) is needed.
10.6.7Other similarity measures
Levenshtein is not the only similarity measure. Depending on the structure of the problem, a simpler or different measure may fit better. Table 10.21 compares four measures on the same pair of strings, AGGTAB and GXTXAYB.
| Measure | What it measures | Time | AGGTAB · GXTXAYB |
|---|---|---|---|
| Hamming | number of differing positions in two strings of equal length | O(n) | undefined (6 ≠ 7) |
| Levenshtein | number of insertions, deletions, and substitutions | O(m · n) | 4 |
| LCS | length of the longest common subsequence | O(m · n) | 4 (GTAB) |
| Longest common substring | length of the longest common contiguous part | O(m · n) | 1 (e.g., “G”) |
The Hamming distance is defined only for strings of equal length and counts the differing characters at corresponding positions. It is computed in a single pass, in O(n) time. For example, the Hamming distance between “karolin” and “kathrin” is 3 (r/t, o/h, l/r). The Hamming measure is suitable when there are no lost or extra characters: fixed-length binary codes, bit errors in communication.
int hamming(String a, String b) {
if (a.length() != b.length())
throw new IllegalArgumentException("lengths differ");
int d = 0;
for (int i = 0; i < a.length(); i++)
if (a.charAt(i) != b.charAt(i)) d++;
return d;
}For two strings of equal length, the Levenshtein distance cannot exceed the Hamming distance. Every differing position that Hamming counts can be fixed by one substitution, which is a transformation Levenshtein allows. Levenshtein, which also uses insertions and deletions, sometimes finds a shorter path. For the pair “karolin” and “kathrin”, both measures are 3.
A sequence obtained by deleting some characters of a string is called a subsequence of that string; the relative order of the remaining characters is preserved, but they need not be consecutive. The longest common subsequence (LCS) of two strings is the longest sequence that is a subsequence of both. The longest common substring, on the other hand, is the longest part that occurs consecutively in both.
The LCS of AGGTAB and GXTXAYB is GTAB. The letters G, T, A, B occur in this order in both strings: at positions 2, 4, 5, 6 in AGGTAB and at positions 1, 3, 5, 7 in GXTXAYB. It does not matter that other letters lie in between. The longest common substring is only 1 character long: there is no two-letter part that occurs consecutively in both strings. The LCS is also found with a DP table similar to Levenshtein's:
int lcs(String a, String b) {
int m = a.length(), n = b.length();
int[][] L = new int[m + 1][n + 1]; // row 0 and column 0 are 0
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (a.charAt(i - 1) == b.charAt(j - 1))
L[i][j] = L[i - 1][j - 1] + 1; // diagonal + 1
else
L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
return L[m][n];
}The recurrence is this: if the characters are equal, L[i][j] = L[i−1][j−1] + 1, that is, 1 is added to the diagonal value; if they are not equal, L[i][j] = max(L[i−1][j], L[i][j−1]). Where Levenshtein looks for the minimum, LCS looks for the maximum. The method returns 4 for AGGTAB · GXTXAYB, 3 for CARS · PAIRS (ARS), and 4 for kitten · sitting (ittn).
There is a simple link between the LCS and the edit distance. If only insertion and deletion are allowed and substitution is forbidden, the distance is m + n − 2 · LCS. Every character that is not in the LCS is either deleted or inserted. For AGGTAB · GXTXAYB this is 6 + 7 − 8 = 5. Levenshtein, which also allows substitution, combines one deletion and one insertion into a single substitution and lowers the distance to 4.
For the longest common substring the recurrence is simpler still. If the characters are equal, L[i][j] = L[i−1][j−1] + 1; if they are not, L[i][j] = 0, because the contiguity is broken. The answer is not in the bottom-right corner but at the largest value in the table:
String longestCommonSubstring(String a, String b) {
int m = a.length(), n = b.length(), best = 0, end = 0;
int[][] L = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (a.charAt(i - 1) == b.charAt(j - 1)) {
L[i][j] = L[i - 1][j - 1] + 1; // the run grows
if (L[i][j] > best) { best = L[i][j]; end = i; }
} // no match: stays 0
return a.substring(end - best, end);
}The method returns “ercan” for “ercan” · “sercan” and “itt” for kitten · sitting. If there are several parts of equal length, it gives the first one found; for the pair AGGTAB · GXTXAYB it returns “A”. Plagiarism detection and finding the common blocks of two files are places where this measure is used.
Distances can also be converted into a comparable similarity ratio. A common definition is 1 − d / max(m, n): it gives 1 for identical strings and a value close to 0 for strings with nothing in common. For kitten · sitting this is 1 − 3/7 ≈ 0.57. A spell checker might, for example, show dictionary words with a similarity above 0.7 as suggestions.
Confusing a subsequence with a substring. The LCS does not require contiguity; the longest common substring does. For the pair AGGTAB · GXTXAYB, one is 4 and the other 1. Applying the Hamming distance to strings of different lengths is another mistake: by definition it cannot be computed, and the hamming method above should throw an error in this case.
10.7The suffix array
If the same pattern will be searched for many times in a text, scanning the text from the beginning on every search is expensive. The index at the back of a book solves this problem: the words are in a sorted list, and the pages on which each occurs are written next to it. The suffix array builds such an index for all the substrings of a text.
10.7.1Definition
The i-th suffix of a string t of n characters is the substring that starts at position i and runs to the end of the string: t[i..n−1]. The suffix array (SA) of t consists of the starting indices of all the suffixes arranged in lexicographic order: SA[k] is the position at which the k-th suffix in the sorted list begins.
| i | suffix | rank | SA | sorted suffix |
|---|---|---|---|---|
| 0 | banana | 0 | 5 | a |
| 1 | anana | 1 | 3 | ana |
| 2 | nana | 2 | 1 | anana |
| 3 | ana | 3 | 0 | banana |
| 4 | na | 4 | 4 | na |
| 5 | a | 5 | 2 | nana |
“banana” has six suffixes. When they are sorted, “a” comes first, because it is a prefix of “ana” and “anana”. Then come “ana”, “anana”, “banana”, “na”, “nana”. The suffix array is SA = [5, 3, 1, 0, 4, 2]. The array stores only the starting indices, not the suffixes. A suffix itself is obtained when needed with t.substring(SA[k]).
The power of the suffix array rests on a simple observation: every substring of a string is a prefix of some suffix. The substring “nan” is a prefix of the suffix “nana”, which starts at position 2. So finding where a pattern occurs in the text means finding the suffixes that begin with that pattern. Because the suffixes are sorted, these suffixes sit next to each other in the list.
An older structure that does the same job is the suffix trie: a tree that inserts all the suffixes into a trie. A suffix trie searches very fast, but its number of nodes is proportional to the number of distinct substrings and is O(n2) in the worst case. Even a six-letter string such as “banana” has 15 distinct substrings, and hence 16 nodes counting the root. The suffix array holds only n integers: O(n) memory. String search, sorting, genome sequence analysis, the BWT, and data compression are the main uses of the suffix array.
10.7.2Construction methods
The easiest way to build the suffix array is to sort all the suffixes with a comparison sort:
int[] suffixArray(String t) { // brute force: O(n² log n)
int n = t.length();
Integer[] ix = new Integer[n];
for (int i = 0; i < n; i++) ix[i] = i;
Arrays.sort(ix, (x, y) -> t.substring(x).compareTo(t.substring(y)));
int[] sa = new int[n];
for (int i = 0; i < n; i++) sa[i] = ix[i];
return sa;
}This brute-force method makes O(n log n) comparisons. Each comparison reads two suffixes character by character and takes O(n) in the worst case; in addition, substring copies a new string on every call. The total time is O(n2 log n). This is adequate for short texts but unusable for a genome sequence of a few million characters. Faster methods avoid comparing suffixes character by character.
| Method | Idea | Time |
|---|---|---|
| Brute force | all suffixes are created and sorted with Arrays.sort; each comparison is O(n) | O(n2 log n) |
| Manber–Myers (1990) | prefix doubling: the ranks for 2k characters are found from the ranks for k characters by radix-sorting the rank pairs | O(n log n) |
| Larsson–Sadakane (1999) | the same doubling; only groups that have not yet been separated are re-sorted | O(n log n) |
| DC3 (2003), SA-IS (2009) | some of the suffixes are sorted recursively, and the rest are derived from them and merged | O(n) |
Prefix-doubling methods run in O(n log n) time, not linear. Linear-time construction became possible only with later algorithms such as DC3 and SA-IS. SA-IS is still one of the fastest methods in practice today and is used in many bioinformatics tools.
10.7.3Prefix doubling
The idea of Manber and Myers is this. First the suffixes are sorted by their first character only, and each suffix is assigned a rank: suffixes with the same first character get the same rank. Then they are sorted by the first two characters, the first four, the first eight. In each round the prefix length considered doubles. An observation that speeds up a round is this: the first 2k characters of the i-th suffix consist of two parts. The first k characters are the prefix of the suffix starting at i, and the next k characters are the prefix of the suffix starting at i + k. The k-character ranks of both are known from the previous round. So the sort on 2k characters is done without comparing letters, by sorting the number pairs (rank[i], rank[i + k]).
Three rounds on “banana”:
- 1 character. The suffixes are sorted by first character: a → 0, b → 1, n → 2. The ranks: rank[0..5] = 1, 0, 2, 0, 2, 0. The suffixes starting at 1, 3, 5 (all starting with a) have not yet been separated.
- 2 characters. The key is (rank[i], rank[i + 1]); if i + 1 ≥ n, the second item is −1. 5: (0, −1); 1: (0, 2); 3: (0, 2); 0: (1, 0); 2: (2, 0); 4: (2, 0). After sorting, the new ranks are 5 → 0, 1 and 3 → 1, 0 → 2, 2 and 4 → 3. The two suffixes starting with “an” and the two starting with “na” are still equal.
- 4 characters. The key is (rank[i], rank[i + 2]). 5: (0, −1); 3: (1, 0); 1: (1, 1); 0: (2, 3); 4: (3, −1); 2: (3, 3). All the keys are distinct; the new ranks spread from 0 to 5. The sort is complete: SA = [5, 3, 1, 0, 4, 2].
| i | first 4 characters | key | new rank |
|---|---|---|---|
| 5 | a | (0, −1) | 0 |
| 3 | ana | (1, 0) | 1 |
| 1 | anan | (1, 1) | 2 |
| 0 | bana | (2, 3) | 3 |
| 4 | na | (3, −1) | 4 |
| 2 | nana | (3, 3) | 5 |
One row of the third round sums up the method. “ana”, starting at 3, and “anana”, starting at 1, have the same first two characters; both have 2-character rank 1. The difference lies in the next two characters: the rank of “a”, starting at 3 + 2 = 5, is 0, and the rank of “an…”, starting at 1 + 2 = 3, is 1. Since (1, 0) < (1, 1), “ana” comes before “anana”. No letter has been read again.
The number of rounds is at most ⌈log2 n⌉, because when 2k ≥ n, the prefix considered covers every suffix from beginning to end and all the ranks must be distinct. In each round, the n number pairs can be sorted in O(n) with a two-pass radix sort. The total time is O(n log n). To keep the idea clear, the version below sorts the number pairs with Arrays.sort; each round therefore takes O(n log n) and the total O(n log2 n):
int[] prefixDoubling(String t) { // sorted with Arrays.sort
int n = t.length();
Integer[] sa = new Integer[n];
int[] rank = new int[n], tmp = new int[n];
for (int i = 0; i < n; i++) { sa[i] = i; rank[i] = t.charAt(i); }
for (int k = 1; ; k *= 2) {
final int kk = k;
final int[] r = rank;
Comparator<Integer> cmp = (x, y) -> {
if (r[x] != r[y]) return Integer.compare(r[x], r[y]);
int rx = x + kk < n ? r[x + kk] : -1, ry = y + kk < n ? r[y + kk] : -1;
return Integer.compare(rx, ry);
};
Arrays.sort(sa, cmp); // key: (rank[i], rank[i + k])
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++)
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp.compare(sa[i - 1], sa[i]) < 0 ? 1 : 0);
System.arraycopy(tmp, 0, rank, 0, n);
if (rank[sa[n - 1]] == n - 1) break; // all ranks distinct
}
int[] s = new int[n];
for (int i = 0; i < n; i++) s[i] = sa[i];
return s;
}The rank array initially holds the character codes. In each round the comparator cmp looks first at rank[x] and, if equal, at rank[x + k]. After sorting, the new ranks are assigned: a suffix's rank increases by one if it differs from the one before it, and stays the same otherwise. When the rank of the last suffix is n − 1, all ranks are distinct and the loop ends. The method returns [5, 3, 1, 0, 4, 2] for “banana” and [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2] for “mississippi”; both are the same as with brute force.
10.7.4Searching with a suffix array
Because the suffixes are sorted, the suffixes that start with a pattern P form a contiguous range in the SA. The two ends of the range are found by binary search. The first end is the first suffix that is not smaller than P. The second end is the first suffix after that point that does not start with P.
int[] search(String t, int[] sa, String p) {
int lo = 0, hi = sa.length;
while (lo < hi) { // first >= p
int mid = (lo + hi) / 2;
if (t.substring(sa[mid])
.compareTo(p) < 0) lo = mid + 1;
else hi = mid;
}
int first = lo;
hi = sa.length;
while (lo < hi) { // not starting with p
int mid = (lo + hi) / 2;
if (t.startsWith(p, sa[mid]))
lo = mid + 1;
else hi = mid;
}
return new int[] { first, lo };
}The first loop is a classic “lower bound” binary search. If the middle suffix is smaller than P, the end being sought lies to the right: lo = mid + 1. Otherwise the end is at mid or to its left: hi = mid. When the loop finishes, lo is the rank of the first suffix not smaller than P and is written into first. The second loop leaves lo where it is and pulls hi back to the end of the array. This time the question is “does this suffix start with P?”. If it does, the end of the range lies to the right. When the loop finishes, lo points just past the range. The method returns the half-open range [first, lo).
search("banana", sa, "an"): lo = 0, hi = 6 (end of the array). The suffixes starting with “an” are shown with a blue prefix.| Loop | mid | Suffix | Question and answer | New range |
|---|---|---|---|---|
| 1 | 3 | banana | “banana” < “an”? no → hi = 3 | [0, 3) |
| 1 | 1 | ana | “ana” < “an”? no → hi = 1 | [0, 1) |
| 1 | 0 | a | “a” < “an”? yes → lo = 1 | [1, 1) |
| — | — | — | first = 1, hi = 6 | [1, 6) |
| 2 | 3 | banana | starts with “an”? no → hi = 3 | [1, 3) |
| 2 | 2 | anana | starts with “an”? yes → lo = 3 | [3, 3) |
first = 1. For the second search, hi is pulled back to the end of the array.[1, 3): ranks 1 and 2 are selected; their SA values are 3 and 1.The result is [1, 3): ranks 1 and 2. The SA values at these ranks are 3 and 1. “an” occurs in “banana” at positions 1 and 3. A total of 5 comparisons were made. Each binary search makes at most ⌊log2 6⌋ + 1 = 3 comparisons. Each comparison reads at most m = |P| characters. The total time is O(m log n). Even in a text of a billion characters, each search finishes with about 60 suffix comparisons.
If an LCP array (longest common prefix) is added next to the suffix array, more questions can be answered. The LCP array holds the length of the longest common prefix of two neighboring suffixes in the sorted list. For “banana”, the common prefix of “a” and “ana” is 1 character, and that of “ana” and “anana” is 3. The longest substring that occurs twice in the text is the largest value of the LCP array. In “banana” this is “ana”, and it is found by one scan of the LCP array, in O(n).
Confusing the values of the suffix array with rank numbers. The range [1, 3) returned by search consists of ranks in the sorted list; the positions of the pattern in the text are the sa[k] values at those ranks (3 and 1). Another mistake is to assume the positions of the range are in order: the SA holds the sorted suffixes, while the positions come in mixed order.
10.8The Burrows–Wheeler transform
Compression algorithms feed on repetition: “AAAAA” can be shortened to the information that the letter “A” is written five times. But in natural text, equal letters are usually not adjacent. The Burrows–Wheeler transform rearranges the letters so that equal letters are gathered together. Moreover, it does so in a reversible way.
10.8.1Definition and steps
The Burrows–Wheeler transform (BWT) of a string s is computed in three steps. First, all the cyclic rotations of s are created. Then these rotations are sorted lexicographically. Finally, the last characters of the sorted rotations are read from top to bottom. The resulting string is called the L column. For the inverse transform, either the row number of the original string in the sorted list is stored, or a $ marker, smaller than every character of the alphabet and occurring only once, is appended to s.
A rotation is obtained by moving the first character of the string to the end; when this is done n times, the string returns to the start. A string of n characters has n rotations. The BWT does not change the characters, only their positions: the L column is another arrangement of the letters of s. Michael Burrows and David Wheeler published the transform in a technical report in 1994.
In the small example in Figure 10.32, the four rotations of “aba$” are aba$, ba$a, a$ab, and $aba. Because $ is the smallest character, $aba comes first in the sorted list, followed by a$ab, aba$, and ba$a. The last characters are a, b, $, a: L = “ab$a”. The first column of the sorted list is the F column: $, a, a, b.
10.8.2Examples: BANANA and abraca
How the BWT groups letters is clearly visible in the “BANANA” example. In this example $ is not used; the number of the original row is stored instead.
The rotations are BANANA, ANANAB, NANABA, ANABAN, NABANA, and ABANAN. The sorted list is ABANAN, ANABAN, ANANAB, BANANA, NABANA, NANABA. The last characters are N, N, B, A, A, A. The output is (NNBAAA, 3). In the original string no letter was equal to its neighbor; after the transform, two N's and three A's are adjacent.
The reason for the grouping is the structure of sorting. In the sorted list, rotations that begin with the same characters sit next to each other. For example, the two rotations that begin with “ANA…” are neighbors. The L column holds the character that comes just before the first character of each rotation. In natural text, the same character usually comes before the same context: in English the character before the context “he” is often t (the), and in Turkish the character before the context “ğı” is often a (ağı, dağı). When similar contexts come together in the sorted order, the equal characters that precede them also fall next to each other in L.
For “abraca” the sorted rotations are aabrac, abraca, acaabr, bracaa, caabra, racaab. The last column is L = “caraab”. The original “abraca” is in row 1 of the sorted matrix, counting from 0; this index is stored for the inverse transform. The first column is F = aaabcr and is the sorted version of the letters of L. This is always true: since every rotation contains the same letters, F and L carry the same multiset of letters, and F is sorted. Once L is known, sorting L is enough to find F.
The direct method explicitly produces the n rotations and sorts them:
String bwt(String s) { // direct method; s ends with $
int n = s.length();
String[] rot = new String[n];
for (int i = 0; i < n; i++)
rot[i] = s.substring(i) + s.substring(0, i);
Arrays.sort(rot); // O(n² log n) time, O(n²) space
StringBuilder L = new StringBuilder();
for (String r : rot) L.append(r.charAt(n - 1));
return L.toString();
}This method uses O(n2) memory, because each of the n rotations has n characters. The sort makes O(n log n) comparisons and each comparison can take O(n): O(n2 log n) time in total. A one-megabyte block would need a matrix of 1012 characters; this is clearly impractical. In practice the BWT is computed from the suffix array. If the text ends with $, the order of the rotations is the same as the order of the suffixes. Two rotations separate no later than when they reach $; what follows $ takes no part in the comparison. The k-th sorted rotation starts at SA[k]; its last character is the character just before that. So L[k] = T[SA[k] − 1], and if SA[k] = 0 then L[k] = $. The formula is for the BWT with $; the BWT with $ and the cyclic BWT give different results: the cyclic BWT of BANANA is NNBAAA, while that of BANANA$ is ANNB$AA. If the suffix array is built in linear time, the BWT is also obtained in O(n).
10.8.3Inversion: the LF mapping
The truly surprising thing about the BWT is that the original text can be recovered from the L column alone (and from $ or the row index). As an example, take T = “banana$”. The $ is the smallest and a unique character.
| i | F | … | L |
|---|---|---|---|
| 0 | $ | banan | a |
| 1 | a | $bana | n |
| 2 | a | na$ba | n |
| 3 | a | nana$ | b |
| 4 | b | anana | $ |
| 5 | n | a$ban | a |
| 6 | n | ana$b | a |
The BWT output is L = “annb$aa”. F is the sorted version of L: F = “$aaabnn”. Since each row is a rotation, the last character of a row, L[i], comes in the text just before the first character F[i]. The inverse transform uses this adjacency as a chain. The only missing piece of information is which row of F a character in L corresponds to. When the same letter occurs several times, this is not obvious. The theorem below removes this ambiguity.
If a character c occurs for the k-th time in L (counting from 0), then the same character in the text is also the k-th occurrence of c in F. Accordingly, the row of L[i] in F is LF(i) = C[c] + occ[i]. Here c = L[i], C[c] is the number of characters in the text smaller than c (that is, the row where c starts in F), and occ[i] is how many c's precede L[i] in L, that is, which c it is, counting from 0.
Two rows that end with c in L have the forms x · c and y · c; let x · c come first in the sorted list, that is, x · c < y · c. Rotating these two rows once to the right gives the rows c · x and c · y; these are also rows of the matrix and begin with c in F. When two strings begin with the same character, the rest decides their order. x · c and y · c have equal length, and the first position where they differ lies within x and y. Hence x < y, and c · x < c · y. So the order of the rows ending with c in L is the same as the order of their rotated versions in F. The k-th c in L is the k-th c in F. Since F is sorted, the first row of c in F is C[c], and the k-th c is in row C[c] + k. □
The inverse transform is now simple. The row beginning with $ is row 0; this row is a rotation of the text itself, and its last character L[0] is the last character of the text before the $. L[0] is read and the walk goes to row LF(0). The L character of that row is the previous character in the text. As the walk continues, the text is read from end to beginning. For “banana$” the rows are visited in the order 0 → 1 → 5 → 2 → 6 → 3 → 4. The L characters read are a, n, a, n, a, b. Reversed, they give “banana”.
If the occurrence counts and the C table are computed beforehand in one pass, each step takes constant time and the inverse transform takes O(n). If the text has no $, as in the BANANA example, the original row index (3) is stored and the walk is started from that row instead of 0.
10.8.4Code trace: inverseBwt
String inverseBwt(String L) { // with $
int n = L.length();
int[] occ = new int[n];
int[] count = new int[256];
int[] C = new int[256];
for (int i = 0; i < n; i++)
occ[i] = count[L.charAt(i)]++;
for (int c = 1; c < 256; c++)
C[c] = C[c - 1] + count[c - 1];
StringBuilder s = new StringBuilder();
int i = 0; // the $ row
for (int k = 0; k < n - 1; k++) {
char c = L.charAt(i);
s.insert(0, c);
i = C[c] + occ[i]; /* LF(i) */
}
return s.toString();
}The method has four parts. The first loop computes occ[i] for each i: count[c] holds how many c's have been seen so far in L and then increases by one. The second loop builds the C table with a prefix sum: C[c] is the number of all characters smaller than c. The third part is the walk. It starts at i = 0, the $ row. At each step L.charAt(i) is read and added to the front of the text being built (s.insert(0, c)); since the text is read from end to beginning, no reversal is needed. Then i is updated to LF(i). The loop runs n − 1 rounds; the $ is not added to the text.
inverseBwt("annb$aa"): L, the occurrence counts, and F. occ[6] = 2, because L[6] is the third a.The results of the preparation steps are these. occ = [0, 0, 1, 0, 0, 1, 2]: the a's in L (positions 0, 5, 6) get the order 0, 1, 2 and the n's (1, 2) get 0, 1; b and $ are 0 because they are unique. The C table: C[$] = 0, C[a] = 1, C[b] = 4, C[n] = 5. These values are the rows where each letter starts in the F column.
k | i | L[i] | s | LF(i) = C[c] + occ[i] |
|---|---|---|---|---|
| 0 | 0 | a | a | 1 + 0 = 1 |
| 1 | 1 | n | na | 5 + 0 = 5 |
| 2 | 5 | a | ana | 1 + 1 = 2 |
| 3 | 2 | n | nana | 5 + 1 = 6 |
| 4 | 6 | a | anana | 1 + 2 = 3 |
| 5 | 3 | b | banana | 4 + 0 = 4 |
L[0] = 'a' is added to the text; LF(0) = C[a] + occ[0] = 1. The arrow shows that the first a in L corresponds to the first a in F.After the sixth round, i = 4. The L character of row 4 is $; this row is “banana$” itself, and the walk has come back to the start. The loop ends at exactly this point. The time is O(n + R) and the extra memory is O(n + R) for the occ, count, and C arrays. There is an implementation detail: because s.insert(0, c) shifts the whole string on every call, it actually takes O(n). For large inputs, the characters are written into an array from back to front, or appended at the end and reversed once at the very end.
Storing the BWT output as just the L column. If neither the $ marker nor the original row index is stored, the transform cannot be undone: all the rotations of “BANANA” give the same L column (NNBAAA). Another mistake is not choosing $ as the smallest character of the alphabet. In Java, '$' (36) is smaller than letters and digits, but if the text contains a space (32), this condition breaks and the LF mapping goes to the wrong rows.
10.8.5Role in compression
The BWT is not compression by itself; its output has the same length as its input. It prepares the data for compression. The widely used bzip2 program uses the BWT at the head of a four-stage chain:
- BWT. The text is split into blocks and each block is transformed. Equal letters are gathered together.
- Move-to-front (MTF). Each character is encoded by its position in a list and is then moved to the front of the list. Recently seen letters are encoded by small numbers; repeated equal letters become 0's.
- Run-length encoding (RLE). Consecutive equal values are written as (value, repeat count) pairs. The long runs of 0's produced by MTF shrink here.
- Huffman coding. Frequent values are given short bit strings and rare values long ones.
Each link in the chain takes advantage of the structure the previous one prepared. Without the BWT, the output of MTF would not contain so many 0's; without MTF, RLE would find no long runs. The BWT is also important in bioinformatics. A structure called the FM-index combines the BWT with the LF mapping to search for short reads in a genome of billions of letters directly on compressed data.
10.9Common mistakes
The warnings scattered through the notes and the list of mistakes in the slides are collected here.
Taking code order for the alphabet. compareTo compares character codes: “Zebra” < “apple” and “şeker” > “zeytin”. For upper/lower-case differences and Turkish letters, a Collator or a normalization beforehand is needed.
Sorting numbers as strings. “10” < “9”, because '1' < '9'. For numeric order, convert the strings to integers or pad them on the left with zeros to the same length.
An unstable subsort in LSD. Every pass must be stable; otherwise the order established by earlier passes is destroyed. In counting sort, placement runs from back to front. A version that places from front to back puts the ten strings from the slides in the order add, ace, bed, bee, bad, ….
An unescaped dot and a greedy .*. a.b also matches “a+b”; <.*> swallows the whole line. The right choices are \. and the lazy .*?. Nested quantifiers such as (a+)+$ can lead to an exponential number of attempts in backtracking engines.
Confusing find with matches. find looks for a part; matches requires the whole string. For validation, either use matches or wrap the expression in ^ and $; otherwise an input such as “abc123” may be accepted as a “number”.
Taking an intermediate state of an FSM for the result. A DFA's decision depends only on the state when the input ends. Passing through an accepting state along the way does not make the string accepted. In a pattern automaton, returning to 0 on a mismatch misses matches; the correct state is the longest matching prefix.
An index shift in the DP table. The table is (m + 1) × (n + 1); for D[i][j], charAt(i − 1) and charAt(j − 1) are compared. Not initializing the first row and column spoils the result.
Confusing a subsequence with a substring. The LCS does not require contiguity; the longest common substring does. The Hamming distance is defined only for strings of equal length.
Not storing the row index or $ in the BWT. All the rotations of a string give the same L column; without extra information the transform cannot be undone. In the suffix array, ranks and text positions (SA values) must not be confused with each other.
10.10Summary
- Lexicographic order: the first differing character decides; if one string is a prefix of the other, the shorter comes first. Computers use character codes: capital letters come before lowercase ones, and Turkish letters come after z. One comparison takes O(W).
- Comparison sorting: O(N2 · W) with the simple method, O(W · N log N) with merge sort. Every comparison-based method makes Ω(N log N) comparisons.
- LSD radix sort: right to left, a stable counting sort on that character in each pass; O(W · (N + R)) time, O(N + R) memory. Its correctness rests on the invariant “sorted by the last k characters after k passes” and on stability.
- MSD radix sort: left to right, each bucket sorted recursively on its own; only the distinguishing prefixes are read. Switch to insertion sort on small buckets.
- Regular expressions:
. * + ? [ ] ^ $ ( ) { } |and\d \w \s \b; quantifiers are greedy by default and become lazy with a?. Lookaround expressions test a position and consume no characters. In Java,Pattern/Matcher;findsearches for a part,matchesfor the whole string. - Finite state machine: (Q, Σ, δ, q0, F). A DFA has one transition per (state, symbol), and scanning takes O(n). DFAs, NFAs, and regular expressions recognize the same languages; the subset construction produces 2n states in the worst case.
- Pattern-matching automaton: the state is the length of the longest prefix of the pattern that matches the end of the text. Construction O(m · |Σ|), search O(n); it is the automaton form of KMP.
- Levenshtein: upper left if equal, otherwise 1 + min(delete, insert, substitute); O(m · n) time. The edit sequence is read back from the table; two rows suffice for the distance alone.
- Other measures: Hamming for equal lengths, O(n). LCS and longest common substring O(m · n). With insertion and deletion only, the distance is m + n − 2 · LCS.
- Suffix array: the starting indices of the sorted suffixes; O(n) memory. Built in O(n2 log n) by brute force, O(n log n) by prefix doubling, and O(n) with SA-IS. Search takes O(m log n) with two binary searches.
- BWT: the last column of the sorted rotations and the row index (or $). It groups equal letters; it is inverted in O(n) with the LF mapping. It is the first step of
bzip2: BWT → move-to-front → RLE → Huffman.
10.11Key terms
- string
- alphabet
- prefix
- suffix
- substring
- lexicographic order
- stable sort
- counting sort
- radix sort
- LSD / MSD radix sort
- regular expression
- quantifier
- lookahead / lookbehind
- finite state machine (FSM)
- deterministic finite automaton (DFA)
- subset construction
- trap state
- edit distance
- Levenshtein distance
- dynamic programming
- traceback
- longest common subsequence (LCS)
- longest common substring
- suffix array
- prefix doubling
- Burrows–Wheeler transform (BWT)
- move-to-front (MTF)
10.12Test Yourself
What is the result when the array
{"kedi", "Kedi", "kediler", "ked", "kafa", "çay"}is sorted withArrays.sort? Where does it differ from Turkish dictionary order?Answer
The result is
Kedi, kafa, ked, kedi, kediler, çay. 'K' (75) comes before all the lowercase letters. “kafa” goes ahead at the second character with a < e. “ked” is a prefix of “kedi”, and “kedi” is a prefix of “kediler”. Because 'ç' (231) is even larger than z, “çay” falls to the very end. In a Turkish dictionary, “çay” comes before the words starting with k, and “Kedi” and “kedi” come next to each other.If LSD radix sort is applied to the strings
dog, cat, dot, cab, cog, what does the array look like after each pass?Answer
By the 3rd character:
cab, dog, cog, cat, dot(b < g < t; dog and cog keep their input order). By the 2nd character:cab, cat, dog, cog, dot(in bucket a, cab, cat; in bucket o, dog, cog, dot in the earlier order). By the 1st character:cab, cat, cog, dog, dot.Which of the strings “A12”, “B1234”, “c123”, “Z999x”, and “Q7y” does the expression
^[A-Z]\d{2,3}[a-z]?$match, in the sense ofmatches?Answer
Only “A12” and “Z999x”. The expression requires one capital letter, two or three digits, and an optional single lowercase letter. “B1234” has four digits. “c123” starts with a lowercase letter. “Q7y” has a single digit.
At which positions does the pattern
(?<=a)bmatch in the text “abcabb”? In the text “abbb”, which parts does afindloop find withb+and withb+??Answer
The lookbehind selects the b's that have an a before them: positions 1 and 4. The b at 5 has a b before it. Because the lookaround consumes no characters, the text of both matches is just “b”. In the text “abbb”, the greedy
b+finds “bbb” as a single match. The lazyb+?takes a single b each time and gives three separate “b” matches.What is the transition table of the pattern-matching automaton for the pattern “aab” (alphabet {a, b})? How do the states change while the text “aaab” is read, and where is the pattern found?
Answer
State 0: a → 1, b → 0. State 1: a → 2, b → 0. State 2: a → 2, b → 3. State 3: a → 1, b → 0. If an a arrives in state 2, the end of what has been read is “aaa” and the longest matching prefix is still “aa”; so the automaton stays in 2. For “aaab” the states are 1, 2, 2, 3. State 3 is reached at character number 3; the pattern starts at position 3 − 3 + 1 = 1.
What is
levenshtein("kitap", "katip")? What is the last row of the table, and which edit sequence gives this distance?Answer
The distance is 2. The last row (p) is 5, 4, 3, 3, 3, 2. The letters k, t, and p are at the same positions in the two strings; only the 2nd and 4th letters differ. One solution is two substitutions: i → a (katap), a → i (katip).
What are the LCS length, the insertion-and-deletion-only distance, and the Levenshtein distance for “ABCBDAB” and “BDCABA”?
Answer
The LCS length is 4 (e.g., BCBA). The insertion-and-deletion-only distance is 7 + 6 − 2 · 4 = 5. The Levenshtein distance is also 5; for this pair, substitutions give no shorter path.
What is the suffix array of the string “abaab”? At which ranks are the suffixes that begin with “ab”, and at which positions does the pattern occur in the text?
Answer
The sorted suffixes are aab, ab, abaab, b, baab; SA = [2, 3, 0, 4, 1]. Those beginning with “ab” are at rank 1 (ab) and rank 2 (abaab). Since the SA values are 3 and 0, “ab” occurs in the text at positions 0 and 3.
What is the BWT of the string “abab$”, and how is it inverted with the LF mapping?
Answer
The sorted rotations are $abab, ab$ab, abab$, b$aba, bab$a; L = “bb$aa”. F = “$aabb”, C[$] = 0, C[a] = 1, C[b] = 3; the occurrence counts are 0, 1, 0, 0, 1. The walk starts at 0: L[0] = b, LF = 3; L[3] = a, LF = 1; L[1] = b, LF = 4; L[4] = a, LF = 2. The L character of row 2 is $ and the walk stops. What was read is b, a, b, a; prepending each character gives “abab”.
How is a DFA built that accepts binary strings ending in “00”? Which states does the input “10100” pass through?
Answer
Three states suffice: q0 (the last symbol is not 0, or the input is empty; the start state), q1 (the last symbol is a single 0), and q2 (the last two symbols are 00; accepting). The transitions: q0: 0 → q1, 1 → q0; q1: 0 → q2, 1 → q0; q2: 0 → q2, 1 → q0. For “10100” the path is q0 → q0 → q1 → q0 → q1 → q2 and the string is accepted.
10.13Further reading
- R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Chapter 5: covers string sorting (LSD, MSD, three-way quicksort), substring search, regular expressions, and data compression with Java code and experimental measurements.
- D. Gusfield, Algorithms on Strings, Trees, and Sequences (Cambridge University Press, 1997): treats suffix trees, edit distance, and alignment algorithms in depth with examples from computational biology.
- J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation (3rd ed., 2006): DFAs, NFAs, the subset construction, and a proof of Kleene's theorem.
- R. Cox, “Regular Expression Matching Can Be Simple And Fast” (2007, swtch.com): an article that compares automaton-based matching via Thompson's construction with backtracking engines and shows the exponential slowdown with measurements.
10.14References
- M. Burrows, D. J. Wheeler, “A Block-sorting Lossless Data Compression Algorithm”, DEC SRC Research Report 124, 1994.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 (string-matching automata).
- R. Cox, “Regular Expression Matching Can Be Simple And Fast”, 2007, https://swtch.com/~rsc/regexp/regexp1.html.
- J. E. F. Friedl, Mastering Regular Expressions, 3rd ed., O'Reilly, 2006; the documentation of Java
java.util.regex.Pattern. - D. Gusfield, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.
- J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., 2006.
- V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals”, Soviet Physics Doklady 10(8), 1966.
- U. Manber, G. Myers, “Suffix Arrays: A New Method for On-Line String Searches”, SIAM Journal on Computing 22(5), 1993.
- R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011 (5.1 String Sorts, 5.4 Regular Expressions).
- R. A. Wagner, M. J. Fischer, “The String-to-String Correction Problem”, Journal of the ACM 21(1), 1974.
Related pages: Chapter 10 slides · © Sercan Külcü. All rights reserved.