An approach to phrase selection for offline data compression.
Recently several offline data compression schemes have been published that expend large amounts of computing resources when encoding a file, but decode the file quickly. These compressors work by identifying phrases in the input data, and storing the data as a series of pointer to these phrases. This paper explores the application of an algorithm for computing all repeating substrings within a string for phrase selection in an offline data compressor. Using our approach, we obtain compression similar to that of the best known offline compressors on genetic data, but poor results on general text. It seems, however, that an alternate approach based on selecting repeating substrings is feasible.
Introduction
If data is to be stored on CD, DVD or in a static
database it will be compressed once, but often decompressed
many times. Given this scenario, a compression
scheme can aord to spend several hours of
computing time, make multiple passes over the input,
and consume many megabytes of RAM during the
compression process in order to make the compressed
representation as small as possible. Decompression,
however, should be both fast and memory e-cient.
Such a compression scheme is said to be oine.
One way to meet the demand for fast decoding
and high compression levels is to identify a suitable
phrase book such that the input data can be stored as
a series of pointers to entries in the phrase book. For
example, Figure 1 shows how the simple string \How
much wood can a woodchuck chuck if a woodchuck
could chuck wood?" is compressed using three different
phrase books. The rst representation favours
phrases that appear frequently in the string, hence the
space character forms a phrase by itself. The second
representation looks to include the space character at
the start or end of a word to form a phrase. The
third greedily chooses the longest repeating phrase
that it can, which is similar to the strategy employed
in compressors based on the LZ77 schemes
1977], such as gzip, winzip, and pkzip.
In the nal le both the phrase book and the series
of pointers must be stored. It is di-cult to tell by inspection
of our example which of these three phrase
books will yield the best compression. The phrase
book in representation 1 contains only 27 characters,
but has 26 pointers. The phrase books in representation
two and three have more characters in their
Copyright c
2001, Australian Computer Society, Inc. This paper
appeared at the Twenty-Fifth Australasian Computer Science
Conference (ACSC2002), Melbourne, Australia. Conferences
in Research and Practice in Information Technology, Vol.
4. Michael Oudshoorn, Ed. Reproduction for academic, not-for
prot purposes permitted provided this text is included.
phrase books, but signicantly less pointers. Unfortunately
the variables involved in choosing a phrase
book are much more complicated than merely the
number of pointers and number of characters in the
phrase book. Assuming that some sort of statistical
coder (for example, Human coding or arithmetic
coding) will be used to actually encode the pointers
and the phrase book, the frequency distribution or
self entropy of the two components are better indicators
of the tness of a phrase book. In this particular
example, the cost of a zero-order Human code on
characters in the phrase book and pointers in the data
portion, shown in the last row of the Figure 1, indicates
that the rst phrase book leads to the smallest
representation of 21 bytes. Even these calculations
are only an approximation of the nal compression
levels obtained with a code of this nature as necessary
information that describes the Human codes
employed (a prelude) is not included in these estimates

