Abstract
DATA COMPRESSION

1. Introduction
	Data compression is a method to reduce the space occupied on the support by a file. Decompression is a method to come back to  the initial form of a compressed file.
	The paper’s objectives are:
•	to present the classes of compression algorithms
•	to present the C++ sources for some algorithms
•	to define the appreciation indicators for algorithms
•	to identify the situations of efficient utilization
•	to create the premises for developing new compression techniques
	To analyze the statistic behavior of programs that implements compression algorithms, significant lots of files will be formed. The compression algorithms’ behavior will be studied by aggregating the time and compression grade criteria.
	All algorithms are presented as text sources, together with the files on a disk that accompanies the paper. 
	The programs have the same variables, for continuity, are auto-documented and have been tested under Borland C++ 4.0.
	The paper describes compression techniques that work on the alphabet, use dynamic dictionaries, appearance frequency for characters, Markov chains, traversing with fractals, genetic algorithms and techniques specific to neural networks.
	For the first time, the paper presents some results of the authors’ research activity in the last five years. Other results are published in the articles specified in bibliography.
	The paper contains many examples, so that the reader can rapidly develop his own applications.
	The disk contains other examples of compression programs and the files used by the authors in the paper.
	The files’ size and the complexity of the statistic processes are done to ensure the stability of the obtained results.
	The bibliography includes both fundamental books in the compression field, as well as articles written by the authors that present results obtained in time.
	The authors thank all those who will contribute to a next edition of this book, by suggestions and propositions.

2. Compression
	The raw file  represents what is introduces, directly or indirectly, from the keyboard, written on the support using the code ASCII , without modifications.
	The modified file is obtained starting from a raw file by eliminating some inconveniences.
	For the considered example, we have, first, to eliminate the spaces.
There are many classification criteria for sets of data.
The significance criterion groups the sets of data in :
•	text files , in which the data are represented directly in ASCII code, or after a compression (binary, real, packed or unpacked decimal);
•	image files , colored or black-and-white, materializing the pixel matrix;
•	sound files, that contains the codification of frequencies, the duration of intensities.
The criterion of structure :
•	continuous files that contains data reflecting a massif, the text of a book; for these files, the basic unit is the word (2 bytes) if the representation of the massif’s elements corresponds to the integer type (int), the double word (4 bytes) if the massif’s elements have the real type (float), and 1 byte corresponding to the character type. 
•	file formed by articles, grouped data describe the individuals of a collective, after a pattern. It is possible that patterns are identical  (files with fix length articles), or different (files with variable length articles).
Another criterion, important in data compression, is the criterion of information’s nature:
•	files in which all represents information that cannot be lost; algorithms without loss of information can be operated on these files;
•	files that can be the object of refinements, sets of data where consecutive spaces, used as separators, can be eliminated
Transformations in sets of data:
•	Concatenation of  files;
•	Elimination of consecutive strings of separators;
•	Numerical conversions;
•	Multiplicity factors;
•	Correspondence of sub-strings;
•	Reduction of the alphabet’s length.
	Compression is a method to reduce the memory space occupied by a set of data. By compression, the initial data are transformed into equivalent representation called compressed data. 
	Decompression is the method to bring the compressed data to a close or identical form to the one had before compression.
	Let’s consider  an alphabet A, formed by the symbols a1,a2,..,an. Each symbol  is represented on a number of bits in the computer’s memory.
The function  : h:AN* called the length function of the alphabet’s symbols.
	A code is distinct  if every symbol of the code is distinct from the other symbols. Both variants of codes previously presented are distinct codes, but the variable code  in table 2.5 is not isomorphism (does not have a unique decompression). By definition, all fix length code are isomorphism. The variable codes are not always isomorphism.
A  code has the property of prefix, if for a symbol x, the combination xy is not a symbol of the code, for any value of y. A variable prefix code has always a unique decompression. The prefix codes have an instantaneous decompression, meaning that they can be decompressed without a previous reading of the file. 
	A prefix code is minimal if for any prefix x of a symbol, there is the combination xy with one of the signification:
•	symbol of the same file’s alphabet;
•	prefix of a symbol.

3. Compression of numerical data files 
	A code is universal if the average of the symbols’ length of the codified alphabet is limited by c1 ( H + c2 ). Being given a arbitrary source file with entropy non-zero (see chapter  6), a universal code reaches an average length of symbols, that is in most cases the possible optim code for the respective file.
	The power of compression offered by a universal code depends directly on the size of constants c1 and c2. By definition an asymptotic optim code is a code for which the average length of codes is close to the entropy. 
	The first Elias code is simpler, but is not optim. This code, gamma, puts in correspondence an integer x with its binary value prefixed by [lg x] zeros. The binary value of x is expressed in as less bits as possible, therefore it will always begin with 1 as a prefix separator.
	Another universal code based on Fibonacci series, was defined by Apostolico and Fraenkel in [Ap85]. While the Fibonacci code is not optim asymptotic, it can be compared with Elias code, as long as the source file’s length is not too big. 
	The Fibonacci code, presented by Apostolico and Fraenkel, is based on the Fibonacci series of order>=2, where the Fibonacci series of oreder=2 is : 1, 1, 2, 3, 5, 8, 13,....
	One of the most used methods to obtain a compression for this type  of files is to converse to packed decimal or real form.
	An alternative to this variant is the compression with differences.
	The term differences describes a technique of comparison of a recording, for the compression of an alphabet’s symbol, with another basic recording, registering only the differences.  
	In this case, the differences are not done after neighbor symbols, but after a base. The base is chosen between the numbers from the file so that a smaller binary representation of the symbols is obtained.

Compression of numerical files in binary code
	A special case for numerical files in binary code is the conversion of rare matrixes. 

4. Compression of text files 
	The editors and the text processors manipulate symbols of an extended alphabet, structured in :
