## 4 Algorithm II: Improved Algorithm
### Improved Sorting - Using Shannon-Fano-Elias Codes
If necessary, we can pad \(T\) with a maximum of \((m-1)\) '\(\$\)' symbols, to form a valid \(m\)-block at the end of the sequence. We compute the quantity: \(P_{i}^{\prime}=\prod_{k=i}^{i+m-1}p_{k}\). Recall that \(t_{i}=T[i]\in\Sigma\), and \(\sum_{j=0}^{|\Sigma|-1}Pr\{\sigma_{j}\}=1\). For a given sequence \(T\), we should have: \(\sum_{i=0}^{n-1}P_{i}^{\prime}=1\). However, since \(T\) may not contain all the possible \(m-\)length blocks in \(\Sigma^{m}\), we need to normalize the product of probabilities to form a probability space:  
\[P_{i}=\frac{P_{i}^{\prime}}{\sum_{i=0}^{n-1}P_{i}^{\prime}} \tag{1}\]  
To determine the code for \(Q_{i}\), we then use the cumulative distribution function (cdf) for the \(P_{i}\)'s, and determine the corresponding position for each \(P_{i}\) in this cdf. Essentially, this is equivalent to dividing a number line in the range [0 1], such that each \(Q_{i}\) is assigned a range proportional to its probability, \(P_{i}\). See Figure 4. The total number of divisions will be equal to the number of unique \(m\)-length blocks in \(T\). The problem then is to determine the specific interval on this number line that corresponds to \(Q_{i}\), and to choose a tag \(q_{i}\) to represent \(Q_{i}\). We use the following assignment procedure to compute the tag, \(q_{i}\). First we determine the interval for the tag, based on which we compute the tag. Define the cumulative distribution function for the symbols in \(\Sigma=\{\sigma_{0},\sigma_{1},\ldots,\sigma_{|\Sigma|-1}\}\): \(F_{x}(\sigma_{j})=\sum_{v=0}^{j}Pr\{\sigma_{v}\}\). The symbol probabilities, \(Pr\{\sigma_{v}\}\)'s are simply obtained based on the \(p_{i}\)'s. For each symbol \(\sigma_{k}\) in \(\Sigma\), we have an open interval in the cdf: \([F_{x}(\sigma_{k-1})\quad F_{x}(\sigma_{k}))\). Now, given the sequence \(Q_{i}=s_{1}s_{2}\ldots s_{k}\ldots s_{m}\), \(s_{i}\in\Sigma\), the procedure steps through the sequence. At each step \(k,k=1,2,\ldots,m\) along the sequence, we can compute \(U(k)\) and \(L(k)\), the respective current upper and lower ranges for the tag using the following relations:  
Figure 4: Code assignment by successive partitioning of a number line. \[L(0)=0;U(0)=1\] **for**\(k=1\) to \(m\) : \[U(k)=L(k-1)+[U(k-1)-L(k-1)]F_{x}(s_{k})\] \[L(k)=L(k-1)+[U(k-1)-L(k-1)]F_{x}(s_{k}-1)\]  
The procedure stops at \(k=m\), and the values of \(U(k)\) and \(L(k)\) at this final step will be the range of the tag, \(q_{i}\). We can choose the tag \(q_{i}\) as any number in the range: \(L(m)\leq q_{i}<U(m)\). Thus we chose \(q_{i}\) as the mid point of the range at the final step: \(q_{i}=\frac{U(m)+L(m)}{2}\). Figure 5(a) shows an example run of this procedure for a short sequence: \(Q_{i}=acabd\) with a simple alphabet, \(\Sigma=\{a,b,c,d\}\), and where each symbol has an equal probability \(p_{i}=\frac{1}{4}\). This gives \(q_{i}=\frac{271}{2048}\). Figure 5: Code assignment procedure, using an example sequence. The vertical line represents the current state of the number line. The current interval at each step in the procedure is shown with a darker shade. The symbol considered at each step is listed under their respective number lines (a) Using the sequence \(Q_{i}=acabd\). (b) Evolution of code assignment procedure, after removing the first symbol (in previous sequence _acabd_), and bringing in a new symbol \(a\) to form a new sequence: \(Q_{i+1}=cabda\). **Lemma 2:** The tag assignment procedure results in a tag \(q_{i}\) that is unique to \(Q_{i}\). _Proof._ The procedure described can be seen as an extension of the Shanon-Fano-Elias coding procedure used in source coding and information theory [32]. Each tag \(q_{i}\) is analogous to an arithmetic coding sequence of the given \(m\)-length block, \(Q_{i}\). The open interval defined by \([(L(m)\ \ U(m))\) for each \(m\)-length sequence is unique to the sequence. To see this uniqueness, we notice that the final number line at step \(m\) represents the cdf for all \(m\)-length blocks that appeared in the original sequence \(T\).