Amar Mukherjee, Principal Investigator
School of Electrical Engineering and Computer ScienceUniversity of Central Florida
Orlando, FL 32816

Contact Information
Contact Name of PI:
Amar Mukherjee
School of Electrical Engineering and Computer Science
University of Central Florida
Orlando, FL 32816
Phone:  (407) 823-2763
Fax:  (407) 823-5419
Email: amar@cs.ucf.edu

WWW PAGE
http://vlsi.cs.ucf.edu/datacomp/nfs/report/nfsreport.html

List of Supported Students
Nan Zhang,  Graduate Research Assistant
Raja Iqbal,   Graduate Research Assistant
Nitin Motgi, Graduate Research Assistant

Research Collaborators
Dr. Robert Franceschini
Mr. Holger Kruse

Project Award Information

• Award Number:  IIS-9977336
• Period of Performance of the entire project: 10/01/1999 - 9/30/2002 and the award period is 3 years
• Current Reporting Period: 10/01/1999 – 6/30/20
• Title of the Project: Algorithms to Improve Efficiency of Data Compression and Caching on Wide-area Networks.

Keywords
Data Compression, Lossless Compression, Text Compression, Wide-area network, Caching.
 

Project Summary
The goal of this research project is to develop new lossless text compression algorithms and software tools to incorporate compression in MIME/HTML standards. The approach consists of encoding the text to exploit the natural redundancy of a language via the use of a dictionary and then compressing it using a pre-existing compression algorithm. The encoding scheme depends on the specific characteristics of the compression algorithm and the Bzip2 algorithm based on Burrows-Wheeler transform is used as the main backend compression algorithm. A basic understanding of the interaction of the encoding schemes and the compression algorithms is being developed. The performance of the algorithms is being measured taking into account both compression and communication metrics. Infrastructure tools are being developed using dynamic caching of dictionaries to embed compression into MIME/HTML standards. The impact of the research on the future of information technology is to develop data delivery systems where communication bandwidth is at a premium and archival storage is an exponentially costly endeavor. It is expected that the new lossless text compression algorithms will have 3 to 30% improved compression ratio over the best known pre-existing compression algorithms which might translate into a reduction of more than 70% of the text traffic on the Internet. The experimental research is linked to educational goals via rapid dissemination of results via reports, conference and journal papers, doctoral dissertation and master’s thesis, and transferring the research knowledge into the graduate curriculum. Software tools developed under this grant will be shared via a web site.
 

Goals and Objectives
The major goal of the project is to develop data delivery systems where communication bandwidth is at a premium and archival storage is an exponentially costly endeavor. Specific objectives for this period were:

• Development of new lossless text compression algorithms and software tools to incorporate compression in text transmission over the Internet.
• Basic understanding of the interaction of encoding schemes and compression algorithms.
• Measurement of performance of the algorithms taking into account both compression and communication metrics.

Method of Approach
The basic philosophy of our compression algorithm is to transform the text into some intermediate form, which can be compressed with better efficiency. The transformation is designed to exploit the natural redundancy of the language. We have developed a class of such transformations each giving better compression performance over the previous one and all of them giving better compression over most of the current and classical compression algorithms (viz. Bzip2 (based on Burrows –Wheeler Transform), the class of PPM (Partial Predicate Match) algorithms (such as PPMA, PPMC, PPMD, PPMZ and PPM*), Gzip (based on LZW algorithms), Arithmetic and Huffman algorithms). We also measured the execution times needed to produce the pre-processing and its impact on the total execution time is negligible.  The algorithm has a fixed amount of storage overhead in the form of a word dictionary for the particular corpus of interest and must be shared by all the users. Typical size of dictionary for the English language is about 1 MB and can be downloaded using caching and memory management techniques that are being developed for use in the context of the Internet technologies. If the compression algorithms are going to be used over and over again, which is true in all practical applications, the amortized storage overhead is negligibly small and is no more than the backend compression algorithm used after the transformation. Our recommendation is to use the Bzip2 algorithm for backend compression along with our proposed transformation. The combined effect is to produce the best average compression ratio of 2.00 BPC (bits per character) over the Calgary and Canterbury corpus with no appreciable degradation over the execution time or storage overhead. We also have measured the impact of using these algorithms on the transmission time and bandwidth over the Internet for text file transfer using both http and ftp protocols. On the average we established a 500% improvement of transmission time and 70% reduction of bandwidth requirements for streamed text data.
The basic idea underlying the transformations that we invented is that one can replace letters in a word by a special placeholder (*) and retain at most two characters of the original word.  Given an encoding, the original word can be retrieved from a dictionary that contains a one-to-one mapping between encoded words and original words.  The encoding produces an abundance of  * characters in the transformed text making it the most frequently occurring character. The transformed text can be compressed better when all the available compression algorithms are applied except in one case:  the Bzip2 algorithm.  For Bzip2, the run-length encoding step at the beginning destroys the benefit of *-encoding. For Bzip2, we propose three new transformations called Fixed Context Length Preserving Transformation (LPT), Fixed Context Reverse LPT (RLPT) and shortened-context LPT (SCLPT) all of which improve the compression performance and uniformly beat the best of the available compression algorithms over an extensive text corpus.

 Targeted Activities, Summary of Results and Indication of Success