Oine compression through the use
of a phrase book is not a new idea
[Rubin, 1976, Storer & Szymanski, 1982,
Nevill-Manning & Witten, 1994], but with the
increased availability of cheap, powerful computers,
computationally intensive techniques are now viable
during encoding in order to improve compression
levels through the construction of good phrase books.
The task of identifying the best possible phrase book
on any input has been shown to be NP-complete
[Storer & Szymanski, 1982], but using heuristics and
a lot of machine power, compression levels superior
to alternate techniques have been achieved on some
data sets.
Nevill-Manning & Witten introduced an
approach that induces a context free
from the text, using their grammar rules
to describe the phrase book for compression
[Nevill-Manning & Witten, 1994]. Both Larsson &
Moat and Cannane & Williams explore the use
of repeated pairing of characters in order to build
a phrase book, with the emphasis on small and
large data sets respectively [Larsson & Moat, 2000,
describe an e-cient algorithm for nding long
repeating substrings to place in the phrase book
[Bentley & McIlroy, 1999].
This paper expands on work of Apostolico &
Lonardi. Recently they introduced the Offline
compressor [Apostolico & Lonardi, 2000], which calculates
a measure of compression gain for all possible
non-overlapping substrings of a string. A high gain
factor indicates that if the substring was to be chosen
as a phrase for the phrase book, good compression
would result. Similarly, a low gain score for a sub-string
indicates that the particular substring should
not be chosen as a phrase in the phrase book. The
compression algorithm used in Offline is outlined in

Figure

2.
Representation 1 Representation 2 Representation 3
How much 1 How much 1 How much 1
wood 3 could 3 c 3
2 a woodchuck 4 ould 4
could 4 chuck 5 a 5
a 5 a woodchuck 4 chuck 6
could 3 c 3
wood 3 chuck 5 huck 7
chuck 6 wood 2 if 8
chuck 6 wood 2
chuck 6
ould 4
a 5 c 3
wood 3 wood 2
chuck 6 ? 9could 4chuck 6wood 3
Phrases 12
Pointers 9 4 8
Total

Figure

1: The string \How much wood could a wood-
chuck chuck if a woodchuck could chuck wood?" represented
with three possible phrase books. The rst
occurrence of each phrase is shown in gray for each
case, and are numbered in order of rst occurrence.
The nal three rows show the cost of Human encoding
the phrase book and pointers in bytes.
As alluded to in the above example, calculating
the exact gain in compression for any given substring
is a di-cult task. At the commencement of encoding
there is no way of knowing how many phrases will
end up in the phrase book, or what the probability
distributions of characters in the phrase book or
pointers in the data component will be. Accordingly,
Apostolico and Lonardi experimented with three
approximate gain formulations. Using this simple approach
they achieve excellent levels of compression on
some genetic sequences, and competitive compression
levels on general data [Apostolico & Lonardi, 2000].
Details of their results can be found at
www.cs.purdue.edu/homes/stelo/Off-line/.
The implementation of Offline relies on a su-x
tree data structure, which is a trie that holds all
possible su-xes of a string [Ukkonen, 1995, and
references therein].
As they acknowledge, however, a su-x tree is a
large and slow data structure for this task. In this
paper we introduce an alternate approach for performing
compression using the Offline algorithm,
based on a string processing algorithm for nding all
repeating substrings in a string. By focusing only on
the repeating substrings, rather than all su-xes of a
string, we hypothesise that the time taken to perform
gain calculations and string manipulations using the
Offline approach can be signicantly reduced.
Section 2 describes Crochemore's algorithm
[Crochemore, 1981] for nding repeating substrings
INPUT String to compress.
Calculate the gain for all possible
non-overlapping substrings of the
input string to be compressed.
Choose the substring with the
highest gain factor, and add it to
the phrase book.
Step 3 Remove all occurrences of the chosen
substring from the string, and
store a pointer to the original
phrase for each occurrence.
Step 4 Recalculate the gain measure for
all substrings of the input string
that have not been covered by a
chosen phrase.
Step 5 While there is still a positive gain
factor, repeat from Step 2 on the
remaining uncovered string.
OUTPUT Phrase book and list of pointers
representing the input string.

Figure

2: The basic algorithm employed in Offline.
within a string, and explains how we use it to select
phrases in our oine compression scheme, Crush.
Section 3 describes experimental results for both compression
levels and timing for Crush and Offline.
Finally, Section 4 discusses our results, and their implications

The Crush compressor consists of two stages. The
rst analyses the input string using Crochemore's algorithm
to generate a two dimensional array C, which
stores information on all substrings up to a given
length. This data structure is then traversed to calculate
a gain measure for all substrings occurring in the
leftmost uncompressed position of the input string,
and the highest gain substring is chosen for the phrase
book. Note that this approach deviates from the Offline
algorithm as we make a local choice at the left-most
uncovered position, rather than a global choice
over all possible uncovered positions remaining in the
string. These two stages are explained in detail in
the following two subsections, and summarised in Figure
3.
2.1 Stage 1|String analysis
Crochemore's algorithm [Crochemore, 1981] for nd-
ing all repeating substrings in an input string begins
by grouping all positions in the string that have
the same character into a single class. Each of these
classes is then rened into subclasses to get repeating
substrings of length two. In turn these classes are
rened to get substrings of length three, and so on.
For example, consider the input string
a a b a b a a b a a b:
The positions that form the initial classes for strings
of length one are
a b
This rst stage can be accomplished in O(n) time,
where n is the number of characters in the input
string, assuming that the alphabet from which characters
of the string are drawn is indexable (for exam-
ple, ASCII).
The next stage of the algorithm splits each class
into classes that represent the starting position of sub-strings
of length two. The rst class, a, splits into the
classes aa and ab, and class b splits into the classes
ba and b$, where $ is the \end of string" symbol:
ab aa ba b$
Using a nave approach, this stage can be accomplished
in (n) time, simply by checking the character
following each position in each class. For example,
in order to rene class
a
it would be necessary to check positions
of S. In this case
a and
so f3; 8; 11g must form the class for aa, and
forms the class for ab.
The process of renement continues, ignoring any
class that contains only a single position, as that must
not represent a substring that repeats, until no rene-
ments are possible:
ab aa ba
aba aab baa
abaa aaba baab
abaab baaba
abaaba
If the nave approach to renement is adopted at
each stage, then the total running time is O(n 2 ), as
there could be O(n) levels, each requiring (n) time.
Crochemore oers two insights that allows this time
to be reduced to O(n log n) [Crochemore, 1981].
The rst is that it is not necessary to refer back
to the original string S in order to rene a class; the
renement can achieved with respect to other classes
at the same level. In order for members of a class
in level L to be rened into the same class in level
must share the same character in their
L+1st position. The nave approach checks this character
directly in S for each class member. However,
if members of a class share the same L + 1st char-
acter, their length L su-xes must also be identical.
For example, substrings aba that all have a b in the
next position share the three character su-x bab. For
these substrings of length to share a su-x of
length L, their positions plus one must all appear in
another class at level L.
For example, if the substring aba occurs in position
i, and the substring baa occurs in position
taking into account the overlap of the two character
su-x of aba and the two character prex of baa, we
can deduce that the string abaa must occur at positions
i. This is precisely what happens when rening
the class for aba = f1; 4; 6; 9g at level 3. We can
check which of the positions f2; 5; 7; 10g fall in the
same class on level 3, and deduce that such strings
form a class at level 4. In this case, 2, 7, and 10 all
inhabit the class baa, so f1; 6; 9g forms a class at level
4. Similarly, f5g is in a class of its own on level 3, so
f4g forms a class at level 4.
This observation alone does not reduce the running
time of the algorithm, but when used in conjunction
with the observation that not all classes
need be rened at each level, the running time comes
down. Consider again the example of rening
9g at level 3 into classes on level 4. How many
other classes on level three do we need to inspect in
order to perform this renement? As discussed above,
each of the other classes must have a prex of ba so
that it overlaps with the su-x of aba. If we inspect
the renements that took place on level 2 to produce
level 3 we see that the class
split into 2 classes on level 3, namely
and f5g. These are precisely the two classes we
need to consider when rening 9g. This
in turn means that if we use one of them to perform
the renement of aba = f1; 4; 6; 9g, the remaining positions
must fall into the other class at level 4. In
this case we can either rene f1; 4; 6; 9g using f5g,
to get a class f4g and a remaining class of f1; 6; 9g,
or we can rene f1; 4; 6; 9g using f2; 7; 10g, to get a
class f1; 6; 9g and a remaining class of f4g. Obviously
we should choose the smallest classes against which
to rene, leaving the largest class as the \left over",
with no processing required. This is precisely the approach
adopted by Crochemore's algorithm; at each
stage only the \small" classes are rened.
Observe that when a class at level L is rened into
two or more classes at level L + 1, the longest of the
smallest classes cannot be greater than half of the size
of the parent class. So any character in a string can
appear in a \small" class at most O(log 2
n) times,
hence can only be involved in a renement O(log n)
times. Seeing as there are n characters, the overall
running time of Crochemore's algorithm is O(n log n).
This very brief description of the intuition behind
Crochemore's algorithm hides some of the complex
and intricate details required to achieve a fast, memory
e-cient implementation of this algorithm. The
implementation used in this paper operates in O(n)
space, storing only a list of classes for each level of
renement, discarding lists from previous levels. The
constant factor is quite high in this space bound, with
the current implementation requiring 44n bytes of
memory.
2.2 Stage II|Phrase selection
In order to use the results from Crochemore's algorithm
for phrase selection, our current implementation
of Crush stores the class information for each
level as it is derived. As memory conservation during
encoding is not a primary aim of Crush, a simple
array of n integers is used to hold a circular list of
class members for each level. More formally, element
C[L][i] of array C is a pointer to the next member
of the class containing position i on level L, with the
nal class member pointing back to the rst member.
In the above example of Crochemore's algorithm, C
would be:
The number of levels is restricted to K, a parameter
to Crush, so total space requirement for C is O(Kn).
Once array C exists, phrase selection can begin.
Unlike Offline, Crush makes its phrase selections
out of the set of substrings beginning at the leftmost
uncovered position which do not overlap an already
covered position. The offline compressor, however,
considers all possible non-overlapping substrings at
each phrase choice. Crush chooses the phrase p with
the highest gain measure G p out of the set of possible
substrings. If G p  0 then the character at the uncovered
position is skipped, and left to a nal stage
of processing. The nal stage simply treats all uncovered
characters as single letter phrases with innite
stores the single letter in the phrase book
and its uncovered occurrences as pointers.
reported that computing G p
as the cost of storing all occurrences of a phrase
with a zero-order character model less the cost of
storing a single copy and a series of pointers to
the copy gave the best results in their experiments
Accordingly, Crush
uses a similar gain measure.
Let H be the cost in bits of storing a single character
in the input string. Using a simple character
based model and a statistical coder (for example,
Human coding or Arithmetic coding), H would be
around 2 to 3 bits, while an ASCII code has
Quantity H can be estimated by a preliminary scan
of the data which records the probability of each
character, setting
which is Shannon's lower bound on compression levels
[Shannon, 1948]. This is the approach adopted by
Crush.
Let f p be the frequency with which phrase p occurs
in the text, and l p the number of characters in
phrase p. The cost of storing the f p copies of phrase
uncompressed in the text is approximated by Hf p l p
bits. If phrase p is chosen for the phrase book, one
copy is required at a cost of approximately Hl p bits
for the phrase, plus H bits to store either the length
of the phrase, or a terminating symbol for the phrase,
in the phrase book. Apart from the phrase book
copy of p, it is also necessary to store f p pointers
to that phrase. The cost of a pointer to the new
phrase can be estimated by dlog 2
is the number of phrases already in the phrase book
2000]. This is not a very accurate
estimate of pointer cost as it amounts to the
cost of a
at binary code for the pointers currently in
the phrase book. Of course as Crush continues, P ,
the number of phrases will increase, and so the net effect
is to slowly make the cost of adding a phrase more
expensive. The total gain in compression if phrase p
is to be included in the phrase book, therefore, is:
uncompressed representation
phrase book entry cost
pointer costs

