Duval Lyndon Factorization

Theory

A string is called a Lyndon word if it is strictly lexicographically smaller than all of its nontrivial cyclic rotations. Equivalently, a nonempty Lyndon word is strictly smaller than every proper suffix of itself. Any string can be uniquely factored into a sequence of Lyndon words s = w_1 w_2 ... w_k such that each w_i is a Lyndon word and the sequence is nonincreasing lexicographically: w_1 >= w_2 >= ... >= w_k. This unique decomposition is known as the Lyndon factorization of the string.

Duval's algorithm finds this factorization in linear time O(n) and constant extra space O(1). It maintains three pointers: i, which marks the start of the current factor being processed; j, which scans ahead; and k, which tracks the period of the current Lyndon prefix. By comparing characters s[k] and s[j], the algorithm determines whether the current prefix can be extended as a Lyndon word or if the accumulated prefix must be factored out.

Worked Example

Let's consider the Lyndon factorization of the string "banana". Duval's algorithm proceeds as follows:

To see this in action, follow these steps:

1. Select Banana from the Text native select control.
2. Observe the resulting expected factors and lengths in the output fields below. This matches our trace expected results.
3. Start with i = 0 (character 'b'). The first Lyndon word is found to be "b" because 'b' > 'a'.
4. Next, i = 1 (character 'a'). The algorithm scans forward and finds the sequence "an" which is a Lyndon word, but since the next character 'a' is less than 'n', it cannot extend. The word is "an".
5. Next, i = 3 (character 'a'). It scans again and finds another "an".
6. Finally, i = 5 (character 'a'). A single character is always a Lyndon word.

The resulting factors are:

Expected factors: "b", "an", "an", "a" Factor count: 4 Longest factor: 2 Order: Nonincreasing

Experiment

You can interact with the algorithm using the Duval Lyndon Factorization module.

1. Select Mixed from the Text native select control.
2. Observe the visual trace showing the linear-time Duval i/j/k comparisons as it factors the text into "abac", "ab", and "a".
3. Check the resulting output cards to see the correct Factors, Factor count, and Longest factor length.

Limitations

Duval's algorithm assumes a fully comparable alphabet and string sequence. It is designed for simple byte or character arrays. Handling complex Unicode grapheme clusters or specialized custom alphabets requires ensuring the lexicographical comparison precisely matches the domain's rules.

References

The following resources provide a comprehensive mathematical background on Lyndon words, the proof of unique factorization, and a deeper dive into Duval's linear-time strategy. These materials are essential for understanding the theoretical underpinnings of the algorithm and its applications in string processing and combinatorics.

• CP-Algorithms: Lyndon Factorization
• Duval, J. P. (1983). Factorizing words over an ordered alphabet. Journal of Algorithms.