•	subset of printable symbols;
•	subset of control symbols;
•	subset of formatting symbols;
•	subset of graphic objects.
	The resulted files are text when ASCII characters of binary type are preponderant, when the printable symbols are accompanied by successions of bits that offer information about the font, format and control. The lots contained 20 files with ASM, Pascal, C/C++ and text programs. 
	Base methods:
•	elimination of spaces;
•	binary topographic representation .
	By definition, static compression algorithms are those algorithms that traverse entire file before compression.
	The standard Huffman algorithm, arithmetic compression and Fano-Shannon algorithm belong to this class.
	Many performant compression programs use algorithms based on dynamic dictionaries. Following, the previous example will be presented , using the LZW algorithm. The algorithm will fully explained in chapter 9.
	LZW is a compression algorithm that replaces a text with another one. It is known as ‘On line textual Substitution’. The LZW algorithm replaces a number of bits of a word, of a phrase or even of a paragraph. The code is formed in a unique way, with the help of a dynamic dictionary, created after the text’s requests. The advantage over other algorithms is that the dictionary must not be transmitted or stored with the data, because it can be reconstructed on the way.

5. Compression in graphic formats
	The screen is structured as a table of pixels disposed on lines and columns. The documentation that accompanies the equipment presents both the number of lines and columns of the table, as well as the size in millimeters of the pixel, seen as a rectangular. The standard graphic libraries have all the data structures and functions that allow the access to the resources necessary to describe, implement and manipulate images, in the conditions of a relative independence of the physic equipment. 	
	A pixel is characterized by position (line and column in the table) and content (color, luminosity). The linear table of pixels has as corespondent ,in the memory, a zone called graphic memory, that stores these information. It can be worked directly on the graphic memory to transform (initialize pixels) or indirectly, using the computer’s intern memory.	
	The graphic memory’s size ensures the recording of information associated with, at least, one complete image from the screen. To ensure the continuity of the animation, similar to the real world, the rate of transfer from extern files to graphic memory or the  speed of computations must be ensured. This requests the existence of extremely performant systems.
	The black-white screens function with 16 nuances of gray, and 4 bits will be necessary for the description of a pixel in the graphic memory.
For black-white screens with 256 nuances of gray, the codification puts in correspondence 00h with black and FFh with white. The codes for the nuances of gray are between them. To represent a pixel, it is necessary 1 byte. 
	The screens that support 32K or 16M nuances request a description of the color palette by associating every fundamental color RGB in 256 nuances each. Graphic formats presented : BitMap, GIF, PCX.
	In data compression, there are used many algorithms, from simple algorithms to complex ones. The algorithms’ efficiency varies depends on the nature of the data. The simplest algorithm used on large scale is RLE. 
	The RLE principle detects a symbol having the number of consecutive appearances exceeding a fixed number. Then, this sequence is replaced by two pieces of information:
•	a digit indicating the number of repetitions
•	the symbol that repeats
	The minimum limit to compress a string, is that the sub-string’s length be minimum 3 identical symbols.
	When the file to be compressed with RLE, meets the symbol used as special character, the next  succession will be written in the compressed file:
•	special character;
•	value 0, because in a normal codification, the string’s length will appear on this position ;
•	value 1, or the special character.
	If a succession of the special character is found, this is compressed as following:
•	special character;
•	value 1, being an unused value in the compression process;
•	number of repetitions of the special character, between 2 and 255.
	The ‘lib.h’ library contains 2 functions, written in C++, to compute and to write the results. Following, the source text of this library is presented.
	JPEG has very good compression results for color and in gray nuances white-black images, but has problems  with white-black images. There are problems with images where colors were mapped (use of the implicit colors of the working environment, for example use of the Windows palette), being necessary to expend them in a normal representation.
Sequential Way
Step 1 		The image is transformed, from the chromatic point of view, into a tridimensional coordinate system. The luminosity is considered as a first axis of compression. The other two axes are used to encode the color.
Step 2(Optional) Averages of the pixel groups are computed. The groups are called sample components.
Step 3		The pixels’ value are grouped for every field in blocks of 8x8 pixels. Each block of 8x8 pixels is transformed with the DCT function (Discrete Cosine Transform), the Fourier transformation, having as result a frequency map, with 8x8 components.
Step 4		For each block, a DC quantification coefficient is obtained. After that the result is rounded to an integer. This is the fundamental step of losing the information. The bigger the DC coefficient is, the  bigger the information loss is. Even if the DC has the minimum value, meaning 1, the information will be lost because the result of the DCT transformed is not  integer in normal sense.
Step 5		After the DC coefficients’ quantification, the data strings are compressed using the Huffman standard algorithm or the arithmetic compression. Strictly, the JPEG standard does not allow anything else but Huffman compression, the arithmetic compression being just an extension.
Step 6 		In a JPEG file all compression parameters are included in headers, so that the decompression can be done rapidly, without traversing the whole file.
Compression without losses
	This method does not used DCT, using a compression based on differences. Only the differences between the pixel’s value and a predicted value are stored.
	The pixel’s predicted value is given by a function that depends on the compressed values already transmitted. For example, it can be used as prediction function the average of the precedent pixels. The JPEG standard allows 8 prediction functions. The differences compression is done using the same methods as in sequential compression, meaning the Huffman algorithm or arithmetic compression.

6. Metrics of files for compression
Indicators of performance for algorithms. The compression degree, the compression rate, minimal length, common strings, files’ entropy. Shannon called this degree of informational liberty entropy, because the equation that express this degree has the same form as the thermodynamic entropy of Boltzmann. In the information theory, the entropy represents the medium degree of disorganization in a file.
	The normal indicator of entropy for the file F is defined on an alphabet with n symbols.