Our activities have been directed to achieve results in all three areas of goals and objectives stated earlier. The major results of our achievements can be summarized as follows.
    1. Performance Measurements of  the Compression Algorithms
          We have implemented the four lossless reversible text compression algorithms (*-encoded, LPT, RLPT and SCLPT)
          as discussed above and measured their compression performance using a combination of the Canterbury and Calgary
          corpus (See Table 1) to do our testing and compared them with the existing algorithms. The results are summarized as
          follows.

          1. When compared to the standard compression algorithms, the *-encoded compression algorithms produce a
              compression improvement of as high as 33% over Huffman and arithmetic algorithms, about 10% over Unix
              compress and 9% to 19% over Gzip algorithms and average 1.7% over Bzip2 and 0.3% over PPMD algorithms.
              The last two algorithms are known to perform the best compression so far in the literature. The improvement over
              Bzip2 algorithms is not always guaranteed because of the effect that we explained earlier. Fig. 1 illustrates typical
              performance results.
 
 

     Figure 1. Comparison of BPC on plrabn12.txt (Paradise Lost) with original file and star converted file using
                     different compression algorithms.

        2. The three new algorithms that we proposed (LPT, RLPT and SCLPT) produce further improvement uniformly over
            the corpus. LPT has an average improvement of 4.4% on Bzip2 and 1.5% over PPMD; RLPT has an average
            improvement of 4.9% on Bzip2 and 3.4% over PPMD. The SCLPT has an average improvement of 7.1% on Bzip2
            and 3.8% over PPMD. The compression ratios are given in terms of average BPC (bits per character) over our test
            corpus. The results of comparison with Bzip2 and PPMD are shown only. As can be seen from this table, our results
            indicate the best average BPC of 2.147 which beats the best results available in the literature. See Table 2, Fig.2 and
            Fig.3.
 

                           Table 2. Average BPC over the corpus with Original, Star-encoded, LPT, RLPT, and SCLPT using
                                          Bzip2 and PPMD.
 

2. Execution Time Measurements
In making average timing measurements, we chose to compare with the Bzip2 algorithm, which so far has given one of the best compression ratios with lowest execution time. We also compare with the family of PPM algorithms, which gives the best compression rations but are very slow.

• The *-transform plus Bzip2 on our corpus is 6.32 times slower than without the transform. However, with the file size increasing, the difference is significantly smaller. It is 19.5 times slower than Bzip2 for a file with size of 11,954 bytes and 1.21 times slower for a file size of 2,736,128 bytes.
• The LPT plus Bzip2 on our corpus is 6.7 times slower than without the transform. However, with the file size increasing, the difference is significantly smaller. It is 19.5 times slower than Bzip2 for a file with size of 11,954 bytes and 1.39 times slower for a files size of 2,736,128 bytes.
• The RLPT plus Bzip2 on our corpus is 6.44 times slower than without the transform. However, with the file size increasing, the difference is significantly smaller. It is 19.67 times slower than Bzip2 for a file with size of 11,954 bytes and 0.99 times slower for a files size of 2,736,128 bytes.
• The SCLPT plus Bzip2 on our corpus is 4.69 times slower than without the transform. However, with the file size increasing, the difference is significantly smaller. It is 14.5 times slower than Bzip2 for a file with size of 11,954 bytes and 0.61 times slower for a file size of 2,736,128 bytes.

