Google Answers Logo
View Question
Q: History of Text Compression ( Answered 3 out of 5 stars,   0 Comments )
Subject: History of Text Compression
Category: Computers > Algorithms
Asked by: dejas-ga
List Price: $7.00
Posted: 18 Sep 2003 12:55 PDT
Expires: 18 Oct 2003 12:55 PDT
Question ID: 258094
I'm looking for information concerning the history of text compression
both before and with computers.
Subject: Re: History of Text Compression
Answered By: bio-ga on 18 Sep 2003 13:57 PDT
Rated:3 out of 5 stars

Here is a short summary of the history of text compression. You can
also access more detailed information using the links at the end of
the summary:

One of the earliest forms of text compression is Morse code, which is
invented in 1838. The compression is simply using shorter codes for
more commonly used letters. With the development of information
theory, statistical compression also developed further. In 1949,
Claude Shannon and Robert Fano introduced the method of compressing
the information using probabilities of blocks.

In 1977, Abraham Lempel and Jacob Ziv published a paper with a
different approach to the symbol coding problem. Instead of assigning
codewords to the symbols (or messages) in advance, they assigned
codewords to repeating source words, or patterns in the text. This
method is still the basis of most lossless modern data compression
techniques today.

In 1984, Terry Welch improved the Lempel-Ziv method known as LZ78, and
introduced the method known as LZW. This algorithm is used by
commercial compression softwares such as PKZIP, and by the mainstream
image formats GIF and some versions of TIFF. LZ78 and LZW algorithms
are patented (1981 and 1983, respectively) but they both are
presumably expired.

Lempel-Ziv method has been improved by many auxiliary algorithms, such
as LZSS (Lempel-Ziv-Storer-Szymanski), LZARI (Lempel-Ziv + Arithmetic
encoding), LZH (Lempel-Ziv + Huffman encoding, used in the archiving
softwares LHArc and ARJ).

There are both online and offline resources on the topic:

Data Compression Information

This is a very good site on data compression history, background and

A Brief History of Data Compression

"The late 40's were the early years of Information Theory, the idea of
developing efficient new coding methods was just starting to be
fleshed out. Ideas of entropy, information content  and redundancy
were explored. One popular notion held that if the probability of
symbols in a message were known, there ought to be a way to code the
symbols so that the message will take up less space."

History of Data Compression

Lossless Data Compression

"Lossless compression methods that can't be pinned down to one of the
more refined topics, such as LZW or ZIP. In some cases, the items here
are esoteric algorithms that don't merit their own topics. In other
cases, they span one or more existing topics. The unifying theme is of
course that they are lossless. This means that after compressing and
then decompressing, the data set in quesition will be bit-for-bit

Lempel-Ziv 1977 (LZ77) Coding Algorithm

"The LZ77 coding algorithm also referred to as sliding-window coding
algorithm. It keeps n-Ls last seen symbols (Ls is maximal length of
the string to be coded and n is the size of input buffer) to find the
maximal substring in these n-Ls symbols which is equal to the prefix
of the string to be coded. Then the found prefix is coded by the
position of the found substring, its length and by the first symbol in
the input stream coming after the found prefix. The length of the
found prefix may vary between 0 and Ls-1 and the greater it is the
more coding efficiency is achieved."

Lempel-Ziv 1978 (LZ78) Coding Algorithm

"The LZ78 coding algorithm also referred to as dictionary-based coding
algorithm. Instead of searching for maximal substring among constant
number of last seen symbols which is equal to the prefix of the string
to be coded, as LZ77 does, the underlying idea of LZ78 is to search
for maximal substring among all last seen symbols which is equal to
the prefix of the string to be coded. Hence for infinitely long input
string the position (and therefore the binary representation of it) of
that maximal substring is unbound, thus complicating coding."

Info on LZ77/LZSS and Derivatives

"LZ77 algorithm and its descendant, LZSS. This is one of two seminal
LZ compression algorithms developed in the late 70s. LZSS forms the
core of the popular deflate algorithm when combined with a Huffman
encoder on the back end."

Lempel-Ziv-Welch (LZW) Coding Algorithm

"LZW is a so-called commercial version of LZ78. The LZW algorithm uses
the same principles and ideas as LZ78 does, while adding several
technical improvements over LZ78."

LZW (Lempel-Ziv-Welch) Algorithm

"The key insight of the method is that it is possible to automatically
build a dictionary of previously seen strings in the text being
compressed. The dictionary does not have to be transmitted with the
compressed text, since the decompressor can build it the same way the
compressor does, and if coded correctly, will have exactly the same
strings that the compressor dictionary had at the same point in the

Hope this helps,

Google Answers Resarcher

Search strategy:

"history of text compression"
"data compression" algorithm
"lempel ziv"
dejas-ga rated this answer:3 out of 5 stars

There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy