Multistream Compression has proven to be competitive in terms of compression ratio. It utilizes a binary tree structure which follows practically the same rules for its construction as the Hu man method. This tree structure is ideal in terms of compression ratio for creation of codewords by Hu man compression. Comparing to the Hu man method the Multistream Compression is based on di erent idea of how to compress data. This fact raises the question whether the same tree structure provides the best performance. The presented paper investigates possible improvements of the tree structure. A genetic algorithm application was created for this purpose. The design of this application is presented in the paper as well as the obtained results. The whole application is set to the context of the MSC trees.
The Multistream Compression (MSC) is a statistical lossless compression method
invented by Jiri Kochanek. The method is based on the idea of splitting data
into parts [
The algorithm is distinctive by a special binary tree structure, similar to Hu man tree, which is used throughout the compression process. Each of the tree nodes contains its own data for compression which are arranged in streams. This method di ers from other compression algorithms based on splitting data into streams by the fact that in this case the streams do not contain symbols but counters.
Although the MSC algorithm is not very well known, it has proven its
qualities in terms of compression ratio. It is reported that the original unoptimized
version of MSC used in conjunction with Burrows-Wheeler Transform (BWT)
and Move-to-Front Transform (MTF) provides results somewhere between gzip
and bzip2. When it is compared to simple Hu man and Arithmetic coding, the
compression ratio is the highest in case of the MSC [
This paper shall serve as a demonstration that the compression ratio of the MSC algorithm can be further improved. This is achieved by using a di erent, more convenient, structure of the MSC tree than the one constructed using the original version of algorithm. The reader shall be warned in advance that this paper does not present a new way of constructing such an improved tree. The paper rather presents an application of genetic algorithms. It searches the space of possible tree solutions and based on the evaluation of candidates it tries to nd the best trees possible. However, it is not the purpose to nd the single best tree for given input data. The main purpose of the application is to delineate to what extent these improvements can be achieved. 2
The MSC algorithm consists of several steps. Some of these steps are incorporated into the presented application. For this purpose the working principle of the MSC algorithm is described in this chapter. 2.1
Input Data Statistics The algorithm starts with reading characters from the input data. For each symbol occurring in the input data, its rst occurrence as well as number of occurrences are determined. Once the reading of input data is nished, the statistics is sorted with respect to the number of occurrences.
5 a 0 11 0 4 1 2 b 1 2 r 2 no of occ symbol first occ
Creation of Binary Tree When the statistics are in the desired form, they serve as a basis for building an MSC tree. Similarly to the Hu man tree, the symbols become the leaves of the binary tree. In this stage, parents of two nodes with the lowest number of occurrences are created iteratively until there is only one unconnected node remaining { the root of the tree as shown in Figure 1. The newly created nodes store the same properties as the leaves. The number of occurrences is obtained as the sum of the values of its children. The rst occurrence is adopted from the child with earlier occurrence (left child). Comparing to the leaves, the inner nodes do not carry any symbol. As opposed to the Hu man tree, the MSC tree is governed by an additional rule. This rule states that every left child must have earlier occurrence in the data than the right one, even if it has a smaller number of occurrences. Moreover, each node is equipped with a counter and a direction switch. 2.3
Creation of Counter Streams Initially, before the traversing of the tree starts, the counter of each node is set to zero and each switch position is set to left. The switch determines the active child of a node and thus only one active path is built in the tree from the root to the leaf. During the creation of counter streams the input data are read for the second time. For each read symbol, the tree is traversed from the root node all the way to the leaf node representing this symbol. Each time a node is passed, its counter is incremented. If two consecutive symbols are di erent, at least one direction switch in the tree needs to be switched to the opposite direction. The rule is that when the position of a switch is swapped, the counter value of the node which loses the active path is written into the stream of this node. 2.4
Statistical Analysis of Streams
This step is performed only when multiple coding methods are available [
ZEBC is a variable-length coding similar to Elias Gamma. This method is more
suitable for compression of the streams containing higher values. It was developed
speci cally for MSC algorithm [
Coding At this stage, the streams of counters are known as well as the coding methods. For creation of the nal compressed stream, the MSC tree is traversed once again. At the beginning, the counter of the root node is set to number of characters in input data, counters of other nodes are reset and switches are set to left. The tree is traversed from the root to leaf nodes using the active path determined by the switches until the counter of root node is equal to zero. In case the counter at entering a node has value 0, next value from the stream of counters is read, coded and written to the nal stream of coded values. If a node is accessed for the rst time, additional information (leaf node ag, chosen coding method and its parameters and symbol for leaf node) is written to the output before the coded counter value. Each time a node is accessed, its counter is decremented. When it reaches zero, the switch position of the parent node is changed. 3
In the well-known Hu man algorithm the codeword lengths depend on the depths of the leaves (representing a symbol) in the tree. In the MSC algorithm the codeword length directly depends on the values of counters { lower number of higher values can be coded more compactly than higher number of lower values. The counter values are then dependent on the structure of the tree. By changing the order as well as depths of the leaves, the number of occurrences for inner nodes (which is the sum of counters) and the total switching count of the tree switches (which determines how the number of occurrences will be divided) also changes.
As described above, the MSC algorithm incorporates the possibility to select a coding method based on the reached compressed length. Each of these methods has a di erent relationship between values of the stream counters and the coded length of the counters. As an example we can name the Elias Alpha coding where the coded length depends linearly on the coded value. ZEBC coding has a logarithmic relationship and therefore it is more suitable for coding higher values as shown in Figure 2. It is also worth mentioning that the coded length changes in steps { the insensitivity increases for higher values. For example it makes considerable di erence if we divide 120 into 119 and 1 or into 60 and 60, the di erence in coded length of the two values is 30%.
Some implementations of the MSC algorithm include also Hu man coding1 for coding of the counters. Hu man coding does not depend on a single value but the resulting codeword for the counter depends on all values in the considered stream. Moreover, the selection among various coding methods causes that the relationship between the occurrences in input data and the length of the nal coded string is rather complex.
DependencyofcodedlengthoninputvalueforEliasAlphaandZEBCcoding
Also, in order to increase the compression ratio, various preprocessing
transformations of input data can be used in conjunction with the MSC algorithm.
The transformation having the highest e ect on the compression ratio is the
Burrows-Wheeler Transform (BWT) [
For unprocessed input data, the majority of the nodes is coded by Elias Alpha. Since Elias Alpha coding produces compressed data length equal to Hu man coding, much improvement is not expected by changing the tree structure. Preprocessing of the input data causes that strong majority of the nodes is coded by ZEBC coding. Since di erent relations apply for ZEBC, the question is whether in this case the tree constructed according to Hu man produces the best result. 4
Genetic algorithms are included in the group of algorithms called evolutionary computing algorithms. These algorithms are derived from the principles de1 In this case the Hu man coding is considered as a coding method for MSC coding.
In other cases throughout the paper it is considered as a standalone compression algorithm which is compared with the MSC. scribed by the Darwinian evolution of species. Genetic algorithms work with a population of result candidates. These candidates are represented as chromosomes. Chromosomes are composed of alleles which can be binary or have a di erent representation. 4.1
Chromosomes The presented application optimizes the structure of a binary tree. Therefore, the chromosomes shall in some way represent the binary tree. The trees were chosen to be represented by the tuple fsymbol; depthg for each leaf. This representation is a compact one since only leaves determine the entire tree. Also, the chromosomes allow simple usage of genetic operators and are easily set up after generating initial population. The length of the chromosome is dependent on the number of symbols in input data.
Various tree representations can be found in literature. In [
Initial Population The initial population of the MSC trees is generated in a random fashion. No a priori knowledge is incorporated. It could possibly accelerate the nding process. However, the di erence rate in the structure between the tree constructed by the original version and the best trees generated by the genetic algorithm is not known. The generation of each tree starts with the root of the tree. In following iterations, two nodes are added to one of the current leaves in the tree. This is performed until the number of leaves is equal to number of symbols in the input data. The current leaf which is appended with the two nodes is selected randomly. When the structure of the tree is nished the symbols are randomly assigned to the leaves. 4.3
Selection of Individuals The progression of the result candidates is caused by the selection and application of genetic operators. Selection is probabilistic and depends on a function evaluating each candidate- tness function. For genetic algorithms various selection mechanisms have been reported. For example, standard genetic algorithms (SGA) typically use Roulette Wheel Selection. In SGA each results get a proportionate interval based on its evaluation result. A random number is then selected ( guratively a roulette wheel is turned). The result candidate into whose interval the random number fell is then selected into the next generation.
The presented application uses the Roulette Wheel Selection. The evaluation of the result candidates is based on the calculation of coded data length. To determine the length, node streams are created and the analysis is performed as described in Sections 2.3 and 2.4 for each result candidate. When using ordinary roulette wheel selection, the best solution is not quite often copied to the next generation. To prevent this loss one of the solutions having the best tness is automatically transferred to next generation.
The aim of the application is to get a minimal length of the coded data. But for Roulette Wheel Selection better solutions shall get a larger chunk. To convert the best solution with minimal value to the highest number the tness function is of following form: f itness = (codedLen minLen)2 (1) where minLen is the calculated length for the best result candidate in the current generation and codedLen is calculated length for the examined candidate. To improve the convergence of the results, the tness function required a tuning. It was empirically determined that the second power of the subtraction gives reasonable balance.
In this implementation two methods are considered for the analysis Elias Alpha and ZEBC. As mentioned above, the length of coded values by Elias Alpha is equal to the coded value itself. Determining the length of the ZEBC coded value is more complicated. Based on the input value and the base, the interval in ZEBC table is found, then lengths of both parts of coded value ZE and BC are determined by (Z+I) and (I+1), where Z is the base and I is the interval number in the ZEBC table. 4.4
Genetic Operators There are two basic genetic operators to modify the result candidates crossover and mutation. In crossover a random point(s) in chromosome is/are selected and subsequently chromosomes of two result candidates are divided in this point and combined. In this way two children are created as a combination of two parents. In order to perform the crossover stage the whole population is traversed and two candidates are randomly picked.
After the crossover is performed, there is a high probability that some of the characters will be contained more than once in the tree. The leaves are thus traversed and if a second occurrence of a symbol is found, it is removed from the leaf. After the traversal, the characters that have not been assigned are assigned to the blank nodes.
In case of mutation, each allele is mutated with a chosen probability of
mutation [
Crossover and mutation are not the only genetic operators used in genetic
algorithms. For example, the paper [
a b
c A non-negligible part of the execution time belongs to managing the created trees. As mentioned before, the MSC tree is not arbitrary. One of the things that needs to be managed is to force its binary structure. This is not a concern when generating the population considering the way the trees are created - two children are added to a node. However, after applying the genetic operators the trees need corrections. For this purpose a technique called balancing is employed.
When balancing the tree we have to look at the number of indicators. Firstly, it has to be found out how many leaves are remaining to be added to the tree and at least how many of them need to be added to get a valid binary tree. When these two indicators are equal it is required that the remaining nodes are added and the tree does not grow deeper. This is illustrated in Figure 3. It is obvious that when the input data contains 5 symbols and after assigning 3 we have two leaves to add. To get a valid tree at least two nodes need to be added. Therefore the last two nodes are added to these positions and the depth does not grow. Table 1 depicts an example of chromosome correction (fsymbol,depthg pairs). In the rst row a chromosome after crossover is illustrated whereas in the second row the balanced chromosome that is created from the rst chromosome is shown.
Secondly, when a leaf is left child of its parent then the depth of the following leaf can be greater than or equal to the depth of the left child. Table 2 depicts an example where the depth of symbol b is changed to 3 by mutation. In this case, this symbol has to be a right child of the node of depth 3 so symbol b must be placed to depth 4 or higher. The corrections are done in a way to reduce the di erence between the obtained and the corrected value. The number 4 is thus selected in the given example.
Another correction technique forces the above-mentioned rule which states
that each left child has earlier occurrence in the input data than the right child.
This correction is performed before the tness calculation and selection. For
this task, a tree representation that contains all tree nodes (not only leaves)
is needed. The chromosome is thus converted to the left tree representation as
described in [
This section presents the achieved results of the designed genetic algorithm. Moreover it delineates how much these results di er from the original version of tree construction.
The genetic algorithm was tested on two sets of data. For this purpose, two random English texts were selected as input data with lengths { 5580 and 11508 characters. These data lengths were enough to obtain majority of nodes in MSC tree coded by ZEBC. If the used input data was too short, the e ect of preprocessing by BWT would be minimal and the results would not be much di erent from results for unprocessed data.
Four experiments were performed { each input data were tested unprocessed and preprocessed by BWT. To obtain results with statistical signi cance each experiment was repeated ten times. The results can be seen in Table 3. Each experiment is identi ed by IDL (input data length) and by the usage of BWT.
The remaining columns in the table then contain: AL - average value for all repetitions after 100 generations. ML is the average of the minimum lengths and TML is the total minimum length that was achieved in all repetitions of the experiment. BAL value is the length of coded data when using the original tree construction process.
The results in the table show that an improvement of compression ratio can be achieved when preprocessing of input data is performed. The rate of improvement is not insigni cant since the genetic algorithm created trees reaching improvement of up to 5%. It can also be seen that in case of unprocessed data the genetic algorithm found the trees which at best produced a coded length of around 1% worse than the original algorithm. Therefore, the improvement for preprocessed data is expected to be even slightly higher than the reported value.
Figures 4 and 5 show the development of average and minimum values in generations. The progressions actually show the average values (of average and minimal length) from all repetitions and the dashed lines depict the standard deviation. The turquoise constant line denotes the length obtained by the original algorithm and the green line shows the total minimum obtained. The plots are shown for cases when preprocessing of input data is used. It clearly demonstrates that from the rst generations the trees obtained by the genetic algorithm give better results than the original algorithm.
15 100 15 000 14 900 14 800 thg14 700 ne led14 600 cod14 500 14 400 14 300 Fig. 4. Progress of average and minimum values in generations for a text with 5580 characters 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
generations This paper presents a genetic algorithm application for the exploration of possible improvements of the MSC tree. It was shown that when the majority of counters are coded by ZEBC coding, the tree construction process of the original MSC algorithm is not ideal. It was found that the improvements in terms of coded length of the data is up to about 3 - 5%.
Moreover, it was found that in case of unprocessed data, where no or very small improvement is expected, the genetic algorithm nds solutions that in the best case are about 1% worse compared to the original algorithm. This means that further improvements might be achieved if the majority of counters is coded by ZEBC.
The next logical step is to create a new tree construction algorithm which would improve the compression ratio. This can possibly be achieved by genetic programming application that would nd this algorithm via optimization. Alternatively, some metrics within the tree can be found that would guide the tree construction based on a determined relationships.