Errors of data compression
	The data transmission using discrete channels without noise is, unfortunately, a not very realistic way in communication systems. These systems of data transmission are predisposed towards two types or errors:
•	phase errors,  in which a symbol’s code is lost or added;
•	amplitude errors, in which a symbol’s code is corrupt.
	The degree the errors degrade the transmission, is a important parameter in choosing the method of data compression.
	The susceptibility to errors of compression algorithms depends on the algorithm’s type: static or dynamic.

7. The Class of Huffman Algorithms
	The Huffman algorithm consists in recording the symbols met in a file by variable length codes. By definition, the Huffman algorithm is a code of the variable-block type.
	For a text file with a length big enough, the symbols’ frequencies from the alphabet associated to the file, have a distribution law different from the normal law.
	In a file F with length n, having an alphabet with m symbols, it is identified min, the symbol with the smallest appearance frequency and max as the symbol with the biggest appearance frequency. The Huffman algorithm associates to the symbol min a configuration of bits with big length, while for max will have the smallest configurations of bits possible in the case of file F. 
	The algorithm is composed from 2 phases. The first consists in reading the whole data ensemble from the source file and accounting the appearance frequencies for every symbol. A table of appearance frequencies will be obtained.  This table id ordered in decreasing order of the frequencies. 
After that, the symbols are reduces successively until the table’s exhaustion. Reducing means forming a new element from the symbols with the smallest appearance frequencies.
Therefore, the standard Huffman algorithm’s steps are:
1. 	traversing the file;
2. 	constructing the stack of distinct symbols and their appearance frequencies;
3. 	constructing the binary tree, whose symbols are the symbols from the stack, like that :
•	arranging the symbols in the stack in decreasing order of the frequencies and considering the leafs of the tree;
•	as long as there is more than one node, assembling the node with the smallest frequencies, in order to form a new node with the frequency equal with the sum of the assembled nodes;
•	assigning values 0 for each right branch and 1 for each left branch;
•	reading sequentially, starting from the root to the leafs, associating to each one the corresponding code;
4. at the second crossing of the file, using  the codes with variable generated lengths and associated to the symbols from the stack, to compress the source file and obtain the compressed file. 
For a better understanding of the Huffman algorithm, the compression and the decompression phases will be fully explained. Each phase, compression or decompression, is accompanied by a program written in C, programs that can be found on the disk.
The source programs for the compression algorithm  can be found on pages 108-115.
	One of the main features of the Huffman compression is that a code can be found as the prefix of another code. Due to this fact, by reading the compressed file bit by bit, the initial file can be decompressed using the same compression table. In the decompression phase, this table is called decompression table. 
	This decompression table will be used to reconstruct the original tree. After determining the tree, the file will be decompressed. The source programs for the decompression algorithm can be found on pages 117-122. 
	The modified, adaptive and dynamic Huffman algorithms will be described in pages 129-144, together with their source programs. 
The Fano-Shannon algorithm has 3 steps:
•	establishing the table of appearance frequencies for all the symbols from the file;
•	coding the symbols after a pre-established algorithm;
•	compressing the file using the new Fano-Shannon code.
The source programs are presented in pages 148-156 and 157-163. The performances are analyzed on  a lot of 32 files.

8. Arithmetic compression 
Arithmetic compression is superior to the well-known Huffman algorithm in many ways. This method introduces a clear separation between the model of data representation and the model of their compression.
	For many, data compression supposes invocation of an ad-hoc technique, such as converting text spaces into TABs, creating special codes to replace common sequences or using the RLE algorithm to compress images.
	These methods contradict with the newest compression methods, based on paradigms, where from an initial string of symbols and an algorithm, a new, encoded string is obtained. This string is a compressed version of the initial string.  
	The decompression, that has to be based on this algorithm, reconstructs the initial string from the compressed one. The initial strings are formed from ASCII or binary characters, while the encoded string is a simple sequence of bits.
	The form in pseudo-code is simply presented  in page 170 and presents a series of factors such as:
	Incremental transmission and reception. The compression algorithm, as described, does not transmit anything until the whole message was not encoded. Similar, the decompression algorithm does not start the decompression until the whole transmission was not received. In most cases, it is necessary an incremental way of operations.
	The desire to use the arithmetic of integers. The requested precision to represent the interval [low, high] increases with the message’s length. The representation using integers will help to overcome this obstacle, but the possibility to overflow or underflow must be considered.
	Representing the model so that it can consulted efficiently. The used representation must minimize the time necessary to decompress, in order to identify the next symbol. More, an adaptive model must be organized to minimize the time consumed by the process of recording cumulated frequencies.
	The source programs are presented in pages 171-183. The restrictions and the arithmetic compression models (fix and adaptive) determines an certain level of performance of this type of compression, reflected by the compression time, reflected by the execution time and the compression rate.

9. Class of Lempel-Ziv algorithms
	The Lempel-Ziv algorithms represents an extension of the classic vision of the compression algorithms, where the source messages were put in correspondence with the codification fixed group.
