# An Efficient Encoding Algorithm Using Local Path on Huffman Encoding Algorithm for Compression
## 2 Technical Background  
### Huffman Encoding Algorithm  
The Huffman encoding algorithm is one of the most commonly used data compression methods in the field of computer science. The algorithm developed by [PERSON] [29] is used to reduce coding redundancy without loss of data quality. The use of data frequency is the basic idea in the Huffman encoding algorithm. The approach in the algorithm assigns symbols from the alphabet with variable codewords according to their frequency. The symbol with a higher usage frequency is  
Figure 2: An example of a grayscale image with 512 \(\times\) 512 resolution. symbolized by shorter codes in order to obtain a higher compression result. The steps for the Huffman encoding algorithm can be defined as follows:  
Step 1: The frequencies of the symbols found in the data and the possibilities of the usage are listed. These possibilities are listed in a descending order from the highest to the lowest. A node is formed as a binary tree with the obtained probabilities. Step 2: The lowest two probabilistic symbols contained in the cluster are retrieved. These two values are aggregated, and a new probability is generated. All the possibilities are regulated by a descending sequence. Step 3: A parent node is created, marking the left branch as child node 1 and the right branch as child node 0, respectively. Step 4: To create a new node, the two nodes with the smallest probabilities are changed, and the tree list is updated. If there is only one node in the list, then the process ends. Otherwise, Step 2 will be repeated. The Huffman algorithm is illustrated by an example below. Let's take the text 'this_is_test' and compress it with Huffman encoding. In the first step, the frequencies of each symbol (letter in the sample) in the text are counted. The frequency of the letters in the sample text is shown in Table 1.  
In the next step, nodes are generated according to the frequencies of the symbols. As shown in Figure 3a, each node created at this stage stores a symbol and the frequency of that symbol, e.g., (i, [2]) demonstrates that the 'i' symbol has a frequency of two in the text. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Symbol** & **t** & **s** & **i** & – & **h** & **e** \\ \hline Frequency & 3 & 3 & 2 & 2 & 1 & 1 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Frequencies of letters in ‘this_is_test’ text. Figure 3: Huffman tree of ‘this_is_test’ text. (**a**) Frequency of letters; (**b**) Huffman tree. The previously created nodes are updated in the second step of the algorithm, as described below. As illustrated in Figure 3b, the nodes of the letters with the lowest frequencies are selected. The nodes with the lowest frequencies that are randomly selected from Level 1 are combined to generate a new node at a higher level (Level 2). The value of the newly created node is equal to the total value of the frequencies of the merged nodes. Merging the nodes with the lowest frequencies continues until the root node is obtained. In the third step, the links connecting the nodes are labeled with the values \"0\" and \"1\". Here, connections on the left side are usually marked with a value of \"0\", and connections on the right side are marked with \"1\". In this way, a symbol is represented by an access path ending at the lowest level node starting from the root node. The access path from root to leaf node is called the Huffman code. The Huffman codes, based on the codeword, used in the example are shown in Table 2. All symbols are replaced by Huffman codes. The compressed bit sequence, obtained as a result of replacing the symbols in the example used with the Huffman codes, is tabulated in Table 3. At the stage of rebuilding a compressed file, the Huffman tree is regenerated from the frequencies of the symbols and converted into the original characters. The bit stream is used to traverse the Huffman tree. Each iteration is monitored from the root node until it reaches the node of that symbol. This procedure starts all over again for the next node.