# An Efficient Encoding Algorithm Using Local Path on Huffman Encoding Algorithm for Compression
## 2 Technical Background
### Arithmetic Coding Algorithm  
Arithmetic coding is one of the most used data compression methods in the literature that decreases coding redundancy, like Huffman coding [30]. It creates a code string that symbolizes fractional values between 0 and 1. The fundamental idea used in arithmetic coding is to divide the values from 0 to 1 according to the probability of the symbols in the message. When the symbol count is small and there are less differences in the probability of the characters, Huffman encoding loses its effectiveness, while arithmetic coding is more successful. In arithmetic coding, each series must be labeled with a unique identifier to separate a particular set of symbols from other symbols. This tag is usually defined as a number between 0 and 1 [31; 32; 33; 34; 35].  
For example, Table 4 presents the text 'xxyxxzzxxx' compressed using arithmetic coding, as seen in [36]. The text consists of three letters, \(A=\{x,\ y,z\}\), the alphabet. The probability distributions of this text are P(x) = 0.7, P(y) = 0.1, and P(z) = 0.2, as shown in Table 4.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Symbol** & **x** & **y** & **z** \\ \hline Frequency & 7 & 1 & 2 \\ \hline \hline \end{tabular}
\end{table}
Table 4: Frequencies of letters in ‘xxyxxzzxx’ text.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Symbol** & **t** & **s** & **i** & – & **h** & **e** \\ \hline Huffman Code & 11 & 00 & 01 & 100 & 1010 & 1011 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Huffman codes of letters in ‘this_is_test’ text.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Symbol** & **this\_is\_test** \\ \hline Huffman Code & 111010010010001001110110011 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Huffman codes of ‘this_is_test’ text.  
To find the tag for the series of letters x, y, and z, it is first necessary to divide it into 3 different parts based on the probability distribution between 0 and 1. The letter x is allocated from 0 to 0.7, y from 0.7 to 0.8, and z from 0.8 to 1. Since the first character of the series is x, the range allocated to x is expanded from 0 to 0.7 when the second character is passed. The new interval is divided into three different parts based on repeat probability distributions. The letter x is now allocated from 0 to 0.49, y from 0.49 to 0.56, and z from 0.56 to 0.7. Since the second character of the series is y, the process is continued by selecting 0.49 to 0.56. The third character of the series, z, will allocate between 0.546 and 0.56, and any numerical value within this range can be selected as the label of the series. The diagram of the determination of alphabetic arithmetic coding labels is shown in Figure 4. In the figure, the steps of this process are shown from left to right. As shown in the figure, the midpoint of the last range in this example, 0.553, was selected as the label.  
Arithmetic coding addresses some deficiencies in the Huffman encoding algorithm, however, there are also significant disadvantages in arithmetic coding. The main disadvantages of arithmetic coding are: (1) it is difficult to implement, (2) it does not generate prefix code, and (3) the algorithm execution is very slow. Such difficulties can be overcome, but the lack of a prefix code is a notable disadvantage, possibly leading to fault resistance.