A new concept is introduced: the free analysis of the source messages during execution.
	In 1984, Terry Welch presented the results of research activities from Sperry Research Center. These activities were a practical description of LZ78 algorithm, called LZW. He talked about the LZW compression algorithm through its possible utilization  in disc controllers and magnetic band, but he was convinced by the possibilities of implementing the algorithm in a compression program of general use. Almost immediate after the article, a compress program was started in UNIX.
	LZ77 compression uses the previous text as a dictionary. It replaces the character string from the input text with pointers to the current dictionary used in compression. The compression rate depends on the dictionary’s length, the size of the window of the previous text and the source text’s entropy.
	The main data structure of the LZ77 algorithm is a text window divided in 2. The first window is formed by a block of text recently compressed. The second one, much smaller, is a reading buffer. The reading buffer contains the read characters in the input flux, but uncompressed. 
	The decompression algorithm is simpler because it does not request any comparison. It reads a symbol, transmits the indicated string, the next character, shifts the text and starts again.
	The LZ-SS variant tries to eliminate some inconveniences of the LZ77 algorithm. This variant brings two major improvements to the algorithm. The first is the way of updating the text window . In LZ77, the strings from the text window were memorized as a single continuous text block, without any helping structures. LZ-SS stores the text in a continuous window, but builds a supplementary data structure that ameliorates the strings’ organization. The source programs for the LZ-SS algorithm are presented in pages 203-216.
	Another problem of the LZ77 algorithms is the limitation of the equivalence strings’ length. The longest correspondence has the length approximately equal with the reading buffer, which means that the presented examples have 17 bytes. A possibility to avoid these limitations is to increase the window’s length. For example, instead of using a window of 4KB and a reading buffer of 17 bytes, we can use a window of 64KB and a reading buffer of 1KB.
	LZ78 abandons the principle of moving window. In LZ78, the dictionary is an unlimited list of strings met in the read text.
	The real problem of LZ78 is managing the dictionary. For example, if we use a code of 16 bits for string index, we can manage 65536 strings, including the NULL character. The strings can vary in length, theoretically obtaining the biggest string of 65536 characters, containing a single repeating character.
	The work on the Compress compression program in UNIX, started immediately after the article appeared. The technique described by Welch, as well as the existent algorithm in Compress, are known as LZW.
	The decompression algorithm accompanies always the compression algorithm. At decompression, the data flux transmitted at compression is received to reconstruct the initial data flux. An advantage of LZW algorithm is that the dictionary must not be transmitted towards the decompresser.  
	The table is reconstructed exactly as in compression phase. The source programs for the LZW algorithm are presented in pages 227-235.

	Optimization of LZW. LZW can be optimized from the dictionary’s size point of view. The compression rate will increase because longer strings can be memorized. 
	Instead of using codes of 15 bits, LZW2C.c starts by using codes of 9 bits, and does not use 10 bits until the 256 free entries from the dictionary are filled. Therefore, it will use 10, 11, 12…, 15  bits. This trick equals the compression of small files and the compression of very large files. 
	A last improvement of the algorithm is the filling code, FillingCode. It indicates to the decompressed, the annulling of all actual strings from the dictionary and the restarting from zero. The source programs for the optimized LZW algorithm are presented in pages 237-246.
	The algorithms; performances are measured on 32 files, computing the next indicators: file’s length, LZSS compression rate, LZW9-15 compression length and LZW9-15 compression rate. 
	As you can notice from presented results, the LZ algorithms  have excellent results for most files. The LZ algorithm have a very pour compression rate  for sound files, because they are very small.
	Another disadvantage of sound files is the great diversity of characters that appear in their content. The dictionaries are not very efficient for small size files, because the code’s length is, generally, bigger than the ASCII code.
	Good results are obtained for large files, as the image ones. As you can notice, for the file 3.img, the compression rates exceed 86%. Therefore, there are confirmed the theoretical results that affirm that LZ algorithms are efficient for large files. 
	The disadvantage of the LZ algorithms towards the other presented algorithms, referring the big period of time necessary for compression, is canceled by the very short period of time of the decompression. This reduction is due to the elimination, almost total, of searching in the tree attached to the dictionary.
	Therefore, the best application for LZ algorithms is to store data, which is used very often, without modifying it every time. Here are some important examples: storing annual statistics, ministries’ archives, historic documents, even telephone books. 
	A field where the implementation of LZ algorithms has conquered almost the whole market, is data transmission. The LZW algorithm is defined as a component of the CCITT V.42 bis standard, and the Unisys firm, that has the license over this algorithm, has defined a series of conditions to give the license to modem constructors. 

10. The JPEG Standard
	The JPEG aim was to develop a method to compress images with continuous tone, which has the following requests:
•	to allow the obtaining of compression rates comparable with the performant algorithms, to allow an image fidelity in a large interval of image quality rates, specially in the zone where the original’s visual fidelity is characterized is from very good to excellent; the encoder must depend on parameters so that the user can set the compression rate and the wanted qualities;
•	to be useful for any type of digital image with continuous tone of color. For example, the image must not be limited from its content point of view, such as complexity, color interval or statistic properties;
•	to have an easy calculable complexity, so that the software implementations with good performances in a wide variety of processors are liable; similar for hardware implementations with an acceptable cost  for applications that request a high performance;
•	 to have the next operating modes:
•	sequential encoding, every image component is encoded is a single scanning : left-right, up-down;
•	progressive encoding, the image is encoded in multiple scanning, the transmission time is big, the user prefers to see the image being constructed progressively;
•	encoding without losses, the image is compressed with the guarantee that any sample from the source image can be reconstructed, even if the resulted file had a larger size that the files with losses;
•	hierarchic encoding, the image is encoded with multiple resolutions, so that the versions with reduced resolution can be accepted without decompressing the image to maxim resolution.  
	After selecting the DCT compression method in 1988, JPEG discovered that the method without information losses can be difficult to define as a practical standard, used to implement encoders and decoders, without imposing severe constraints.
	The source image model used in JPEG proposal is an abstraction from a variety of image types and applications, and it is constructed only from what is necessary to compress and reconstruct the base image. It must be recognized that the compressed format JPEG does not memorize enough information to be used to realize the image indifferent the resolution.
	The standard compression of an image must establish the management of data by the system, during the decompression process. Many applications must link the printing process of the multicomponent images with the decompression process. For many systems, this is possible only if the components are related inside the same compressed file. 
	The order in which the compressed data units are placed in the compressed data string is raster-scan.
	Generally, the same entropic encoding tables and quantification tables must be used to encode the samples from a component.
	The JPEG decoders can store up to 4 different quantification tables and up to 4 different entropic encoding table, simultaneous.
	The sequential operating way based on DCT is constituted from the FDCT steps and the quantification steps, described at the beginning of this chapter. This model is known as baseline.
	Additionally to the sequentially baseline model, other sequential models are defined to fit 2 sample precisions, 8 and 12 bits, and 2 different types of entropic encoding: Huffman and arithmetic compression.