Note the above times are only for encoding and one can afford to spend more time off line encoding files, particularly if the difference in execution time becomes negligibly small with increasing file size which is true in our case. Our initial measurements on decoding times show no significant differences.

When we compared the average execution times with PPMD, the results are as follows:

• The *-transform plus PPMD on our corpus is 18% slower than without the transform.
• The LPT plus PPMD on our corpus is 5% faster than without the transform.
• The RLPT plus PPMD on our corpus is 2% faster than without the transform.
• The SCLPT plus PPMD on our corpus is 14% faster than without transform.
• In general, SCLPT runs fastest among all the PPM algorithms

                      Original:
 

                     Star-transform:
 

                         LPT
 

                        RPT
 

                       SCLPT
 

                             Table 3. Statistics of compressions in different context order for alice.txt with PPMD
 

2. Explanation of Observed Compression Performance
Recent research [A3][A4] shows that both the BWT and PPM algorithms explore the representation of context in the text either implicitly or explicitly. The longer and more deterministic the context is, i.e., higher order context, the higher is the probability estimation of the next predicted character leading to better compression ratio. All our transforms aim to create such contexts. Table 3 gives the statistics of the context for the sample text “alice.txt” using PPMD, as well as our four transforms along with PPMD. The first column is the order of the context. The second is the number of input bytes encoded in that order. The last row is the summation of all the bytes compressed at different context levels, namely, the file size. The third column is the cumulative percentage of column two. The fourth is the final number of bits used to encode all the input in that order. The fifth column shows the cumulative frequency of column four. The sixth is the corresponding bytes for bits statistics. The seventh is the compression ration of that order and the last column shows the BPC in that order.
Table 3 shows that length preserved transforms (*, LPT and RLPT) result in a higher percentage for high order contexts than the original PPMD algorithm. The advantage is accumulated in the different orders to gain an overall improvement. Although SCLPT has a smaller value of high order context compressions, it is compensated by compression on the deterministic contexts beforehand that could be in a higher order with long word length. We are continuing to research the precise relationship between the statistics of different order context and the overall compression ratio.
 

3. Compressed Data Delivery via the Internet
 Due to the increased growth in the traffic (refer to Table 4 from the NSF Website) there is a need to compress data transferred over the network. If not, growth would lead to congestion, drowning the Internet with the amount of data in transition.  Web browsing, FTP transfers and electronic mail generate most of the traffic on internet, which transfer basic text code as payload (viz., HTML, plain/text part in mails) with additional payloads of different formats (like attachments, inline images, word processing documents, etc.). One of the objectives of our project is to minimize the part of the basic payload that is plain text.  Reduction in text data transfer over the Internet will help in using the bandwidth for other types of data (like video and audio) transferred on the Internet. In our research, we incorporated new lossless text compression algorithms into file transfers that are made over some of the standard network protocols e.g., FTP, HTTP, POP3 and SMTP. These algorithms will be implemented as a part of the standard protocols defined at Session-Application layer over the transport layer in the OSI Model. The compressed file is transferred over the TCP/IP Network (official protocol for the Internet).
 

                                          Table 4. Current and Projected transfer over Internet in Gigabits/sec
                                             (The data transfer include normal text, image, video and audio)
 

We are in the process of testing the above method for different compression/decompression methods, which have performed 3% to 30% better than standard compression algorithms (viz. Huffman, arithmetic, LZW, DMC, PPM*, BWT) under different network conditions and server loads. We will be evaluating several performance metrics like payload transform time (includes transformation and compression), payload transfer time and payload reverse transform time (includes decompression and reverse transformation). During the transfers there are different other parameters that will be evaluated, such as server performance, bandwidth use over high and low bandwidths.  These tests will reflect the overall performance in the transfer of files over the Internet.  We will be also looking into designing a protocol for managing a dictionary on the clients. This management should incorporate some of the features like dictionary update and propagation, different dictionaries for different languages and should also have versioning capabilities.

As for the initial stages in this approach we have procured all the material needed and have built the infrastructure that is necessary to start. We are developing a real-time compression test facility, which will be capable of testing encoding/compression algorithms for the above-mentioned parameters and for different standard protocols like FTP, HTTP, POP3 and SMTP. This facility will log different parameters mentioned above plus some miscellaneous information, which can be later used to evaluate the performance of the compression algorithms on text transfers over Internet.