Figure

3 shows pseudo code for the complete algorithm
used in Crush. Steps 1 and 2 simply
run Crochemore's algorithm and create the C array,
Step 4 performs phrase selection, and Step 5 nishes
any skipped positions for which there was no positive
gain during the Step 4 processing. The time
required by Crush is dominated by the traversals of
the C lists in Step 4.3.2. For each possible substring,
of which there may be K 1, the entire pointer chain
of O(n) items must be traversed in order to calculate
the frequency of a substring. Step 4.6 also sees
the chain of pointers relating to a selected phrase traversed
a second time to record pointers and mark the
positions as covered. Note Steps 4.3.2 and 4.6 must
also exclude self overlapping positions from consideration

An implementation of Crush as described above, and
an implementation of Offline as downloaded from
www.cs.purdue.edu/homes/stelo/Off-line/ were
run on the Purdue corpus [Purdue, 2001]. Table 1
shows the compression and speed results achieved using
a Pentium III 800MHz CPU with 640Mb of RAM,
primary cache, and running Linux. The C
code was compiled using gcc version egcs-2.91.66
with full optimisations. Phrases in crush were limited
to characters in length. The values reported
in

Table

1 used a gain formula of
The nal term was added in order to bias the phrase
selection towards single chars: that is, to reduce the
number of phrases chosen. Our initial experiments
showed that Crush using the gain measure stated in
the previous section was too aggressive in its phrase
selection, a problem we discuss below. Compression
values assume a Human coder is used in coding both
the phrase book and pointer lists, but prelude-costs
for both codes are not included. For both codes, the
number of codewords was small (less than 100 in all
cases), and so prelude size has negligible eect on nal
compression levels.
As

