## 3 SAIS-BsDiff Algorithm  
In this section, we introduce the improvements based on the BsDiff algorithm. The suffix array induced sorting (SAIS) is a suffix array (SA) construction algorithm that consumes linear time and memory [21]. It uses an LMS substring to replace the original string to be processed and processes the order of the LMS substring through induced sorting, which has good suffix array sorting performance. The SAIS algorithm can be used to optimize and improve the low efficiency of suffix array sorting in the BsDiff algorithm and reduce the time complexity to O(n). A fusion algorithm based on the SAIS algorithm and the BsDiff method, called the SAIS-BsDiff algorithm, is proposed to improve the efficiency of differential compression BsDiff. The calculation process for the SAIS-BsDiff algorithm is shown in Figure 4. This optimization scheme can reduce the time consumed in the OTA upgrade process and the waste of the communication network in the upgrade process. The input of the proposed algorithm is a mirror image of the old version, and the output is a Diff (difference) file. The calculation process of the proposed SAIS-Bisdiff difference algorithm is as follows: first, the LMS substring is created, and the suffix array is built through _is_lms_char_. The LMS substring can replace the original suffix array by _equal_substring_, induced by _induced_sort_ to the LMS string, and SAIS finally obtains a simple string summary. The generated string summary replaces the original suffix array as input  
Figure 3: Format of patch file. for the BsDiff algorithm. The _search_ function searches for the data segment matched by the old and new files by traversing the entire file; it finds the maximum matched data segment length using _matchlen_, which is sent to _BsDiff_internal_. _BsDiff_internal_ processes data segments, such as calculating the approximate and mismatched regions of a file, and processes data segments in different regions. The processed data are copied using the writeData function. Finally, the data are collated using the BsDiff function, and the output of the algorithm is realized through BZZP packet compression. That is, the output is a Diff file. At this point, the difference algorithm is completed. Then, when the assignment is downloaded to the networked terminal, the restore operation is performed. That is, the internal computing unit of the networked terminal performs the corresponding calculation operation, thereby restoring the difference file to the new version file. In this case, the input of the restoration algorithm is the Diff file and the old version file, and the output is the upgrade file. The output of multiple files can be based on the file number information to achieve multiple package splicing in the controller. This splitting and splicing behavior realizes the whole process of the OTA upgrade. The SAIS lexicographic generation framework used to optimize BsDiff is presented in Algorithm 1 SAIS lexicographical order generation framework. ```
Input: Assign the input character to S[i] Output: Get the suffix array SA 1: t = bool[], Scan the string S\({}_{\text{t}}\) to determine the type of each suffix. 2: P = int[], Scan the array t for all LMS substrings. 3: bucket = int[], Bucket sort all LMS substrings. 4: S1 = int[], Scan t\({}_{\text{t}}\) to determine all LMS substrings and induced sort, then generate a new stringS1. 5: Is every character in S1 the same? If the same, repeat steps 1-5, then recursive calculation SA1 = SAIS(S1). SA1 was used for induction sequencing to obtain SA. calculating SA1 directly. 6: End of the algorithm
```  
**Algorithm 1** SAIS ()  
In the calculation of the suffix array of the SAIS algorithm, the size of the recursive suffix array is halved each time [22]. The time complexity of the optimized BsDiff algorithm for generating the lexicographical order is T(n) = T(n/2) + O(n) \(\approx\) O(n), which is better than  
Figure 4: SAIS–BsDiff Algorithm. that of the BsDiff algorithm in terms of speed, which is O(nlogn).