Many data compression schemes are developed nowadays and they are
selected according to requirements, such as fast encoding, fast
decoding, good compression performance, small amount of required
memory, etc.  Data compression schemes can be divided into two
schemes: dictionary method and statistical method.  The former encodes
strings to be compressed to indices into a dictionary.  Since it runs
quickly with small memory, it is widely used in compress or gzip
command in unix.  The latter encodes characters one by one according
to the probability of occurrence of characters.  As the speed and
memory of CPU increase, the statistical method becomes available and
the compression performance is improved.  Recently, block sorting
compression and a compression based on context similarity was
developed and the relationship among these two methods and the
previous methods was studied.

In this thesis, improvements of speed and performance of data
compression based on dictionary and context similarity are considered.
Concerning the dictionary method, acceleration of the algorithm for
searching the longest match string used in gzip is considered.
Because gzip uses chaining hash, searching becomes slower if many
collisions occur.  In this thesis, an algorithm using two-level hash
is proposed.  Since longer strings are searched first, the search
space is considerably reduced when they are found in the dictionary.
The compression speed also increases by 30% to 60% for English text
files and becomes three to five times faster for PostScript files of
English papers created by dvi2ps.

The compression scheme based on context similarity is regarded as an
on-line version of the block sorting compression and it is
asymptotically optimal. However, its compression speed is slow and the
real performance is not so good.  In this thesis, recency rank code
with context (RRC), which is a variation of the scheme, is proposed.
The proposed method can be implemented using suffix tree and recency
rank code is realized by move-to-front transformation of edges in the
tree.  The method is faster than the original one and is also
asymptotically optimal.  Moreover, compression performance becomes
better by changing models according to the length of the context and
by combining some characters into a code. However, the proposed method
is still inferior to the block sorting in both performance and speed.
The reason of bad performance was investigated and the relation among
these methods and statistical method became clear.