THE FOLD / BOSS / THE FIREWALL / THE SUFFIX ARRAY
THE SUFFIX ARRAY
sort every suffix — index every substring in O(n) space
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A suffix array lists the starting positions of all suffixes of a string, sorted lexicographically. For ‘banana’ the suffixes sort to a < ana < anana < banana < na < nana, giving indices [5, 3, 1, 0, 4, 2].
Paired with the LCP array (longest common prefix of adjacent suffixes), it answers ‘does pattern P occur?’ by binary search in O(m log n), finds the longest repeated substring, and does much of what a suffix tree does in a fraction of the memory. The doubling method sorts by 1-, 2-, 4-, … character prefixes.
LIT verified live: over 300 strings, the doubling-built suffix array matches a brute lexicographic sort of the suffixes, and the LCP array is correct (window.__suffixarray). FIG no framing; exact.
Paired with the LCP array (longest common prefix of adjacent suffixes), it answers ‘does pattern P occur?’ by binary search in O(m log n), finds the longest repeated substring, and does much of what a suffix tree does in a fraction of the memory. The doubling method sorts by 1-, 2-, 4-, … character prefixes.
LIT verified live: over 300 strings, the doubling-built suffix array matches a brute lexicographic sort of the suffixes, and the LCP array is correct (window.__suffixarray). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-firewall — the pattern-matching guard, now with an index. A suffix array lets the firewall answer ‘is this substring present?’ in log time. AVAN (AI) built the instrument: the prefix-doubling sort, the LCP construction, the brute cross-check, the binary-search lookup.
Credit as content: Udi Manber & Gene Myers (1990), who introduced suffix arrays as a compact alternative to suffix trees. The weave: David names the firewall; I sort the suffixes by doubling prefixes, build the LCP array, and confirm the order matches a direct suffix sort.
Credit as content: Udi Manber & Gene Myers (1990), who introduced suffix arrays as a compact alternative to suffix trees. The weave: David names the firewall; I sort the suffixes by doubling prefixes, build the LCP array, and confirm the order matches a direct suffix sort.
3 ONE DIMENSION
The suffixes of ‘banana’ listed and sorted: a, ana, anana, banana, na, nana — their starting indices form the suffix array. Adjacent suffixes share a prefix; its length is the LCP.
4 TWO DIMENSIONS · INTERACTIVE
Type a string; its suffix array and LCP array are built. Search a pattern by binary search over the sorted suffixes; the array is checked against a brute suffix sort.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the n sorted suffixes, a searchable index of the string.
AVAN’s addition (the inverse-companion): the array is a compressed index of every substring. Because every substring is a prefix of some suffix, sorting the n suffixes implicitly organises all O(n²) substrings into a searchable structure using only O(n) space. The inverse of ‘store every substring’ is ‘sort every suffix.’ And the LCP array recovers the suffix tree’s branching structure from the flat array — so a linear list holds a tree’s information. Magenta is the O(n²) substrings never explicitly stored; green is the n sorted suffixes that index them all. A whole substring universe folded into one sorted list — the suffix tree, flattened.
LIT Genuine suffix array (Manber & Myers 1990). Verified live: the prefix-doubling construction matches a brute lexicographic sort of all suffixes for 300 random strings, and the Kasai LCP array equals directly-computed longest common prefixes of adjacent suffixes (window.__suffixarray.matchesBrute && .lcpCorrect); banana -> 5,3,1,0,4,2.
FIG No framing: the doubling sort, the LCP construction, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — every substring is a prefix of some suffix, so sorting the n suffixes indexes all O(n^2) substrings in O(n) space, and the LCP array recovers the suffix tree's branching from the flat array; magenta is the uncomputed substrings, green the sorted suffixes. Ties to the-oracle-of-echoes and the-block-sort.
FIG No framing: the doubling sort, the LCP construction, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — every substring is a prefix of some suffix, so sorting the n suffixes indexes all O(n^2) substrings in O(n) space, and the LCP array recovers the suffix tree's branching from the flat array; magenta is the uncomputed substrings, green the sorted suffixes. Ties to the-oracle-of-echoes and the-block-sort.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE FIREWALL · David Lee Wise (ROOT0), with AVAN