In the intermediary sequence of symbols, each AC coefficient is presented in combination with other AC coefficients with null values that precede in the zigzag order.
	The VLC Huffman codes must be specified externally, as an input for the JPEG encoders. JPEG includes a set of Huffman tables in its appendix, none is specified for current use, because they are specific to the application. The VLI codes are much more numerous and can be computed very fast. 
	The sequential DCT model’s structure on 12 bits with Huffman compression is an extension of the entropic compression method describes previously. The DCT quantified coefficients can be with 4 bits longer, therefore the information on the size and amplitude is larger.
	The progressive way of the JPEG standard consists from the same 2 FDCT steps and the quantification, similar for the  sequential DCT models. The difference is that every image component is encoded by multiple scanning, not in a single step as before.
	The first scanning encodes roughly, but produces an image that can be recognized. This will be rapidly transmitted, in comparison with the total transmission time. It will be refined by successive scanning until the image quality level established by quantification tables is reached. 
	Hierarchic way. The encoding procedure can be summarized like this:
1. 	filtrating and dividing of the original image in a number of multiples of 2, for any dimension; 
2. 	compressing this small size image, using one the mentioned encoders: sequential DCT, progressive DCT or model without losses;
3. 	decompressing these small size images, then interpolating and diving it  with 2 horizontal and/or vertical, using the same interpolation filter as the receiver;
4. 	using these divided images as a prediction of the original, with the same resolution and encoding the difference image with the described models;
5. 	repeating steps 3 and 4, until the whole image resolution is encoded.
	The encoding from steps 2 and 4 can be done using only process based on DCT, with a final process without losses for every component. The source programs for the DCT sequential algorithm is presented in pages 270-283.

11. Compression with fractals
	In this chapter, a series of image compression methods with fractals are presented. After 1990, the image compression with fractals has developed rapidly, due to the increase of computers’ speed. Even though, the compression of an image, using a Pentium 133 microprocessor takes between 20 and 30 minutes. 
	The fractal term became known due to the beautiful images generated by the computer, called fractals. Under this name, it is hidden the mathematics definition of fractals, known only to those interested in this domain. 
	Because the fractals theory is only beginning to develop, their applications are almost nonexistent.
	The fractals’ definition, intuitively, was given for the first time by  Mandelbrot in 1989 like this : a geometric figure or a natural object is a fractal if respects the next conditions:
•	its components have the same form as the whole, considering that they are small and can be easily deformed;
•	its form must be extremely irregular, interrupted or fragmented;
•	it contains distinct forms, variety enough when scaled and forming a very large set;

From the generation method point of view, the fractals divide into:
•	natural fractals, existent in nature and created by natural phenomena. For example: mountains, shores, neural system, trees, etc.
•	artificial fractals, informatics models of natural fractals. Met under the name of sets of fractals or ensembles of fractals. Another group of artificial fractlas can be identified in nature. 
This is the case of economic, social system, etc.

From the point of view of the transformation that generates the fractals, they divide in:
•	linear fractals that are generated by linear geometric transformations applied over some points, segments, surfaces or objects. For example, the Von Koch curves are based on the next transformation:
- it starts from a equilateral triangle with a finite length side;
- each side is sectioned in three equal parts, the middle segment is
erased and replaced by an angle that has as sides 2 segments, equal to the eliminated segment;
- for each segment of the obtained figure, the previous operation is repeated;
If it is started from an equilateral triangle, it will be obtained a
 closed polygonal line with a side that it is getting smaller.
•	non-linear fractals are obtained with nonlinear geometric
transformations. They can be artificial or natural.
In the present, there are a variety of image compression models
using fractals. Even techniques of 3D data compression developed, represented in a tridimensional space. These techniques could be used in the future to compress tomographic images, which does not present a perfect clarity.
Following, the most used compression with fractals techniques will be presented.

Vector Quantization (VQ) is a wide spread technique of image or
other data compression, having direct extensions towards 3D data
compression.

The JPEG standard of image compression. based on the DCT (discrete cosinus transformation), presented in chapter 10, can be easily
extended to volumetric data compression. This model divides the
initial volume in blocks with size 512 and the DCT converts the 512
special values into 512 frequency values, which will be encoded more
rapidly than the initial data volume. 
The DCT algorithm implementations can be met in many methods of  compression with fractals, because the DCT coefficients computation leads to very small compression times.
The approximations between the rang blocks and the domain blocks
are done on the extended DCT coefficients table. Sometimes, with
the exhaustive search algorithms from the fractals theory, a
series of resemblances are found. These resemblances were not
found in JPEG compression, because of the sequential character of
the division of the image in the JPEG algorithm. 
The YIQ colour representation model is used instead of the RGB
model, to exploit easily the human eye's sensibility to colors.
More bits will be assigned to the Y canal, and less for the I and
Q channels. This is very well known in the YIQ model.
For each rang block, the domain block is searched, to resemble
on the Y channel, using the domain blocks of the I and Q
channels when determining the IFS. The domain blocks of I and Q
channels are not necessary the blocks that fit the best, but the
comparison is done only for the Y channel. Therefore, a single
geometric transformation exists for all the three components of
YIQ, while the recalculation of the optim volume transformation
is done for each of the three channels.
It is known under the name of volumetric compression with
fractals. The volumetric compression with fractals divides the
set of tridimensional data in non-overlapped rang blocks. The
domain blocks determination can be done on the same set of
data, in this case being possible to overlap zones of these
blocks.
For each rang block, the decompression algorithm searches for
a domain block and a special transformation to transform the
domain block it the best approximation of the rang block.          
	A complete search of the volumetric volumes includes all the 48 possible isometries, between 2 cubes. This leads to a compression time rather large, compared to the  one realized at the compression of the bidimensional images, where 10 isometries were possible.
