Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 225 ยท Strings

Lyndon Words, Booth's Algorithm and Burrows-Wheeler Transform

Learn Lyndon words and Duval's factorization, find the minimal rotation of a string in O(n) and build the Burrows-Wheeler transform and its inverse in Python.

Rotating a string moves characters from the front to the back: banana becomes ananab, then nanaba, and so on. Many string problems are about the family of all rotations of a string. Which rotation is smallest in dictionary order? Can two strings be rotations of each other? What happens if you sort all rotations and keep the last column?

This lesson covers three connected ideas. Lyndon words are strings that are strictly smaller than all their proper rotations, and Duval's algorithm splits any string into them in O(n). From that, you get the minimal rotation in linear time (the job of Booth's algorithm, which we solve with a compact two-pointer method). Finally, the Burrows-Wheeler transform (BWT), sorting rotations to make text easy to compress, is built and inverted. You should know string basics and suffix structures.

Lyndon words

A string is a Lyndon word if it is non-empty and strictly smaller than every one of its proper suffixes (equivalently, strictly smaller than all its proper rotations). Examples: a, ab, aab, abb, aabab. Not Lyndon: aa (equal to a rotation), ba (the rotation ab is smaller), abab (equals its own rotation by two).

Chen-Fox-Lyndon theorem: every string can be written in exactly one way as a concatenation of Lyndon words w1 w2 ... wk with w1 >= w2 >= ... >= wk. For example, banana = b | an | an | a, which reads b >= an >= an >= a.

Python Lyndon test by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The number of binary Lyndon words of length 8 is 30, which matches the necklace-style counting formula (1/n) * sum of mu(d) * 2^(n/d) (see Mobius function).

Duval's algorithm

Duval's algorithm finds the Lyndon factorization with three pointers i, j, k, in O(n) time and O(1) extra space. The loop keeps a prefix of the form (Lyndon word)^m + (prefix of that word):

  • k is the position being compared with j.
  • If s[k] == s[j], the pattern continues (move both).
  • If s[k] > s[j], the whole block is a single longer Lyndon word (set j = i, move k).
  • If s[k] < s[j] (or the string ends), emit the repeated Lyndon word of length k - j as many times as it fits, then restart after the emitted part.
Python Duval's Lyndon factorization

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The factors are non-increasing, so equal factors appear together (such as an | an). The outer loop emits at least one character each time, and the inner pointers j never move backward more than the emitted length, so the total work is linear.

Minimal rotation (Booth's problem)

The minimal rotation of s is the lexicographically smallest string among its n rotations. Brute force builds all rotations: O(n^2) time and memory. Booth's algorithm uses a failure function to do it in O(n). An equally fast alternative that fits in a few lines uses two candidates i and j and a match length k:

  • Compare s[i + k] and s[j + k] (indices modulo n).
  • If they are equal, increase k.
  • If one is larger, the candidate with the larger character, and all starting points up to k after it, can never be a minimal start. Jump that candidate forward by k + 1.
  • Make sure the two candidates never coincide.

Each step moves a candidate forward or grows k, and the sum stays below 2n, so the time is O(n).

Python Minimal rotation: two-pointer method vs brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line shows the main use: the minimal rotation is a canonical form for a cyclic string. Comparing canonical forms answers "are these two necklaces the same?" (compare with Burnside's lemma).

The Burrows-Wheeler transform

Take a string s and append a sentinel $ that is smaller than every other character. List all rotations of s + "$", sort them, and write the last character of each sorted rotation. That string is the BWT.

For banana$:

TEXT
$banana   -> a
a$banan   -> n
ana$ban   -> n
anana$b   -> b
banana$   -> $
na$bana   -> a
nana$ba   -> a

The BWT is annb$aa. It tends to put equal characters next to each other (nn, aa), which is why it helps compression tools like bzip2. It is also the heart of the FM-index used in genome search.

The sorted rotations are exactly the suffixes of s + "$" in sorted order, so you can build the BWT from a suffix array: the character before each suffix.

Python BWT from sorted rotations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Inverting the BWT

It seems the BWT loses information, yet the original text can be recovered. Let L be the BWT (the last column). The first column F is simply the sorted characters of L. Key fact: the k-th occurrence of a character in F corresponds to the k-th occurrence of the same character in L (the LF mapping). Follow it from the row that starts with $ and you read the text backward.

The simplest correct way: rebuild the table by repeatedly prepending the column and sorting (O(n^2 log n)). The efficient way uses LF mapping in O(n log n) or O(n).

Python Inverse BWT with the LF mapping

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The text must not contain the sentinel $. If it might, choose a character that does not occur, or work with byte values and a sentinel outside that range.

Complexity summary

Task Simple method Efficient method
Lyndon factorization O(n^2) by testing Duval, O(n)
Minimal rotation O(n^2) by enumerating two-pointer or Booth, O(n)
BWT sort rotations, O(n^2 log n) suffix array, O(n log n) or O(n)
Inverse BWT rebuild table, O(n^2 log n) LF mapping, O(n log n) or O(n)

Common mistakes: forgetting the sentinel in BWT (the inverse becomes ambiguous), mixing up equal strings (a Lyndon word is strictly smaller than its rotations), and returning the index of a non-minimal start when several indices tie (the code takes min(i, j), which is the first minimal start).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which of these strings is a Lyndon word?

    A Lyndon word is strictly smaller than all its proper rotations. abab equals its own rotation, ba has the smaller rotation ab, and aa equals its rotation. aabab is smaller than all of its rotations.
  2. 2. What does the Lyndon factorization of a string look like?

    By the Chen-Fox-Lyndon theorem, every string splits uniquely into Lyndon words w1 >= w2 >= ... >= wk.
  3. 3. What is the minimal rotation of 'bca'?

    The three rotations are bca, cab and abc, and abc is the smallest in dictionary order. acb is not a rotation of bca at all.
  4. 4. Why is a sentinel character needed in the BWT?

    Without a unique smallest end marker, different strings can share a BWT, and the inverse would not know which row is the original.

Summary

  • A Lyndon word is strictly smaller than all its rotations; every string factorizes uniquely into non-increasing Lyndon words, found by Duval's algorithm in O(n).
  • The minimal rotation is found in O(n) with two candidate start positions and a match length; it gives a canonical form for cyclic strings.
  • The BWT lists the last characters of the sorted rotations of s + "$"; it groups equal characters and helps compression.
  • Invert the BWT with the LF mapping: the k-th occurrence of a character in the first column matches the k-th occurrence in the last.

Next: String Compression and Encoding