We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
from I - Classroom-tested Projects
Summary
We investigate the Lempel-Ziv '77 data compression algorithm by considering an analogous algorithm for efficiently embedding strings in binary trees. This project includes a discussion of this comparison with two optional addenda on error correction and decompression, followed by exercises and solutions.
Notes for the instructor
Students in discrete mathematics often have a dual interest in computer science. This project succinctly combines these two areas. Data compression can be viewed as a discrete mathematics topic with many ramifications for computer scientists. Students who have completed one or two semesters of computer science (in particular, who are familiar with trees) may be eager to implement the algorithms discussed in C++, Java, or another object-oriented programming language.
The Lempel-Ziv '77 data compression algorithm was introduced in [1]. Analysis of the multiplicity matching parameter of suffix trees was presented in the present author's Ph.D. thesis; an abridged journal version with many more references to the literature can be found in [3]. An error correcting version of LZ'77 is outlined in [2].
Bibliography
[1] Lempel, A. and J. Ziv. “A universal algorithm for sequential data compression,” IEEE Transactions on Information Theory 23 (1977) 337–343.
[2] Lonardi, S., W. Szpankowski, and M. D. Ward. “Error resilient LZ'77 data compression: algorithms, analysis, and experiments,” IEEE Transactions on Information Theory 53 (2007) 1799–1813.
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.