An attractive characteristic of the image compression with fractals is the independence towards the decompressed image’s resolution. At decompression, it is not necessary for the decompressed image’s sizes to be the same with the initial image’s ones.
The transformed blocks’ sizes are not part of the compression process. Therefore, they can be changed. If the image is decompressed to a dimension bigger than the original’s one, acceptable details for the human eye are generated by algorithm.
The Barnsley algorithm works better when parallelized or hardware encoded; but, generally, it needs a very large amount of time to compress images. 
The Jaquin algorithm opened the path for research in reducing the search space for similar blocks.
In detail, the transformations applied on an image are:
•	 scaling the domain block to fit the rang block, by reducing from    16x16, to 8x8 or 4x4;
•	 one of the 8 isometries that modifies a block, used to minimize the residual errors between the rang and the domain;
	These two transformations are known as geometric transformations.
•	non-homogeneous scaling of luminosity, which are applied on every pixel from the partially transformed domain block; this transformation is called mass transformation.
•	transformation of the domain block into a mask of the rang block.
	The source programs can be found on pages 297-309.
	Unlike the first three, the images drawing, parrot and photo have a slow regeneration, being recognizable after 8 or 9 iterations.
	The loss of information at compression is about 2-3% for these images, after a compression of 16 iterations.
	The compression rate of the images is 43.75%, with a gaining of 56.25% for memory space, which is comparable with the compression degree obtained when compressing images with compression algorithms without loss of information. The performances of the image compression with fractals algorithms are visible for very large files. For example, for a Targa image file, having 1024x768 size in grayscale, with a length of 786450 bytes, it is obtained a compressed file with the length of 36004 bytes.
	The evolution ascends from one step to another one. The iteration number can increase, and it is possible to identify a number for the wanted compression quality, by repeated trials. Our trials lead to a number of 16 iterations, as performant level.

12. Compression with neural networks
	The data compression by neural networks idea appeared at the end of 1996. Neural networks are used in compression as data filters. In this chapter, an example of implementing neural networks for image compression is presented.
	In the last ten years, a considerable increase of interest in neural networks took place. Why? The first referring to such networks , under mathematical aspect, was in 1943.  An answer could be need to find an alternative to a deadlock situation.
	An artificial neural network is formed by a set of nodes containing artificial neurons, nonlinear processing elements, that operates in parallel. By analogy with the biological neuron, an artificial neuron has a number of inputs and one output, that can connect to more neurons. Each entrance has a certain weight that represents the importance of the impulse presented on the respective line, at the neuron’s activating.
The artificial neuron is a simple copy of the biological neuron. It is formed from a corps, a set of entries and one exit. Each entry is weighted, meaning that its value is multiplied with a value called weight, then all the weighted entries are added.
In comparison with the MLP and Boltzmann systems, that need assistance in the instruction process, the input and the output vectors act on the network’s parameters, these new structures training alone. This type of networks are called self organizing feature maps, SOFM.
In this sub-chapter, here are presented the results of a system of compression algorithms using neural networks, for image compression. The used system is a combination of 2 models: Kohonen and Grossberg networks. 
The networks uses three layers, the first one being the input layer, used to process the image. Every node from the input layer is connected to all nodes from the second layer, called the Kohonen layer. Finally, every Kohonen node is connected to all nodes from the third layer, the Grossberg layer. The links’ weight from these layers are determined by instruction rules, which will be presented.
The compression/decompression process includes the next steps:
a. 	instructing the neurons from the input layer, that is a simple neural network, using a small data set. Generally, these data are loaded before the compression, without loosing time with the instruction.
b. 	instructing the decompression network, that is a neural network similar to the compression one, using the same data set.
c. 	dividing the image in blocks of 4x4 or 8x8 pixels.
d. 	compression each sub-image in 6 or 4 signals by using them as inputs in a compression network.
e. 	transmitting the compressed image to the receival, or storing it.
f. 	rebuilding the initial image with a certain tolerance, measured as rate of noise introduced by signal, with the help of the decompression network.
	To extend these results to image compression with more than two colors, it must be developed a procedure to divide the images, that can be used on colored or gray images.
	To compress or decompress images using neural networks, the image must be decomposed in a finite number of sub-images. Supposing that the original image has NxN pixels, it can be divided in k>0 sub-images with MxM pixels. Each sub-image will be compressed with neural network with m data bits transmitted at reception.
Two neural networks are developed, for compression and decompression, being called compression network and decompression network.
	The number of neurons from the entry layer is MxM, that is compatible with total number of pixels of the sub-image. The number of Grossberg nodes id m, and represents the total number of transmitted bits. The number of Kohonen nodes is equal to the total number of used models in the instruction process of the compression/decompression networks. 
	If an image to be compressed is white-black, the pixel having as value 0 or 1, only, the compression process will be direct. But, if the image has a finite number of gray nuances, it is necessary a method to decompose these images in a certain number of white-black images. This study uses only images with 4 levels of gray. Because a pixel needs only 2 bits to represent the 4 levels of gray, meaning 00, 01, 10, 11, the most significant bit and the less significant bit can be separated, obtaining 2 white-black images.
	These 2 images can be compressed, transmitted and decompressed separately. The combination of these 2 images after decompression will have as result the initial image in 4 gray nuances, or an approximation of it. For images in gray nuances, good results were obtained with backpropagation implementations of neural networks, but these present a great risk to loose information.
	The study of image compression using neural networks presents a new approach in the data compression/decompression field. The process’s quality, right now, is not good. New methods to compress with neural networks must be found. The improvement of the process’s quality can be done by reducing the compression rate. If, instead of using 4 bits strings, a redundancy of 4 bits is assured, it will be enough to obtain a sufficient image quality.
	The main difficulty in the compression/decompression processes using neural networks is to select a small number of instruction models, to reduce the compression/decompression time. The selection of the instruction models is one of future domain of research in data compression. 

