# An Efficient Encoding Algorithm Using Local Path on Huffman Encoding Algorithm for Compression
## 3 Materials and Methods
### Proposed Algorithm  
To better explain the proposed algorithm, an example follows. The text 'aaaabbbbcdefghjklmnoprsaabb' is used. For a better understanding of the developed algorithm, a sample special sequenced text is selected. However, in the experimental results of the study, the algorithm is tested with the data used in the literature. The number of times each character is used in text is defined as the frequency of these characters. In the text used in our example, 'a' is used 6 times, and 'c' is used 1 time. The frequency table for each character in the text is tabulated in Table 5 below. The Huffman tree of the text is formed, as shown in Figure 8. To produce a bit codeword of each character, the Huffman tree is traversed from the root to the leaf node where the target character is located. For example, in order to reach the character 'c', the sequence of 10010 bits must be followed, respectively. In addition, each character symbolized by the Huffman encoding algorithm is presented in Table 6. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Character** & **Symbol** & **Bit** \\ \hline a & 00 & 2 \\ b & 01 & 2 \\ c & 10010 & 5 \\ d & 10011 & 5 \\ e & 10100 & 5 \\ f & 10101 & 5 \\ g & 10110 & 5 \\ h & 10111 & 5 \\ j & 11000 & 5 \\ k & 11001 & 5 \\ l & 11010 & 5 \\ m & 11011 & 5 \\ n & 11100 & 5 \\ o & 11101 & 5 \\ p & 11110 & 5 \\ r & 11111 & 5 \\ s & 1000 & 4 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Symbolization of the characters. Figure 8: Huffman tree of ‘aaaabbbbcdefghjklmnoprsaabb’ text. \begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c c c c c} \hline \hline
**Symbol** & **a** & **b** & **c** & **d** & **e** & **f** & **g** & **h** & **j** & **k** & **l** & **m** & **n** & **o** & **p** & **r** & **s** \\ \hline Frequency & 6 & 6 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Frequencies of letters in ‘aaaabbbbcdefghjklmnoprsaabb’ text. If only the Huffman encoding algorithm is used to compress the text used in the example, a 98-bit sequence would be generated as follows:  
\"00000000010101010010100111010010101010110111110001100110110111100111110111110000000101\". The main objective of the proposed algorithm, and all compression algorithms, is to reduce the number of bits needed to symbolize the characters. The flowchart of the proposed method is shown in Figure 9.  
The developed encoding algorithm is outlined in the following steps:  
Step 1: The Huffman encoding algorithm is applied to the data. Step 2: Characters represented by large bits are identified, and characters represented by small bits are ignored. In this example, ignored characters are 'a' and 'b'. Because the Huffman coding algorithm ideally symbolizes these characters with 2 bits, further compression of these characters is not possible. Step 3: Flag bits identified as 0 or 1 are added between characters represented by long bits. Flag bit \"0\" is added between determined characters if the current character and next character are not in the same leaf. Flag bit \"1\" is added between determined characters if the current character and next character are in the same leaf. That means there is no need to go through the entire Huffman tree to reach the next character. In Figure 10, an example bit sequence from the text \"...bcdefg...\" is shown. Figure 10a shows the Huffman encoding algorithm and Figure 10b indicates the bit sequence of the specified section. Figure 9: Flowchart of proposed encoding algorithm. Step 4: When the flag bit represents the characters on the same node, there is no need to repeat the first three bits common in these characters. In this step of the algorithm, the first three bits of the characters on the same node are truncated and the bit sequence is rebuilt.