WHAT IS HIDDEN IN AN INDIVIDUAL SEQUENCE ?
UNIVERSAL DATA-COMPRESSION REVISITED
ABSTRACT
We consider the case where consecutive blocks of N letters of a semi-infinite,
, finite-alphabet
individual sequence X are being compressed into binary sequences by some one-to-one
mapping.
No a-priori information about X is available at the encoder, which must therefore
adopt a
universal data-compression algorithm.
It is known that if the universal LZ77 data compression algorithm is successively
applied to
N-blocks, then the best error-free compression, H(X), for the particular individual
sequence X is
achieved as N tends to infinity.
We discuss the best possible compression H(X,N) that may be achieved by ANY universal
data
compression algorithm for finite N-blocks, and demonstrate that context tree
coding essentially
achieves the optimal H(X,N).
Possible extentions to cases were some distortion is allowed and were side-information
is available
at the decoder are introduced.
Jacob Ziv – A brief Biography
JACOB ZIV was born in Tiberias, Israel, on November 27, 1931. He received the
B.Sc., Dip. Eng., and M.Sc. degrees, all in Electrical Engineering, from the Technion—Israel
Institute of Technology, Haifa, Israel, in 1954, 1955 and 1957, respectively,
and the Sc.D. degree from the Massachusetts Institute of Technology, Cambridge,
U.S.A., in 1962.
From 1955 to 1959, he was a Senior Research Engineer at the Scientific Department,
Israel Ministry of Defense, where he engaged in research and development of communication
systems. From 1961 to 1962, while studying for his doctorate at M.I.T., he joined
the Applied Science Division of Melpar, Inc., Watertown, MA, where he was a Senior
Research Engineer doing research in communication theory. In 1962 he returned
to the Scientific Department, Israel Ministry of Defense, as Head of the Communications
Division and also served as an Adjunct of the Faculty of Electrical Engineering,
Technion—Israel Institute of Technology. From 1968 to 1970 he was a Member of
the Technical Staff of Bell Laboratories, Inc., Murray Hill, NJ. He joined the
Technion full time in 1970 where he is now the is Herman Gross Professor of Electrical
Engineering and a Technion Distinguished Professor.
He was Dean of the Faculty of Electrical Engineering from 1974 to 1976 and Vice
President for Academic Affairs from 1978 to 1982.
From 1977 to 1978, 1983 to 1984, and 1991 to 1992 he was on Sabbatical leave
at the Information Research Department, Bell Laboratories, Murray Hill, NJ, USA.
He was the Chairman of the Israeli Universities Planning and Grants Committee
from 1985 to 1991. (The Planning and Grant Committee is the interphase between
The Government of Israel and the Universities; it prepares the budget, presents
it to the government and allocates it to the Universities; it is in charge of
development and means and practices in the Universities.)
He is a Member of the Israel National Academy of Sciences and Humanities and
has served as its President from 1996 till 2005.
His research interests include data-compression, information theory and statistical
communication.
Honours and Awards
Honours
-
Herman Gross Professor of Communications
-
Technion Distinguished Professor, 1982.
-
Fellow, IEEE
-
Member of the Israel Academy of Sciences, 1982;
-
Foreign Associate Member of the US National Academy of Engineering, 1988.
-
The IEEE Information Theory Society held the IEEE International Workshop on Information
Theory in Haifa on the occasion of Jacob Ziv’s 65th birthday,
-
Foreign member of the American Academy of Arts and Science, 1998 Member of the
American Philosophical Society, (2003)
-
Foreign member of the American Philosophical Society, 2003
-
Member of the European Academy of Sciences and Arts 2004
-
Foreign Associate Member of the US National Academy of Science 2004
Awards
-
“The Rate Distortion Function for Source Coding, with Side-Information at the
Detector” – see paper No. 33. Received the IEEE Information Theory Group Best
Paper Award for the year 1976.
-
“A Universal Algorithm for Sequential Data-Compression” – see paper No. 36. Received
the IEEE Information Theory Group Best Paper Award for the year 1977.
-
Israel Prize in Exact Sciences (Engineering and Technology) 1993.
-
Marconi International Award 1995
-
IEEE Richard W. Hamming Medal 1995.
-
IEEE Information Theory Society Shannon Award for 1997.
-
ACM 1997 Paris Kanellakis Theory and Practice Award.
-
1998 Eduard Rhein Prize for Basic Research
-
2002 Rothschild Prize for Technological Sciences
