This chapter introduces an in-place suffix sorting algorithm with linear time complexity[^in-place-sa-sort] (Optimal In-Place Suffix Sorting).
Warning
This chapter is only recommended for reading if you are extremely familiar with SA-IS[nzc09a][sa-is-intro].
Global Settings
Target string \(\texttt{Pat}\), suffix array \(\texttt{SA}\), string indices start from 0, the ending character is a sentinel, which can be set to 0.
Suffix Sorting on Integer Alphabet
In fact, this part can be seen as an in-place version of the SA-IS algorithm.
Since it is the algorithm with the clearest details and simplest implementation in the original text, and also the foundation for understanding subsequent algorithms, it is the focus of this article.
The principle of in-place transformation is to use the renamed \(\texttt{Pat}\) to replace the S and L buckets, and use an additional \(O(n)\) operations to replace the type buckets.
Renaming the Target String Pat
Simply put, we rename \(\texttt{Pat}\) without changing the relative order of suffix sizes, using the renamed \(\texttt{Pat}\) to replace the original S and L buckets to indicate bucket heads or tails.
The renaming method replaces S-type characters in \(\texttt{Pat}\) with the bucket tail index and L-type characters with the bucket head index.
As shown in the following figure:
\[
\begin{aligned}
\texttt{Index}:\qquad&\texttt{ 0 1 2 3 4 5 6 7 8 9 10 11 12} \\
\texttt{Pat}:\qquad&\texttt{ 2 1 1 3 3 1 1 3 3 1 2 1 0} \\
\texttt{Type}:\qquad&\texttt{ L S S L L S S L L S L L S} \\
\texttt{Bucket}:\qquad&\texttt{(0)}\texttt{ }\texttt{(1}\texttt{ }\texttt{ }\texttt{ 1 }\texttt{ }\texttt{ 1 }\texttt{ }\texttt{ 1 }\texttt{ }\texttt{ 1 }\texttt{ }
\texttt{ 1) }\texttt{(2 }\texttt{ }\texttt{ 2) }\texttt{(3}\texttt{ }\texttt{ }\texttt{ 3 }\texttt{ }\texttt{ 3 }\texttt{ }\texttt{ 3)}
\end{aligned}
\]
The renamed \(\texttt{Pat'}\) (hereafter, the renamed \(\texttt{Pat'}\) is directly referred to as \(\texttt{Pat}\)):
Since within a bucket, L-type characters have smaller suffixes and serve as the bucket head, while S-type characters have larger suffixes and serve as the bucket tail, the relative order of suffix sizes is preserved.
Describe the specific steps of renaming:
As in SA-IS, count each character in \(\texttt{Pat}\) and compute its prefix sum (counting sort) to construct S/L buckets, except here \(\texttt{SA}\) is used to hold this prefix sum;
Scan each character of \(\texttt{Pat}\) from tail to head, so that by recording the type of the previous character, the type of each character can be determined dynamically, and then it is renamed according to the prefix sum.
Sorting LMS Characters
The key here is the use of an internal counter technique.
Initialization
Initially, set each entry of \(\texttt{SA}\) to E (EMPTY).
Scan \(\texttt{Pat}\) from tail to head. If an LMS character \(\texttt{Pat[i]}\) is found, set the marker in \(\texttt{SA[Pat[i]]}\):
If \(\texttt{SA[Pat[i]]}\) is E, set it to U (UNIQUE);
If \(\texttt{SA[Pat[i]]}\) is U, set it to M (MULTIPLE);
Scan \(\texttt{Pat}\) from tail to head. For each LMS character \(\texttt{Pat[i]}\), classify according to the symbol in \(\texttt{SA[Pat[i]]}\):
U: Directly set \(\texttt{SA[Pat[i]] = i}\)
M: Means there are at least two LMS characters in the bucket.
If there are at least three LMS characters in the bucket:
Use the second-to-last position in the bucket as a temporary counter, indicating the number of LMS characters already filled in the bucket (the last position in the bucket is marked M).
Insert the new LMS character starting from the third-to-last position, incrementing the temporary counter by 1.
If the bucket is found to be full, shift all elements from the bucket head to the third-to-last position two positions to the right, then insert the new element into the second position of the bucket (the first position of the bucket is filled with E).
If there are exactly two LMS characters in the bucket, obviously no counter is needed; simply insert from right to left in order.
Normal value:
123
According to our previous discussion, this means $\texttt{i}$ is the position of the last LMS character to be inserted in the bucket,
simply scan from the bucket head to the left, find the first position marked E, and set it to $\texttt{i}$.
Finally, scan \(\texttt{SA}\) from tail to head to clear any residual special symbol M (the bucket is not full, so M and the counter are not overwritten).
The method is to shift the LMS characters in the bucket two positions to the right as described above, filling the left positions with E.
In this phase, since each bucket only needs to be moved and scanned once, the time complexity is \(O(n)\).
Induced Sorting of LMS Substrings
Induced Sorting of LMS Prefixes
Induced sorting of LMS prefixes is performed. As in SA-IS, this part is exactly the same as the subsequent induced sorting of suffixes (using the same function), so it is skipped here.
\[
\begin{aligned}
\texttt{Index}:\qquad&\texttt{ 0 1 2 3 4 5 6 7 8 9 10 11 12} \\
\texttt{SA}:\qquad&\texttt{ }\texttt{E }\texttt{ }\texttt{ E }\texttt{ }\texttt{ E }\texttt{ }\texttt{ E }\texttt{ }\texttt{ E }\texttt{ }\texttt{ E }\texttt{ }\texttt{ E }\texttt{ }\texttt{ E }\texttt{ }\texttt{ E }\texttt{ }{\underline{\color{red}{\texttt{12}}}}\texttt{ }\texttt{ }\texttt{ }{\underline{\color{red}{\texttt{1}}}}\texttt{ }\texttt{ }\texttt{ }{\underline{\color{red}{\texttt{5}}}}\texttt{ }\texttt{ }\texttt{ }{\underline{\color{red}{\texttt{9}}}}
\end{aligned}
\]
Constructing the Reduced Sub-target String Pat1
Scan the LMS substrings at the tail of \(\texttt{SA}\) from left to right, determine their size relations ("rename"), and store the renamed value of \(\texttt{SA[i]}\) in \(\texttt{SA}\left[\left\lfloor\frac{\texttt{SA}[i]}{2} \right\rfloor\right]\).
Since LMS characters are not adjacent, there is no conflict. This places the renamed values in the original order of the substrings they represent in \(\texttt{Pat}\):
Solving Pat1 Recursively to Complete Sorting of LMS Suffixes
As in SA-IS, recursively solve the suffix sorting of the reduced \(\texttt{Pat1}\) at the head of \(\texttt{SA}\), storing the result at the tail of \(\texttt{SA}\):
Move \(\texttt{SA1}\) from the tail of \(\texttt{SA}\) to the head of \(\texttt{SA}\), then scan \(\texttt{Pat}\) from tail to head again, placing its LMS characters in the order they appear in \(\texttt{Pat}\) at the tail of \(\texttt{SA}\):
According to the "lookup table" at the tail of \(\texttt{SA}\), restore the \(\texttt{SA}\) at the head of \(\texttt{SA1}\) to the index positions of the corresponding LMS suffixes in \(\texttt{Pat}\):
Scan SA from left to right. Similar to sorting LMS characters, the complexity lies in determining the type of \(\texttt{suf[SA[i] - 1]}\), requiring case analysis (see code for details):
\[
\begin{aligned}
\texttt{Index}:\qquad&\texttt{ }\texttt{ 0 1 2 3 4 5 6 7 8 9 10 11 12} \\
\texttt{SA}:\qquad&\texttt{(}{\overrightarrow{\color{red}{\texttt{12}}}\texttt{)}\texttt{(}{\underline{\color{red}{\texttt{11}}}}}\texttt{)}\texttt{ (E E 1 5 9) (M E) (M E E E)}\\
\texttt{SA}:\qquad&\texttt{(}\texttt{12}\texttt{)}\texttt{(}{\overrightarrow{\color{red}{\texttt{11}}}}\texttt{)}\texttt{ (E E 1 5 9)}\texttt{(}{\underline{\color{red}{\texttt{10}}}}\texttt{ }\texttt{ }\texttt{ E)}\texttt{ (M E E E)}\\
\texttt{SA}:\qquad&\texttt{(12)(11)}\texttt{ (E E }\texttt{ }\texttt{ } {\overrightarrow{\color{red}{\texttt{1}}}}\texttt{ }\texttt{ 5 9)}\texttt{(10 }\texttt{ }\texttt{ }{\underline{\color{red}{\texttt{0}}}}\texttt{)}\texttt{ (M E E E)}\\
\texttt{SA}:\qquad&\texttt{(12)(11)}\texttt{ (E E 1 }\texttt{ }\texttt{ } {\overrightarrow{\color{red}{\texttt{5}}}}\texttt{ }\texttt{ 9)}\texttt{(10 0)}\texttt{ (}{\color{red}{\texttt{M 1}}}\texttt{ }\texttt{ }\texttt{ }{\underline{\color{red}{\texttt{4}}}}\texttt{ }\texttt{ }\texttt{ E)}\\
\texttt{SA}:\qquad&\texttt{(12)(11)}\texttt{ (E E 1 5}\texttt{ }\texttt{ } {\overrightarrow{\color{red}{\texttt{9}}}}\texttt{)}\texttt{(10 0)}\texttt{ (}{\color{red}{\texttt{M 2}}}\texttt{ }\texttt{ }\texttt{ 4 }\texttt{ }\texttt{ }{\underline{\color{red}{\texttt{8}}}}\texttt{)}\\
\texttt{SA}:\qquad&\texttt{(12)(11)}\texttt{ (E E 1 5 9)(10 0)}\texttt{ (}{\overrightarrow{\color{red}{\texttt{4}}}}\texttt{ }\texttt{ 8 }\texttt{ }\texttt{ }{\underline{\color{red}{\texttt{3}}}}\texttt{ }\texttt{ }\texttt{ E}\texttt{)}\\
\texttt{SA}:\qquad&\texttt{(12)(11)}\texttt{ (E E 1 5 9)(10 0)}\texttt{ (4 }\texttt{ }\texttt{ }{\overrightarrow{\color{red}{\texttt{8}}}}\texttt{ }\texttt{ 3 }\texttt{ }\texttt{ }{\underline{\color{red}{\texttt{7}}}}\texttt{)}
\end{aligned}
\]
Different from SA-IS, after induced sorting of one type of character, LMS characters need to be cleared to avoid affecting subsequent in-place induced sorting:
As for inducing S suffixes from L suffixes, it is completely symmetric to inducing L suffixes from LMS suffixes, so no further introduction is given here.
At this point, induced sorting is complete.
Implementation
There is no significant difference in time performance compared to SA-IS, and space usage is reduced to less than one-third of the original (code size doubles), living up to the title of the original Optimal In-Place Suffix Sorting[^in-place-sa-sort].
Reference Code
```rust
use std::cmp::max;
use std::cmp::Ordering;
use std::slice::from_raw_parts_mut;
fn lms_str_cmp(l1: &[E], l2: &[E]) -> Ordering {
for (x, y) in l1.iter().zip(l2.iter()) {
let cmp_res = x.cmp(&y);
1234
if cmp_res != Ordering::Equal { return cmp_res; }
}
Ordering::Equal
}
[inline]
fn pat_char_type(cur: usize, prev: usize, last_scanned_type: bool) -> bool {
if cur < prev || cur == prev && last_scanned_type == STYPE { STYPE }
else { LTYPE }
}
fn rename_pat(pat: &mut [usize], sa: &mut [usize]) {
let patlastpos = pat.len() - 1;
// Fill all with bucket head
//sa.fill(0);
for i in 0..sa.len() { sa[i] = 0 }
1 2 3 4 5 6 7 8 9101112131415161718192021
for i in 0..pat.len() { sa[pat[i]] += 1 }
for i in 1..sa.len() { sa[i] += sa[i - 1] }
for i in 0..pat.len() - 1 {
pat[i] = sa[pat[i]] - 1;
};
// Paint L-suffix as bucket head
//sa.fill(0);
for i in 0..sa.len() { sa[i] = 0 }
for i in 0..pat.len() { sa[pat[i]] += 1 }
let mut last_scanned_type = STYPE;
pat[patlastpos] = 0;
for i in (0..pat.len() - 1).rev() {
if pat_char_type(pat[i], pat[i + 1], last_scanned_type) == STYPE {
last_scanned_type = STYPE;
} else {
pat[i] -= sa[pat[i]] - 1;
last_scanned_type = LTYPE;
}
}
}
fn sort_lms_char(pat: &mut [usize], sa: &mut [usize]) -> usize {
//sa.fill(EMPTY);
for i in 0..sa.len() { sa[i] = EMPTY }
// step 2
let pat_last_pos = pat.len() - 1;
let mut lms_cnt = 0;
let mut i = pat_last_pos;
let mut bucket_tail_ptr = pat_last_pos + 1; // for renamed bucket ver
let mut bucket = EMPTY; // Can be omitted, but convenient for coding
let mut num = 0; // S type number of bucket
while i > 0 {
if pat[sa[i]] != bucket { // reach new bucket
num = 0;
let mut l = 0;
while pat[sa[i - l]] == pat[sa[i]] { // Scan bucket to count S characters, by definition loop terminates when l=i
let pat_i = sa[i - l]; // l < i, i.e., i - l > 0, 0 <= pat_i < patlen - 1
if pat[pat_i] < pat[pat_i + 1] {
let mut k = pat_i;
while k > 0 && pat[k - 1] == pat[pat_i] { k -= 1 }
num += pat_i - k + 1;
} else {
break; // Bucket has no S characters, stop scanning
}
l += 1;
}
bucket_tail_ptr = i;
bucket = pat[sa[bucket_tail_ptr]];
}
if num > 0
&& i > bucket_tail_ptr - num
&& sa[i] > 0
&& pat[sa[i]] < pat[sa[i] - 1] {
sa[pat_last_pos - lms_cnt] = sa[i];
lms_cnt += 1;
}
i -= 1;
}
sa[pat_last_pos - lms_cnt ] = sa[i]; // i = 0
lms_cnt += 1;
//sa[0..pat_last_pos - lms_cnt + 1].fill(EMPTY);
for i in 0..pat_last_pos - lms_cnt + 1 { sa[i] = EMPTY }
let mut prev_lms_str_len = 1;
let mut rank = 0;
sa[(patlen - 1) / 2] = rank;
let mut has_duplicated_char = false;
for i in patlen - lms_cnt + 1..patlen { // Start from the character after sentinel
let mut j = sa[i];
while pat[j] <= pat[j + 1] { j += 1 } // Find first L character to the right of suf(sa[i]), since sentinel LMS suffix is excluded, won't go out of bounds
let mut k = j;
while k + 1 < patlen && pat[k] >= pat[k + 1] { k += 1 } // Find first LMS character to the right of suf(sa[i])
let cur_lms_str_len = k + 1 - sa[i];
let cmp_res = lms_str_cmp(&pat[sa[i]..sa[i] + cur_lms_str_len], &pat[sa[i - 1]..sa[i - 1] + prev_lms_str_len]);
if cmp_res != Ordering::Equal {
rank += 1
}
if rank == sa[sa[i - 1] / 2] {
has_duplicated_char = true;
}
let rank_index = sa[i] / 2;
sa[rank_index] = rank; // Integer division
prev_lms_str_len = cur_lms_str_len;
}
// move to head of sa
let mut j = 0;
for i in 0..patlen - lms_cnt {
if sa[i] != EMPTY {
sa[j] = sa[i];
if i > j {
sa[i] = EMPTY;
}
j += 1;
}
}
//sa[lms_cnt..patlen].fill(EMPTY);
for i in lms_cnt..patlen { sa[i] = EMPTY }
has_duplicated_char
}
fn sort_lms_suf(pat: &mut [usize], sa: &mut [usize], lms_cnt: usize, has_duplicated_char: bool) {
// solve T1 recursively
let patlen = pat.len();
let salen = sa.len();
unsafe {
let sa_ptr = sa.as_mut_ptr();
let mut pat1 = from_raw_parts_mut(sa_ptr, lms_cnt);
let mut sa1 = from_raw_parts_mut(sa_ptr.offset((patlen - lms_cnt) as isize),