13. 	Compression of non-homogeneous files
	The programs and the tools that implements compression algorithms are performant by using differentially the algorithms. An compression algorithm is efficient if obtains comparatively equal compression rates for different sets of files. The algorithms that give good results only for certain types of files, must be used differentially in the compression process.
	To exemplify a classification of the compression algorithms using the files’ homogeneity, 250 different files are processed. The used metrics are the entropy, the file’s length and the entropic indicator.
	The appearance in 1990 of the MS-DOS 6.0 version surprised the users world, by the small number of brought innovations. From the programmers point of view, the single major improvement brought by Microsoft was the DoubleSpace in line compression resident program. 
	Generally, all compression programs, from LhArc to Stacker, considering DoubleSpace, reduce the space occupied by files on disk with the help of 3 algorithms:
•	RLE, Run Length Encoding ;
•	Algorithm Huffman ;
•	Compression Lempel-Ziv, mainly the LZW algorithm.
	To exploit to the best, the available space on disk, DoubleSoace does not register the compressed files after the usual scheme of the DOS file system. They are stored in a compressed volume file CVF. 	This file is fix, starting from the installation of DoubleSpace, occupying the major part of the disk. Beside the compressed files, DoubleSpace stores the data structures necessary to manage the ensemble. DoubleSpace can install more CVF files inside the system: each one can be considered a compressed disk and have its own data structures. A CVF file, eventually under the form of a virtual disk, can have up to 512 MB, uncompressed, and store  up to 1GB of files or more, due to the compression algorithms of DoubleSpace.
	The second limitation is referring to the CVF file’s structure. The DoubleSpace compression techniques must be compatible with this limitation. For example, a DOS program opens a file and sets a pointer to that file at the address 35000, to read a record. Such an operation, that does not create any problems for a standard DOS file, rises real problems. Normally, the record can be found at a distance of 34999 bytes from the first byte.
	Following, the interruptions used by the DoubleSpace will be presented.

15. Compared analysis of algorithms
	There is a great diversity of compression algorithms. The compressions on lots of files use a multitude of algorithm s. The static analysis gives strictness to the algorithm’s classifications and hierarchies.
	There are numerous classifications criteria and an algorithm passed through each of these criteria has defined the characteristics.
	The compression algorithms are:
•	compression algorithm with by a single pass: the file’s compression takes place simultaneous with the reading. These are known as dynamic algorithms.
•	compression algorithms by multiple passing, or static algorithms. At the first passing, the alphabet, the symbols’ frequencies are  analyzed, the repeating strings are identified the next passing individualize the destination alphabet strictly to the particularities of the source file’s alphabet.
	After the differences between the initial file and the expanded one, the next algorithm classes are identified:
•	perfect algorithms, that lead to decompressed files identical with the original file;
•	algorithms with non-significant loss of image. In this case, there are differences between the initial file and the decompressed file, but they can be controlled and accepted.
•	algorithms with errors in the compression/decompression process. In this case, the differences are random.
	The file lots considered depend on the real diversity of files. There are very long, long, medium and small files.
	The biggest file has tens or even hundreds of MB. The long files have dimensions between 1 and 10 MB. Medium files have under 1MB, but over 400KB. The small files are under 400KB.
	In this sub-chapter, a series of indicators will be defined, used in the analysis of the algorithms’ behavior.
	Let’s consider n files, and the compression degrees between 0 and 100. The compression algorithm x is :
•	excellent if the compression average degree is between 0.89 and 1;
•	very good if the compression average degree is between 0.68 and 0.89;
•	good if the compression average degree is between 0.41 and 0.68;
•	medium  if the compression average degree is between 0.23 and 0.41;
•	bad if the compression average degree is between 0.11 and 0.23;
•	very bad if the compression average degree is under 0.11;

16. Tools for compression
	Indifferent how big is your hard disk, there comes a moment when it is full and you do not want to give up any file. Then, you will have 2 solutions: bye another one, but this will fill too, or use compression programs that can save you space and money. The problem is what programs to use. To decide that by yourself, read this chapter.
	To reduce the disproportions between the available and the necessary of memory, there were built compression tools.
	The tools can de characterized by :
•	generality: realizes the compression/decompression of any file. It must be indicated the tool’s name, the new file’s named  the file to be compressed. After compression, a message about the process quality will be printed, along with the compression degree.
•	liability: the program is built so that execution or compression errors  do not occur. For this, it was necessary to test very strictly.
•	continuity: starting from other tools, rules were taken so that the user use the product directly, without restrictions. The parameters’ symbol, separators and their significance given in previous versions must be kept.
•	performance: the compression/decompression speed must be raised, ensuring the framing in accepted limits, that define the real working time of the configuration.
•	protection: all conflict situations are managed by the program.
	The PkZip, Arj, Rar, LhArc and Danar 2.4 SNNS tools are presented.
In the year 1997, a Windows 95 application  was developed, that can run in multitasking. The basic functions of Danar Multimedia Compressor v2.4 for Windows 95 (see figure 16.1.)  are the compression/decompression of files, using a large variety of algorithms. 
	The application is very easy to use, for each option existing an explication presented in the status bar.
	The experimental results from chapter 15 were obtained with this product. On the disk that accompanies the book, the DOS variant of the application is present
