## 4 Algorithm II: Improved Algorithm
### Improved Sorting - Using Shannon-Fano-Elias Codes
Denote this cdf for the \(m\)-blocks as \(F_{x}^{m}\). Given \(Q_{i}\), the \(i\)-th \(m\)-block in \(T\), the size of its interval is given by \((U(m)-L(m))=P_{i}\). Since all probabilities are positive, we see that \(F_{x}^{m}(Q_{i})\
eq F_{x}^{m}(Q_{j})\) whenever \(Q_{i}\
eq Q_{j}\). Therefore, \(F_{x}^{m}(Q_{i})\) determines \(Q_{i}\) uniquely. Thus, \(F_{x}^{m}(Q_{i})\) serves as a unique code for \(Q_{i}\). Choosing any number \(q_{i}\) within the upper and lower bounds for each \(Q_{i}\) define a unique tag for \(Q_{i}\). Thus the chosen tag defined by the midpoint of this interval is unique to \(Q_{i}\). \(\square\)  
**Lemma 3:** The tags generated by the assignment procedure are order preserving. _Proof._ Consider the ordering of the tags for different \(m\)-length blocks. Each step in the assignment procedure uses the same fixed order of the symbols on a number line, based on their order in \(\Sigma\). Thus, the position of the upper and lower bounds at each step depends on the previous symbols considered, and the position of the current symbol in the ordered list of symbols in \(\Sigma\). Therefore the \(q_{i}\)'s are ordered with respect to the lexicographic ordering of the \(Q_{i}\)'s: \(q_{i}<q_{j}\Leftrightarrow Q_{i}\prec Q_{j}\), and \(q_{i}=q_{j}\Leftrightarrow Q_{i}=Q_{j}\). \(\square\)  
**Lemma 4:** Given \(T=t_{0}t_{1}\ldots t_{n-1}\), all the required tags \(q_{i},\forall i\), can be computed in \(O(n)\) time. _Proof._ Suppose we have already determined \(P_{i}\) and \(q_{i}\) for the \(m\)-block \(Q_{i}\) as described above. For efficient processing, we can compute \(P_{i+1}\) and the tag \(q_{i+1}\) in the \([0\ 1]\) number line, using the previous values for \(P_{i}\) and \(q_{i}\). This is based on the fact that \(Q_{i}\) and \(Q_{i+1}\) are consecutive positions in \(T\) (In practice, we need only a fraction of the positions in \(T\), which will mean less time and space are required. But here we describe the procedure for the entire \(T\) since the complexity remains the same.). In particular, given \(Q_{i}=T[i\ldots i+m-1]\), and \(Q_{i+1}=T[i+1\ldots i+m]\). We compute \(P_{i+1}^{\prime}\) as:  
\[P_{i+1}^{\prime}=\frac{P_{i}^{\prime}.p_{i+m}}{p_{i}}\]  
Then, we compute \(P_{i+1}\) using Equation (1). Thus, all the required \(P_{i}\)'s can be computed in \(O(n+m)\) = \(O(n+\log n)=O(n)\) time. Similarly, given the tag \(q_{i}\) for \(Q_{i}\), and its upper and lower bounds \(U(m)\) and \(L(m)\), we can compute the new tag \(q_{i+1}\) for the incoming \(m\)-block, \(Q_{i+1}\) based on the structure of the assignment procedure used to compute \(q_{i}\), (see Figure 5(b)). We compute the new tag \(q_{i+1}\) by first computing it's upper and lower bounds. Denote the respective upper and lower bounds for \(q_{i}\) as: \(U^{i}(m),L^{i}(m)\). Similarly, we use \(U^{i+1}(m),L^{i+1}(m)\) for the respective bounds for \(q_{i+1}\). Let \(s=T[i]=Q_{i}[0]\) be the first symbol in \(Q_{i}\). Its probability is given by \(p_{i}\). Also, let \(s_{new}=T[i+m]\) be the new symbol that is shifted in. Its probability is given by \(p_{i+m}\), and we also know it's position in the cdf. We first compute the intermediate bounds at step \(k=m-1\) when using \(Q_{i+1}\), namely:  
\[U^{i+1}(m-1) =[U(m)-F_{x}(s)](\frac{1}{p_{i}})\] \[P_{i}=\frac{P_{i}^{\prime}}{\sum_{i=0}^{n-1}P_{i}^{\prime}} \tag{1}\]0Multiplying by \((\frac{1}{p_{i}})\) changes the probability space from the previous range of \([F_{x}(s-1)\ F_{x}(s))\) to \([0\ 1]\). After the computations, we can then perform the last step in the assignment procedure to determine the final range for the new tag:  
\[P_{i}=\frac{P_{i}^{\prime}}{\sum_{i=0}^{n-1}P_{i}^{\prime}} \tag{1}\]1 \[P_{i}=\frac{P_{i}^{\prime}}{\sum_{i=0}^{n-1}P_{i}^{\prime}} \tag{1}\]2  
The tag \(q_{i+1}\) is then computed as the average of the two bounds as before. The worst case time complexity of this procedure is in \(O(n+m+|\Sigma|)=O(n+\log n+|\Sigma|)\). The \(|\Sigma|\) component comes from the time needed to sort the unique symbols in \(T\) before computing the cdf.