Efficient compression from non-ergodic sources with genetic algorithms

Several lossless data compression schemes have been proposed over the past years. Since Shannon developed information theory in his seminal paper, however, the problem of data compression has hinged (even though not always explicitly) on the consideration of an ergodic source. In dealing with such sources one has to cope with the problem, of defining a priori the minimum sized symbol. The designer, therefore, is faced with the necessity of choosing beforehand the characteristics of the basic underlying element with which he or she is to attempt data compression. In this paper we address the problem of finding the characteristics of the basic symbols to consider in information treatment without assuming the form of such symbols in the same data source. In doing so, we expect to achieve a pseudo-ergodic behavior of the source. Then we are able to exploit the characteristics of such sources. Finding the basic elements (which we call "metasymbols") is a complex (NP complete) optimization task. Therefore, we make use of a non-traditional genetic algorithm (Vasconcelos genetic algorithm) which has been shown to have excellent performance, to find the metasymbols. In this paper we discuss the problem, the proposed methodology, some of the results obtained so far and point to future lines of research.