A genetic algorithm approach for verification of the syllable-based text compression technique

Abstract

Provided that an easy mechanism exists for it, it is possible to decompose a text into strings that have lengths greater than one and occur frequently. Having in one hand the set of such frequently occurring strings and in the other the set of letters and symbols, it is possible to compress the text using Huffman coding over an alphabet which is a subset of the union of these two sets. Observations reveal that, in most cases, the maximal inclusion of the strings leads to an optimal length of compressed text. However, the verification of this prediction requires the consideration of all subsets in order to find the one that leads to the best compression. A genetic algorithm is devised and used for this search process. In Turkish texts, because of the agglutinative nature of the language, a highly regular syllable formation provides a useful testbed.

Get full access to this article

View all access options for this article.

References

[1] L.D. Davis , Handbook of Genetic Algorithms ( Van Nostrand Reinhold , 1991).

[2] D.E. Goldberg , Genetic Algorithms ( Addison-Wesley, Reading, MA , 1989).

[3] D.E. Goldberg , Sizing populations for serial and parallel genetic algorithms , Proceedings of the ICGA ‘89 70-79 .

[4] R.W. Hamming , Coding and Information Theory ( Prentice-Hall, Englewood Cliffs, NJ , 1986).

[5] T. Jones, Evolutionary Algorithms, Fitness Landscape and Search (PhD Thesis) (The University of New Mexico, New Mexico, 1995).

[6] K. A. De Jong and W.M. Spears , An analysis of multi-point crossover , FGA (1991) 301-315 .

[7] G. Lewis , Turkish Grammar ( Oxford University Press, Oxford , 1991).

[8] S. Roman , Coding and Information Theory ( Springer-Verlag, New York , 1992).

[9] R. Sedgewick , Algorithms ( Addison-Wesley, Reading, MA , 1988).

10.

[10] A. Wright (ed.), Foundations of Genetic Algorithms ( Morgan-Kaufmann , 1991).