With this application, many types of archives can be processed: .zip, .arj, .lha, .rar, .dan. With the option extern link, different types of archives can be compressed/decompressed. It is necessary only to exist in the application’s directory of the product that creates these archives. 
The application is accompanied by a series of tools, that are presented in almost all compression programs. When the computer works with many users, each one can create his option file. The option files have the extension .set, and the verification of its existence can be done using the option: Tools / Restore default settings ... .
	Two archives can be process simultaneously, even if they are different. In the 2 archives, additions, erasures, extractions and even transfers can be done.
	The standard option of the application, existent in most compression programs:
•	creating new archives;
•	opening of an archive, only of the specified type;
•	opening the second archive;
•	exchanging the two archives, if there are two opened archives;
•	closing the archives;
•	information on the archives;
•	information on the files; (double click) ;
•	erasing the files;
•	copying the archives;
•	erasing the archives;
•	adding comments, for each file;
•	saving the comments in comment files, to be used afterwards;
•	introducing passwords, even for every file in the archive;
•	creating autoexpandable archives;
•	presenting step-by-step the compression process;
•	adding files in the archive;
•	extracting files from the archive;
•	erasing files from an archive.

	What the Danar application brings is :
•	selecting a specific compression method, automatically or from the menu: Easy compression; Average compression; High rate compression; Huge rate compression; Fractal compression; Genetic compression; Multiple mode compression; Cryterial compression.
•	selecting a type of file to be compressed: text files,executable files, images, sound files, multimedia compression, video compression, compression with no type, other type of files;
•	transferring files from an archive to another one;
•	listing completely the archives;
•	restoring parameters saved previously, by configuration files;
•	introducing a file analyzer, that can obtain information about the best compression method for selected files;
•	existence of a history of previously archived files;
•	a rapid analysis of files, due to statistic studies made on files;
•	the automatic compression component, that calls the analyzer in the compression phase.
For commercial  variant contact the authors.

Conclusions
	Indifferently how much the supports of information storing develop, their capacity will , always, be insufficient to implement informatics applications.
	Passing from perforated band to magnetic band led to restrictions when using independent files. The pass from magnetic band to disks brought some restriction over the data bases. The development of magnetic disks generates restrictions in the multimedia data base field, the restriction string continuing over the data volume’s complexity and dimensions. An improving solution is to compress/decompress data, consuming a certain time, influenced by the microprocessors’ performances and the transfer rates.
	Therefore, there are outlined algorithm typologies, but the problem of developing new classes remains still open. The elaboration of software destined to compress increases the compression rate.
	The next problems can be identified:
•	establishing the characteristics of the files to compress/decompress and the algorithm with the best compression rate;
•	quantifying the redundancy enclosed in files and using the associate indicators to select the compression algorithms, or even to develop new algorithms;
•	building software that differentiates the compression algorithms, in function of the files’ characteristics; an algorithm is used for image static files, another one for other type of files;
•	developing multicriterial optimization elements (minimization of the space on support and minimization of the compression/decompression time, minimization of the costs);
•	realizing a balance between the stored information and the generated one, by evaluating functions;
•	following the development of algorithms that consider new resources of the systems, cache memory, RAM memory, multiprocessor;
	The compression/decompression problem is more important, since the computer networks are being globalized. 
	To pass from classic documents to images stored on magnetic support requests to specialize the servers, therefore to concentrate homogeneous information.
	Extremely big volumes suppose finding criteria. In this case, the 3 software layers implemented are:
•	interface software, to localize in the network and to find after composed keys, the information (article); this software must be simple and friendly;
•	software to find the information, that takes the dialog elements, localize and extracts the wanted information, in compressed form;
•	software to decompress and process the selected information at the user’s level; this component makes the network data transmission technology liable.
	Indifferently what are the technique performances of the information manipulation in network, the increase of the compression rate remains the same, because:
•	the working stations have limited storing resources and any activity is preceded by decompression/compression of data;
•	the typology of the numerical data file destined to compute the economic indicators, techniques have a small weight in favor to the applications in which the image is very important;
•	the ratio between the transmitted information and the processed one is extremely small;
•	the files’ content, which are transferred, takes without modifications, images of the documents or pictures in raw form, that limits the compression algorithm’s performances.
	The actuality of the compression/decompression as research and development subject is underlined by annual conferences (Data Compression Conference DCC), by launching on the market compression program packages, and by elaboration of standards to store information in files, in concordance with the compression rate.
	There is not an installation kit that does not have compressed files, does  not decompress data with its own, special tools.
	Very powerful tools were developed lately, in informatics, and used for applications in data compression (fractals, neural networks, genetic algorithms).
	It can be noticed the open feature of the domain. But, qualitative and quantitative analysis must be done over entries, exits, transformations specific to the compression/decompression process, and an optim zone must be found. This must minimize the information loss,  maximize the compression rate, minimize the compression time and occupied space.
	Each typology has estimated limits associated. The algorithms are classified and balanced compression/decompression process are created based on them. 
	The software dedicated to these operations does not create data bases regarding the behavior; this must be improved.
	For this, the added components must measure the characteristics of the input files, the resource consume and the exit files. 
	These data bases contribute to adjusting the compression programs’ behavior, by modifying the algorithm selection criteria.
	Ensuring a large circulation of the source texts that correspond to algorithms implementation is a condition to develop data compression applications.
	The practical software becomes complete if it operates with its own compressed files. For example, a programming environment for C++ is complete if it offers, as exit, a compressed source program, if, at compilation, the source text file is decompressed and the object file is compressed, if, at link-editing, the object file is decompressed and the executable file is compressed, and, at execution, the executable file is decompressed and run.
	Those compression and decompression functions, at the user’s disposal, must incorporate tools and applications to eliminate the compression/decompression transparency, by commands offered to the user.