## 5 Binary Tree Structure Compression
#### Context Mixing Method  
The shortcoming of methods that use contexts to predict the next symbol (DMC, PPM, and CTW) is that the context must be coherent. The best symbol prediction for images is adjacent horizontal and vertical pixels, but they do not form a coherent context. The previously mentioned methods do not provide a mechanism for combining statistics from contexts. _Context mixing method_ combines predictions from a large number of independent models using weighted averaging [52]. The input data are represented as a stream of 1 s and 0 s. For each bit, each model independently provides two characters \(n_{0},n_{1}\geq 0\), which can be used as the probability that the next symbol will be 0 or 1. Considering these two numbers together, they are the model's assertion that the next bit will be 0 with probability \(n_{0}/n\) or 1 with probability \(n_{1}/n\), where \(n=n_{0}+n_{1}\) is the model's relative confidence in this prediction. Since the models are independent of each other, the confidence is only meaningful when comparing two predictions of the same model. The models are combined by a weighted summation of \(n_{0}\) and \(n_{0}\) over all models as follows:  
\[S_{0} =\epsilon+\sum w_{i}n_{0i}\quad\textit{evidence for }0 \tag{15}\] \[S_{1} =\epsilon+\sum w_{i}n_{1i}\quad\textit{evidence for }1\] \[S =S_{0}+S_{1}\quad\textit{total evidence}\] \[p_{0} =\frac{S_{0}}{S}\quad\textit{probability that the next bit is }0\] \[p_{1} =\frac{S_{1}}{S}\quad\textit{probability that the next bit is }1,\]  
where \(w_{i}\geq 0\) is the weight of the \(i\)'th model, \(n_{0i}\) and \(n_{1i}\) are outputs \(n_{0}\) i \(n_{1}\) of the \(i\)-th model, and \(\epsilon>0\) is a constant that guarantees \(S_{0},S_{1}>0\) i \(p_{0},p_{1}\in(0,1)\). After coding each bit, the weights are adjusted in favor of the models that correctly predict that bit. Let \(x\) be the first bit to be encoded in the sequence. The cost of the optimal \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Compression Method**} & \multirow{2}{*}{**None**} & \multicolumn{3}{c}{**Data Stream Transformation**} & \\  & & **Delta** & **CTW** & **BWT** & **PPM** & **DMC** \\ \hline Huffman coding & 4.75 & 6.12 & 4.22 & 4.68 & 4.66 & / \\ Arithmetic coding & 5.02 & 7.10 & 4.08 & 5.11 & 4.21 & 3.80 \\ Range coding & 5.33 & 7.24 & 3.99 & 5.39 & 4.13 & 3.84 \\ LZ77 & 4.68 & 5.88 & / & 4.65 & 4.34 & / \\ LZ78 & 4.89 & 6.01 & / & 4.93 & 4.48 & / \\ LZW & 4.76 & 5.94 & / & 4.87 & 4.42 & / \\ \hline \hline \end{tabular}
\end{table} 
Table 8: _AAE_ for possible combinations of data transformation and compression at binary tree structure coding. encoding of \(x\) is \(\log_{2}1/p_{x}\). From the partial derivative of the encoding cost with respect to each \(w_{i}\) in (15) with the constraint that the weights must be non-negative, we obtain the weight adjustment term:  
\[w_{i}\leftarrow max\bigg{[}0,w_{i}+\frac{(x-p_{1})(Sn_{1i}-S_{1}n_{i})}{S_{0}S _{1}}\bigg{]}, \tag{16}\]  
where \(n_{i}=n_{0i}+n_{1i}\). The term \((x-p_{1})\) is the prediction error. The weights tend to grow logarithmically because the term \(S_{0}S_{1}\) grows along with the weights. The predictions from Equation (15) are sent to arithmetic coder. If the input in the coder is \(x\) then the output from the coder is the length of \(x\) together with a number from a half-open interval \([p_{<x},p_{<x}+p(x))\) where \(p_{<x}\) is a probability that a random picked string is lexicographically smaller than \(x\). Within the interval, there is a number with a base \(B\) encoding that has maximum \(1+\log_{b}1/p(x)\) digits [42]. When \(p(x)\) is expressed as a product of conditional probabilities  
\[p(x_{1},x_{2},\ldots,x_{n})=\prod_{i}p(x_{i}|x_{1},x_{2},\ldots,x_{i-1})\]  
and only \(1\) s and \(0\) s are used.