## 3 SAIS-BsDiff Algorithm
In addition, the larger the memory of the upgraded file, the faster the upgrade speed of the proposed method. Taking a string of \"GTCCCGATGTCATGTCAGGAS\" as an example, the general linear time/space lexicographical derivation method [23] was compared with the SAIS algorithm to verify the optimization effect. A string \(S=t_{0}t_{1}\ldots t_{n-1}\) is defined as an array index with subscripts \(\{0\ldots n-1\}\) that defines the end of the string to end with the smallest dictionary character '$' symbol. To store the suffix, \(\mathrm{Suff}(S,\mathrm{i})\) is used to represent suffixes in S starting with S[i] and ending with the sentinel character '$'. SA represents the suffix array of the string S. All the suffix arrays in S are sorted in lexicographical order from smallest to largest. SA[i] represents position j of the suffix \((S,\mathrm{j})\) of the \(i\)th name in the original string S. That is, for SA[i] = j, the suffix \((S,\mathrm{j})\) ranks I in the SA. Three suffix types are defined in the SA array: S-type, L-type, and LMS-type [24]. Table 1 shows the determination of string types using \"*\" to represent LMS characters. **Theorem 1**. : _For two suffixes with the same initial letter, the lexicographical order of the S-type suffix is greater than that of the L-type suffix._  
Proof. : Assume that the suffixes of S-type and L-type begin with the same character c. \(S_{i}=c^{k}c_{1}a\) and \(T_{j}=c^{l}c_{2}\beta\), \(k\)\(>\) 0, \(l\)\(>\) 0, \(\alpha\), and \(\beta\) are strings. Assume that \(c_{1}>c\). If \(c_{2}<c\), \(c_{l}\) should be compared with \(c\). \(c_{1}>c\Rightarrow S_{j}\prec S_{i}\) (for strings \(S_{j}\) and \(S_{i}\), we use \(S_{j}\prec S_{i}\) to denote that \(S_{j}\) is lexicographically less than \(S_{i}\)). If \(k>l\), \(c_{2}\) should be compared with \(c\): \(c>c_{2}\Rightarrow S_{j}\prec S_{i}\). If \(k=l\), \(c_{1}\) should be compared with \(c_{2}\); if \(c_{1}>c\) and \(c>c_{2}\), then \(c_{1}>c_{2}\Rightarrow S_{j}\prec S_{i}\) is deduced. \(\square\)  
**Corollary 1**. : _If SA is divided into buckets alphabetically, the lexicographical order of the S suffix is larger than that of the L suffix in the same bucket, and S1 has the same lexicographical order as S._  
To achieve a linear time complexity and high execution efficiency, the input characters must first be preprocessed to shorten the length of the string to be processed. The existing linear sorting method for the suffix array replaces the entire array S-suffix S sort with the S-type suffix and compares it with all the suffixes in the bucket each time. The algorithm for deriving the lexicographical order in ordinary linear time/space can be divided into the following steps:  
Step 1: Assign the input character to the S array and determine the character type. According to the aforementioned theorem, find all S-suffixes in the string, sort them from smallest to largest, and replace them in order in all substring positions (I). Record the order of the SA sorted by S1, where S1 = {0, 16, 11, 6, 2, 13, 8}, as shown in Figure 5. Create different buckets according to the suffix array first letter, including $', A', C', G', and T' buckets, and place the new string S1 at the end of the corresponding bucket in sequence. \begin{table}
\begin{tabular}{l c c c c c c c c c c c c c c c c c c c c c} \hline \hline
**i** & **0** & **1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** & **9** & **10** & **11** & **12** & **13** & **14** & **15** & **16** & **17** & **18** & **19** & **20** \\ \hline S[i] & G & T & C & C & C & G & A & T & G & T & C Step 2: Find the heads of each L bucket in the SA and scan the SA from beginning to end. For each item SA[i], if S[SA[i] \(-\) 1] is of the L-type, place SA[i] \(-\) 1 to S[SA[i] \(-\) 1 in the current head of the L bucket and move it one bit backward until the scan is complete. Scan the SA from beginning to end. For each item SA[I], if S[SA[i] \(-\) 1] is of type S, place SA[i] \(-\) 1 to S[SA[i] \(-\) 1 in the current tail of the S bucket and move it forward by one bit.