Table

shows, our compression results were
competitive on most les of the corpus, which is unusual
given our local rather than global approach to
phrase selection. One obvious failure of Crush is
to nd good phrases in the le Spor All 2x, which is
the le Spor All repeated twice. This is an example
of the short-comings of the local choice approach we
have adopted. The Spor All 2x le, as for all the les
in the Purdue Corpus, consists of 258  2 blocks of
about 14 lines of genetic data as shown in Figure 4.
On this le, Offline rst chooses
upstream sequence, from -800 to -1\n
as its highest gain phrase, and then proceeds to choose
200 phrases all of length 800 characters (the maximum
allowed) and that occur four or less times.
Crush, on the other hand, must rst deal with the
characters
before it can select the phrase
upstream sequence, from -800 to -1\n.
In fact, Crush determines that
upstream sequence, from -800 to -1\n
is its rst decent phrase, leaving the preceding characters
to be encoded as singletons. Amongst Crush's
phrase choices for this le are the phrases
upstream sequence, from -800 to -1
upstream sequence, from -800 to -1
upstream sequence, from -800 to -1
3 upstream sequence, from -800 to -1
4 upstream sequence, from -800 to -1
9 upstream sequence, from -800 to -1
7 upstream sequence, from -800 to -1
8 upstream sequence, from -800 to -1
5 upstream sequence, from -800 to -1
6 upstream sequence, from -800 to -1,
which clearly could be improved. Once Crush gets
to line 2222 of the le, the location of the block Offline
designates as its second best phrase, most of
that block has already been covered by earlier choices
of smaller phrases, and so is not available as a choice
to Crush.
A similar problem occurred on general text. We
ran Crush on the small text les from the Calgary
[Calgary, 2001] and Canterbury [Canterbury, 2001]
Input String to be compressed, and
K, the maximum length phrase to consider for the phrase book.
level one classes for Crochemore's algorithm.
algorithm to level K, storing each level in the C array such that
C[k][i] points to the next member of the class containing position i on level k.
Step 3 Set all positions of S to uncovered.
Step 4 While there are uncovered positions in S
Step 4.1 Let i be the smallest uncovered position in S.
Step 4.2 Let j be the min(smallest covered position > i, i +K).
Step 4.3 For each level 2  k  j i
Step 4.3.1 Set f 0.
Step 4.3.2 For each position c in the list rooted at C[k][i]
If the k positions fc,c+1,. ,c+k-1g are all uncovered set f f + 1.
Step 4.3.3 Set G k Hfk H(k
Step 4.4 Find
Step 4.5 If Gm  0 then record position i as skipped, mark it as covered, and goto Step 4.
Step 4.6 For each position c in the list rooted at C[m][i]
Step 4.6.1 If the k positions fc,c+1,. ,c+k-1g are all uncovered
Record a pointer in position c to the new phrase.
positions fc; c to covered.
Step 5 For each position i recorded as skipped in Step 4.5
Step 5.1 If the single character at position i is not a phrase, add it to the phrase book.
Step 5.2 Record a pointer to the phrase at position i.
Output Phrase book and list of pointers into the phrase book.

Figure

3: The algorithm used in Crush
File Size bzip2 Offline Crush Offline Crush
Name (bytes) (bpc) (bpc) (bpc) (secs) (secs)
Spor EarlyII 25008 2.894 2.782 2.217 6.2 1.1
Spor EarlyI 31039 1.882 1.835 2.222 8.5 1.9
Helden CGN 32871 2.319 2.264 2.219 9.8 2.1
Spor Middle 54325 2.281 2.176 2.196 21.3 9.0
Helden All 112507 2.261 2.116 2.227 75.0 58.5
Spor All 222453 2.218 1.953 2.195 278.5 291.2
All Up 400k 399615 2.249 2.136 2.275 989.7 1034.8
Spor All 2x 444906 1.531 0.148 2.194 1133.7 1046.7

Table

1: Compression and timing results for the Purdue corpus.
corpora, but the compression results were abysmal,
averaging around four bits per character.

Table

also shows that the running time on the
Purdue corpus, was not as low as we had anticipated.
Running times on the Calgary and Canterbury corpora
were exceptionally fast, but this is hardly surprising
given the poor compression results. The reason
for the low running time on general text is that
short phrases are initially chosen which cover much
of the input string. Subsequent processing only need
look at the remaining substrings, of which there are
few.

Table

2 shows a breakdown of the running time
on the Purdue corpus generated using the gprof soft-
ware. Proling of the code indicated that by far the
majority of the time was spent in counting the frequency
of phrases: Step 4.3.2 in Figure 3. The string
processing portion of Crush with Crochemore's algorithm
was extremely fast.
This paper has reported on a simple attempt to apply
Crochemore's algorithm for nding repeating sub-strings
to phrase selection for oine data compres-
File Steps 1 Step 4.3.2
and 2
Spor EarlyII 2% 78%
Spor EarlyI 2% 82%
Helden CGN 2% 85%
Spor Middle 1% 91%
Helden All 0% 96%
Spor All 0% 98%
All Up 400k 0% 99%

Table

2: Percentage of running time taken in
Crochemore's algorithm (Steps 1 and 2) and frequency
counting (Step 4.3.2) by Crush on the Purdue
Corpus.
sion. We have followed the model of Apostolico &
Lonardi, greedily choosing phrases at each stage that
maximise an approximation of the compression gain
expected if the phrase is included in the phrase book
than a global
approach to phrase selection, however, we trialled
a local approach, which has been shown to work
well for string covering algorithms [Yang, 2000]. The
>RTS2 RTS2 upstream sequence, from -800 to -1
GTAATGGTTCATTTCTTTAATAGCCTTCCATGACTCTTCTAAGTTGAGTTTATCATCAGG
TAGTAAGGATGCACTTTTCGATGTACTATGAGACTGGTCCGCACTTAAAAGGCCTTTAGA
TTTCGAAGACCACCTCCTCGTACGTGTATTGTAGAAGGGTCTCTAGGTTTATACCTCCAA
TGTCCTGTACTTTGAAAACTGGAAAAACTCCGCTAGTTGAAATTAATATCAAATGGAAAA
GTCAGTATCATCATTCTTTTCTTGACAAGTCCTAAAAAGAGCGAAAACACAGGGTTGTTT
GATTGTAGAAAATCACAGCG
>MEK1 MEK1 upstream sequence, from -800 to -1
ACAGAAAGAAGAAGAGCGGA
>NDJ1 NDJ1 upstream sequence, from -800 to -1
GTACGGCCCATTCTGTGGAGGTGGTACTGAAGCAGGTTGAGGAGAGGCATGATGGGGGTT

Figure

4: Beginning of the le Spor All 2x
string processing portion of our compressor based on
Crochemore's algorithm [Crochemore, 1981] is fast,
but the subsequent processing stage is limited by a
poor data structure.
Several techniques oer hope for improvement to
the running time of Crush. The rst is to replace
the pointer chain data structure, which stores the results
of Crochemore's algorithm for later processing,
with an alternate structure. Recently Smyth & Tang
have shown that all the repeating substring information
required by Crush can be stored in (n) space
arrays [Smyth & Tang, 2001]. Their structure plays
the same role as a su-x tree, but is generated directly
from Crochemore's algorithm, hence stores only repeating
substrings. The overhead for its construction
is minimal, and so should not increase the running
time of the rst stage of Crush. Using these arrays
will signicantly reduce the memory requirements of
Crush, and speed up the processing of the repeating
substring information. Importantly, it should allow
the frequency of phrases to be calculated more e-
ciently, which is a major bottleneck. As shown in

Table

2, typically over 90% of the time is spent calculating
phrase frequencies in the current implementation

Another avenue for resource savings is in an alternate
implementation of Crochemore's algorithm.
Future versions of our software will make use of a
new array-based implementation of Crochemore's algorithm
[Baghdadi et al, 2001] that in practice runs
much faster than the standard implementation and
reduces space requirements from 44n to 12n bytes.
One nal avenue worth exploring in this context is
a recent algorithm due to [Smyth & Tang, 2001] that
calculates all repeating substrings that are nonex-
tendible to both the left and right. Currently
Crochemore's algorithm supplies a set of all sub-strings
that are nonextendible only to the right. By
running Crochemore's algorithm on the reverse of the
string, and collating the results with a run on the
string itself, the set of candidate strings for the phrase
book should be reduced, while at the same time the
utility of the remaining string should be enhanced.
We anticipate a substantial improvement in compression
results once this approach is implemented.
A major point of deviation between our approach
and that of Apostolico & Lonardi is that at each
phrase choice, Crush considers only those phrases
starting at the leftmost uncovered position in the input
string|a local approach. This is clearly a major
contributing factor to our poor compression levels on
general text. Examining the phrase choices made by
Crush and Offline, for example, on progc of the
Calgary Corpus, shows that many \good" phrases selected
by Offline are unavailable to Crush because
they have been partially covered by an earlier phrase
choice. Indeed, Crush only chooses four phrases that
are not single characters, hence the poor compression
results. This was the reason for the introduction of
the 2f p l p term in the gain calculation formula. Biasing
the gain towards single characters limits the early
selection of short phrases that occur very frequently;
the very phrases whose selection prevents the use of
longer matches later in the processing. The down-side
is, of course, that it is extremely di-cult for any
infrequent, long phrases to be chosen. For a le in
the Purdue corpus, H is typically around 2.5 bits per
character and so
For a phrase of length 800 to be selected, it must
occur at least 6 times, whereas on Spor All 2x, Offline
routinely chooses phrases of length 800 with a
frequency less than 6.
It is interesting to note that our local approach,
however, still gave good compression on the majority
of the Purdue corpus. The reason that Crush
performs well on the Purdue corpus, rather than on
other text, is that in general the high gain phrases in
the Purdue corpus occur towards the start of the data
les. This allows their early selection by Crush unlike
on general text, where high gain substrings are
never considered as possible phrase candidates because
parts of those phrases have been covered by
an earlier, local choice. Implementing the global approach
using the current pointer chain data structure
in Crush would be prohibitively expensive. Once the
tree data structure of [Smyth & Tang, 2001] is incor-
porated, however, the global approach may become a
feasible option. The compression results on the Purdue
corpus indicate that a global approach would improve
the compression performance on general data.
Another technique that we intend to incorporate
in Crush is a more accurate gain measure. As the
generation of repeating substring information is fast,
with a more appropriate data structure to store this
information we can aord to spend more time estimating
the gain of each phrase. An approximation
based on the self entropy of both pointers and the
phrase book representation should lead to improved
compression levels on a wide range of data. Also an iterative
approach that makes multiple passes over the
data to improve gain estimates is worth investigating
A further avenue for exploration is allowing
phrases to overlap. If phrases are allowed to overlap
then the data section of the compressed le can
no longer be a simple sequential list of pointers to
phrases in the phrase book. Each pointer must also
be paired with an indication of how much the phrase
it represents overlaps the previous text. If Human
coding or similar is used for storing this informa-
tion, so that fast decoding is guaranteed, at least
one bit per pointer must be added to the nal le.
Therefore, to maintain the compression levels of the
non-overlapping implementation, the average size of
the pointers must reduce by one bit. A reduction
in pointer size would occur if a suitable change in
the frequency distribution of pointers occurred when
overlap was allowed, or there was a large reduction in
the number of pointers. Our preliminary experiments
allowing phrase overlap on the Purdue corpus seem to
indicate that allowing overlap is not benecial.

Acknowledgments

Thanks to Lu Yang [Yang, 2000] for making available
code for the k-cover algorithm and to F. Franek
making available code for
a very e-cient implementation of Crochemore's algo-
rithm. Thanks also to the anonymous referees for
their helpful comments.



--R


A fast space-e-cient approach to substring re nement
Data compression using long common strings.
The Calgary Corpus

The Canterbury Corpus
An optimal algorithm for computing the repetitions in a word.
Crochemore's algorithm revisited

Compression by induction of hierarchical grammars.
The Purdue Corpus
Experiments in text
A mathematical theory of communication.
The Mathematical Theory of Communication.
Computing all repeats using O(n) space and O(n log n) time.


Online construction of su-x trees
Computing a k-cover of a string
A universal algorithm for sequential data compres- sion
--TR
Data compression via textual substitution
Experiments in text file compression
General-purpose compression for efficient retrieval
Data Compression Using Long Common Strings

--CTR
Frantiek Frank , Jan Holub , William F. Smyth , Xiangdong Xiao, Computing quasi suffix arrays, Journal of Automata, Languages and Combinatorics, v.8 n.4, p.593-606, April
strings;textual substitution;repeating substrings;offline data compression