טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentShapiro David
SubjectGeneralization and Efficient Realization of the HZ
Universal Data Compression Algorithm
DepartmentDepartment of Electrical Engineering
Supervisor Research Professor E Jacob Ziv


Abstract

A compression algorithm with limited memory was suggested by Prof. Jacob Ziv and Yehuda Hershkovits (HZ algorithm), based on context matching. It was later shown by Ziv that the HZ approaches general universal lower bound on universal compression with limited training data.

The algorithm presents efficient compression scheme for moderate as well as long sequences based on context matching. An efficient implementation of this algorithm was performed by Zeev Cohen using block coding length of one symbol.

This work deals with further research regarding the implementation of HZ algorithm and relies on work performed by Zeev Cohen. While prior works deal with single symbol coding, this work investigates the influence of encoded block length on compression results. These work also describes existing vastly used schemes emphasis on algorithmic, functional and performance comparison of these schemes.

A new compression scheme is suggested incorporating combined one symbol and two symbol block coding. The data structure and simulation codes are based on Zeev Cohen work and allow coding and decoding using HZ algorithm in relatively small number of operations.