The basic test facility has been developed to perform Internet transfers using FTP. The results obtained from this are very promising. The transfers were initiated by normal FTP clients from people on the same network as well as from different networks. These networks are at different distances from the location where the server runs. The compression method is employed on the server and we used the Bzip2 algorithm for compression as a starting point without any of the transforms RPT, LPT or SCLPT.  Results of the test runs are shown in Table 5.

As we can see in Table 5, the size of the files transferred is in the range of 0.3KB to 500KB. Our method always shows improvement in the transfer even if we include time involved in compressing the data. In one example, the size of the uncompressed data transferred is 3420.72 Kbytes and time taken to transfer that amount of data is 458.057 sec. When the same data is compressed and transferred, total data transferred is 743.097 Kbytes and time taken is 50.17sec. The time taken to compress 3420.72 Kbytes of data is 5.971sec (server was assumed to slightly loaded). Hence, 2677.63Kbytes of data transfer and (458.057 – 50.17 – 5.971) sec = 401.916sec was saved.  If we used any of the transforms mentioned earlier we will spend some amount of time in applying the transform but will gain in reducing the transmission time since data is much more compressed
 

FileName	Station Name	Size in KBytes	Type (N or C)	Payload Transformation Time (Transformation Time, Compression Time)	Transfer Time in sec
testfile1.txt	LAB	481.862	N	0.000, 0.000	35.456
testfile1.txt	LAB	145.076	C	0.000, 1.448	4.079
testfile1.txt	LAB	145.076	C	0.000, 0.000	4.349
testfile1.txt	LAB	481.862	N	0.000, 0.000	36.185
Server.c	LAB	2.061	C	0.000, 0.043	0.371
Server.c	LAB	4.547	N	0.000, 0.000	1.114
Ftpcomp.c	LAB	11.097	N	0.000, 0.000	0.877
Ftpcomp.c	LAB	3.719	C	0.000, 0.069	0.184
Logfile.c	LAB	0.377	C	0.000, 0.010	0.571
Logfile.c	LAB	0.655	N	0.000, 0.000	1.255
testfile1.txt	ENG	145.076	C	0.000, 1.348	10.990
testfile1.txt	ENG	481.862	N	0.000, 0.000	70.028
server.c	ENG	4.547	N	0.000, 0.000	1.798
server.c	ENG	2.061	C	0.000, 0.046	0.588
ftpcomp.	ENG	11.147	N	0.000, 0.000	4.156
ftpcomp.c	ENG	3.719	C	0.000, 0.072	0.532
server.c	FSC	2.061	C	0.000, 0.042	0.481
server.c	FSC	4.547	N	0.000, 0.000	0.775
ftpcomp.c	FSC	3.719	C	0.000, 0.069	0.734
ftpcomp.c	FSC	11.147	N	0.000, 0.000	0.910
testfile1.txt	FSC	481.862	N	0.000, 0.000	16.916
testfile1.txt	FSC	145.076	C	0.000, 1.368	4.859
testfile2.txt	FSC	963.723	N	0.000, 0.000	145.164
testfile1.txt	IND	145.076	C	0.000, 1.456	22.432
testfile1.txt	IND	481.862	N	0.000, 0.000	143.423

Table 5: Payload transformation and transmission using Bzip2 compression algorithm at the server. Three stations were used: LAB located at UCF, FSC stands for Florida SolarEnergy Center, and IND is a place located in India. N= not compressed, C=Compressed.

Project Impact
We expect that our research will impact the future status of information technology by developing data delivery systems where communication bandwidths is at a premium and archival storage is an exponentially costly endeavor. We have developed new lossless text compression algorithms that have 3 to 30% improved compression ratio over the best known pre-existing compression algorithms which might translate into a reduction of more than 70% text traffic on the Internet.  We are developing software tools to include compression in standard Internet protocols, and we are planning to automate dynamic caching interaction with web browsers, e-mail programs and authoring tools.
We have taught (in the spring 2000 semester) a new course entitled "Multimedia Compression on the Internet": http://www.cs.ucf.edu/courses/cap5937-01/. This is a graduate level course with 14 students enrolled in the Spring 2000 semester.  This particular topic has grown directly out of the research that we have been conducting for the last couple of years on data compression.  Lecture topics have included both text and image compression, including topics from the research on the current NSF grant.
So far three Ph.D. students and five Masters students have participated and contributed in this research project, but not all of them received direct support from the grant. Dr. Robert Franceschini and Mr. Holger Kruse made significant contributions in the project before it was officially funded by NSF. Currently, one Ph. D. student (Nan Zhang ) and two Masters Students (Nitin Motgi and Raja Iqbal) are working on the project. Another Master student (Fauzia Awan) did a term project in the graduate course “Multimedia Compression on the Internet” directly related to this research project. Other members of the M5 Research Group at the School of Electrical Engineering and Computer Science, Dr. Kunal Mukherjee, Tao Tao, and Piyush Jamkhandi, made critical comments and observation during the course of this work.  The overall effect of these activities is to train graduate students with the current research on the forefront of technology.
 

Project References
This work was started several years ago; two early papers that established this work are the following:
  1. R. Franceschini and A. Mukherjee.  "Data Compression Using Encrypted Text", Proceedings of the Third Forum on Research and Technology, Advances in
      Digital Libraries, ADL96, May 13-15 1996, pp 130-138.
  2. H. Kruse and A. Mukherjee.  "Data Compression Using Text Encryption", Proceedings of the   Data Compression Conference, 1997, IEEE Computer Society
      Press, pp. 447.

We have submitted a journal version of a paper [1] and two other papers [2,3] are under preparation for submissions to conferences in the near future. Copies of these papers will be made available via our project website and also by hard copy
1. R. Franceschini, H. Kruse, N. Zhang, R. Iqbal and A. Mukherjee, “Lossless, Reversible Transformations that Improve Text Compression Ratios”, submitted to
    IEEE Transactions on Multimedia Systems (June 2000).
2. F. Awan, R. Iqbal and A. Mukherjee, “ A New Text Preprocessing Algorithm for Bzip2 and PPM*” (in preparation).
3. N. Motgi and A. Mukherjee, “ High Speed Text Data Transmission over Internet Using Compression Algorithm” (in preparation)

Area Background
In the last decade of the 20th century we have experienced an unprecedented increase in the amount of digital data transmitted across public networks, in particular across the Internet. Recent standards such as the World Wide Web, HTTP, HTML and image standards have provided free access to a vast amount of information available from public servers. With the continuously increasing use of the Internet the efficient use of available resources, in particular hardware resources, has become a primary concern. One way of improving performance is by compressing and caching data, i.e. by ensuring that data is not sent more often than necessary, that as little data is sent in response to each request as possible, and that all data transmitted across networks is compressed during transmission, to increase the efficiency by which the existing infrastructure is utilized.  This proposal is concerned with integrating new data compression and caching techniques for improving the efficiency of bandwidth-limited Internet.  We propose new algorithms to preprocess text in order to improve the compression ratio of textual documents, in particular online documents such as web pages on the World Wide Web.  We also develop similar techniques for images that do not change with time. We describe how our algorithm can be efficiently used to aid in the compression of documents consisting of large texts and static images, for transmission across public data networks such as the Internet, using existing standards such as HTTP and HTML. The compression algorithms also can be used to utilize archival storage effectively.  Our approach integrates the two basic ideas of compression and caching into a single mechanism, i.e., data is automatically cached whenever possible, avoiding retransmission altogether, and if data has to be transmitted, it is compressed in a very efficient way, which surpasses the performance of compression algorithms that are widely used at this time.
 

Area References
A1. I.H. Witten, A. Moffat, and T.C. Bell.  Managing Gigabytes.  2nd Ed, Morgan Kaufmann, 1999.   Managing Gigabytes Web Site
A2. K. Sayood.  Introduction to Data Compression.  2nd Ed, Morgan Kaufmann, 2000.  Introduction to Data Compression Web Site
A3. J. Cleary, W. Teahan, Unbounded Length Contexts for PPM, The Computer Journal, Vol. 36, No. 5, 1993. (Also see Proc. Data Compression Conference,
      Snowbird, Utah, 1997)
A4. Michelle Effros, PPM Performance with BWT Complexity: A New Method for Lossless Data Compression, Proc. Data Compression Conference, Snowbird,
      Utah, March, 2000

Potential Related Projects
There is an ongoing research project under the supervision of the Principal Investigator on Wavelet Based Image Compression and Transmission supported by Intel Corporation. A research proposal on this subject is under preparation for submission to NSF in the near future.