bwtzip - nuwen.net

bwtzip: A Linear-Time Portable Research-Grade Universal Data Compressor

Status - 21^st Century Compression, 22^nd Century Memory Usage

• All of the necessary algorithms for Burrows-Wheeler compression have been implemented in bwtzip.
• There are no known bugs in bwtzip.
• bwtzip generally produces smaller compressed output than bzip2 and ZIP.
• There are still several issues to be resolved before bwtzip can be used widely, explained in the Issues section. Chief among them is bwtzip's memory usage.

Download

Efficiency

Frequently Asked Questions

• Q: Is bwtzip compatible with [insert another compressor here; e.g. ZIP]?
  
  
  • A: No. bwtzip does not produce output that anything else can understand; bwtzip cannot understand output produced by anything else. This is because bwtzip uses new, advanced algorithms not found in ZIP, gzip, or bzip2.
  
  
• Q: What is chunk size?
  
  
  • A: A setting that changes bwtzip's compression efficiency. It is an inherent feature of any Burrows-Wheeler compressor. The algorithm is designed to work on a single block of data. If your file is 10 gigabytes, it may be a bad idea to work on all of it in memory at once. Thus, a Burrows-Wheeler compressor must break up a long file into separate parts (chunks). These chunks are then processed independently. The decompressor then integrates everything together. Controlling how large the chunks are has a few effects.
    
    Larger chunks lead to...
    
    
    • Higher compression. If the algorithm can see more data at once, it can find more redundancy.
      
      
    • More memory used during compression. All algorithms ordinarily used to perform the BWT use some constant multiple of the chunk size for temporary memory.
      
      
    • Slower compression for nonlinear algorithms. This is not true of linear algorithms, such as bwtzip's Ukkonen suffix trees.
      
      
    • More memory used during decompression. The decompressor also uses some constant multiple of the chunk size for temporary memory. However, this multiple is significantly less than that for the compressor, so ordinarily decompression memory usage is not a consideration. Chunk size has little effect on decompression time, as the algorithm is always linear.
  
  
• Q: How can you ever decompress something? Will there ever be a bwtunzip?
  
  
  • A: bwtunzip is part of the bwtzip project. The two are developed synchronously, since the compressor has to produce output that the decompressor can understand. bwtunzip doesn't get as much attention as bwtzip because its algorithms are simply the mirror image of the compressor. However, any improvements to bwtunzip's performance would be welcome.
  
  
• Q: I'm not a programmer. All these files confuse me. What do I need and what can I delete?
  
  
  • A: You only need the EXE files. The CC, HH, and TXT files are unnecessary if you don't care about the source code.
  
  
• Q: How can I uninstall bwtzip?
  
  
  • A: Simply delete bwtzip's EXE files. bwtzip makes no changes to your system. It's the way programs should behave.
  
  
• Q: Is bwtzip available for other platforms?
  
  
  • A: Sure. My only interest is in Win32 and Linux, but the source code is reasonably portable and should work on all sorts of other platforms. If you use Linux, compile bwtzip yourself. If you've found a portability problem in bwtzip, I'd like to hear about it. However, I have no sympathy for systems that have non-8-bit unsigned chars, 16-bit ints, non-32-bit unsigned longs, or non-64-bit unsigned long longs.
  
  
• Q: Who has worked on bwtzip?
  
  
  • A: Stephan T. Lavavej and Joergen Ibsen, in chronological order. I [Stephan] am the original author; I created the bwtzip framework, as well as implementing (and reimplementing) many algorithms. Joergen contributed an adaptive Huffman encoder; his website is www.ibsensoftware.com.
  
  
• Q: Can I see the source code?
  
  
  • A: Of course. bwtzip is distributed under the GNU GPL.
  
  
• Q: Can I use the source code in one of my own projects?
  
  
  • A: Read the GPL.
  
  
• Q: How can I help?
  
  
  • A: Spread the word, report bugs, or contribute code, in order of increasing difficulty. If you contribute code, it must be GPLed or public domain. It helps immensely if you can follow bwtzip's coding conventions. As for spreading the word, that may be the most helpful thing of all. It's time to create a high-performance, high-efficiency compressor for the twenty-first century, and I think that bwtzip is that compressor. bwtzip is already very efficient; as more people learn about and experiment with bwtzip, we'll make its performance acceptable.
  
  
• Q: How do you pronounce bwtzip?
  
  
  • A: I pronounce it "bee double-you tee zip". It may not be the most euphonic pronunciation, but it works for me. Alternative suggestions I have heard include "beaut zip" (as in beautiful), "boot zip", and "bw00tzip". :-)
  
  
• Q: Why the name bwtzip?
  
  
  • A: I am ridiculously uninventive. bwtzip uses the Burrows-Wheeler Transformation, and it's traditional to give compressors names that end with zip. (pkzip, gzip, bzip2, etc.) Furthermore, no one has ever used the name bwtzip before.
  
  
• Q: Can I see the file format?
  
  
  • A: Yes, but it's not clearly documented. I'm an ardent believer in open file format specifications. It does no good if free reading/writing implementations exist for a file format if the specification is not available to all. (I'm looking at you, Ogg Vorbis.) The golden standard for file format specifications is the Portable Network Graphics standard, which is freely available and readily comprehensible. Unfortunately, bwtzip is not quite there yet. Too much work is going into the algorithms themselves for the file format to be stable. (It changes every time a major revision occurs in the code; different versions of bwtzip usually cannot understand each other.) That said, if you wanted to, you could look at the bwtzip algorithms and figure out the format I use for compressed output. Now, the eventual goal is for bwtzip to go from research-grade to production-grade code without compromising its clarity. Once it settles down, an actual file format can be written down clearly for all to see. It wouldn't take more than a couple of pages; the hardest thing is to describe how the arithmetic compressor works.
  
  

Definitions

The Burrows-Wheeler Transformation

BWT Example

STEPHANTLAVAVEJ
TEPHANTLAVAVEJS
EPHANTLAVAVEJST
PHANTLAVAVEJSTE
HANTLAVAVEJSTEP
ANTLAVAVEJSTEPH
NTLAVAVEJSTEPHA
TLAVAVEJSTEPHAN
LAVAVEJSTEPHANT
AVAVEJSTEPHANTL
VAVEJSTEPHANTLA
AVEJSTEPHANTLAV
VEJSTEPHANTLAVA
EJSTEPHANTLAVAV
JSTEPHANTLAVAVE

ANTLAVAVEJSTEPH
AVAVEJSTEPHANTL
AVEJSTEPHANTLAV
EJSTEPHANTLAVAV
EPHANTLAVAVEJST
HANTLAVAVEJSTEP
JSTEPHANTLAVAVE
LAVAVEJSTEPHANT
NTLAVAVEJSTEPHA
PHANTLAVAVEJSTE
STEPHANTLAVAVEJ
TEPHANTLAVAVEJS
TLAVAVEJSTEPHAN
VAVEJSTEPHANTLA
VEJSTEPHANTLAVA

ANTLAVAVEJSTEPH Location: 0
AVAVEJSTEPHANTL Location: 1
AVEJSTEPHANTLAV Location: 2
EJSTEPHANTLAVAV Location: 3
EPHANTLAVAVEJST Location: 4
HANTLAVAVEJSTEP Location: 5
JSTEPHANTLAVAVE Location: 6
LAVAVEJSTEPHANT Location: 7
NTLAVAVEJSTEPHA Location: 8
PHANTLAVAVEJSTE Location: 9
STEPHANTLAVAVEJ Location: 10
TEPHANTLAVAVEJS Location: 11 <== The original first letter
TLAVAVEJSTEPHAN Location: 12
VAVEJSTEPHANTLA Location: 13
VEJSTEPHANTLAVA Location: 14

Reverse-BWT Example

Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
L:     H L V V T P E T A E J  S  N  A  A
F:     A A A E E H J L N P S  T  T  V  V

F[0]  is the 1st A in F. L[8]  is the 1st A in L. T[0]  = 8
F[1]  is the 2nd A in F. L[13] is the 2nd A in L. T[1]  = 13
F[2]  is the 3rd A in F. L[14] is the 3rd A in L. T[2]  = 14
F[3]  is the 1st E in F. L[6]  is the 1st E in L. T[3]  = 6
F[4]  is the 2nd E in F. L[9]  is the 2nd E in L. T[4]  = 9
F[5]  is the 1st H in F. L[0]  is the 1st H in L. T[5]  = 0
F[6]  is the 1st J in F. L[10] is the 1st J in L. T[6]  = 10
F[7]  is the 1st L in F. L[1]  is the 1st L in L. T[7]  = 1
F[8]  is the 1st N in F. L[12] is the 1st N in L. T[8]  = 12
F[9]  is the 1st P in F. L[5]  is the 1st P in L. T[9]  = 5
F[10] is the 1st S in F. L[11] is the 1st S in L. T[10] = 11
F[11] is the 1st T in F. L[4]  is the 1st T in L. T[11] = 4
F[12] is the 2nd T in F. L[7]  is the 2nd T in L. T[12] = 7
F[13] is the 1st V in F. L[2]  is the 1st V in L. T[13] = 2
F[14] is the 2nd V in F. L[3]  is the 2nd V in L. T[14] = 3

Index: 0 1  2  3 4 5 6  7 8  9 10 11 12 13 14
L:     H L  V  V T P E  T A  E J  S  N  A  A
T:     8 13 14 6 9 0 10 1 12 5 11 4  7  2  3

Read primary index. Value: 11
Index = 11  L[11] = S   T[11] = 4
Index = 4   L[4]  = T   T[4]  = 9
Index = 9   L[9]  = E   T[9]  = 5
Index = 5   L[5]  = P   T[5]  = 0
Index = 0   L[0]  = H   T[0]  = 8
Index = 8   L[8]  = A   T[8]  = 12
Index = 12  L[12] = N   T[12] = 7
Index = 7   L[7]  = T   T[7]  = 1
Index = 1   L[1]  = L   T[1]  = 13
Index = 13  L[13] = A   T[13] = 2
Index = 2   L[2]  = V   T[2]  = 14
Index = 14  L[14] = A   T[14] = 3
Index = 3   L[3]  = V   T[3]  = 6
Index = 6   L[6]  = E   T[6]  = 10
Index = 10  L[10] = J   T[10] = 11
Index = 11  Primary index reached, end of string.

Long BWT Example

Three_Rings_for_the_Elven-kings_under_the_sky,#Seven_for_the_Dwarf-lords_in_the
ir_halls_of_stone,#Nine_for_Mortal_Men_doomed_to_die,#One_for_the_Dark_Lord_on_
his_dark_throne#In_the_Land_of_Mordor_where_the_Shadows_lie.#One_Ring_to_rule_t
hem_all,_One_Ring_to_find_them,#One_Ring_to_bring_them_all_and_in_the_darkness_
bind_them#In_the_Land_of_Mordor_where_the_Shadows_lie.#$

.me,,.,,#emeylnfee___##_______##_##____#__$eeeeeklffr,eeeeeemmlsoseonoeensrndss
sddsdoefrrrnneenrnddegkgdggsrrhht__h_LLwDdd__nnnrnne__n__rraarnniiihhhhhnnnehhh
nnhrrlmrhhhhhvMvdhhnSrooo_____nnnnnnSS_ttttttttttttttww_Ttdll__bfNrRRRRkehrr-rs
lalu__aaa-lEeeeeoeeeoIIiiaaaiiuooOOOiOkiiiiiitttt___o_rtdffffddLMMlMddoioooeooo
oooeehabaaaho_sigdwwlg_e_r___________________sr_leD__ook

Asymptotic Time Complexity

• The Manber-Myers suffix array algorithm (also implemented in bwtzip), runs in O(N log N) worst case time and requires 8N bytes of space, but is considerably slower than suffix trees (on the order of 3x to 10x slower).
• The Bentley-Sedgewick algorithm is based on quicksort, requires only 5N bytes of space, and is rather fast in the average case. However, it is extremely slow in the worst case, which occurs when the input sequence contains long repeated substrings. bzip2 implements the Bentley-Sedgewick algorithm.
• The Larsson-Sadakane algorithm runs in O(N log N) worst case time and uses 8N bytes of space. It is reported to be only slightly slower than a suffix tree algorithm.

Circular Shifts = Suffixes

The Move-to-Front Transformation

Bcell list("MTF Array", 256);    // Bcells have names; this one is named "MTF Array" and can hold 256 bytes

for (int n = 0; n < 256; n++) { // Initialize the list
    list[n] = n;
}

for (size_t n = 0; n < cell.size; n++) {    // For every element in the Bcell cell
    unsigned char uc, out;

    uc = cell[st];            // Input byte
    out = list.find(uc);      // Where is it in the array?
    cell[st] = out;           // Write that back
    if (out != 0) {           // If the byte read isn't in position 0
        list.move(out, 0, 1); // Take the bytes at positions 0, ... , out - 1 and move them to 1, ..., out
        list[0] = uc;         // Put the byte in position 0
    }
}

Bcell list("MTF Array", 256);    // Bcells have names; this one is named "MTF Array" and can hold 256 bytes

for (int n = 0; n < 256; n++) { // Initialize the list
    list[n] = n;
}

for (size_t n = 0; n < cell.size; n++) {    // For every element in the Bcell cell
    unsigned char uc, out;

    uc = cell[st];            // Input byte
    out = list[uc];           // Decoded byte
    cell[st] = out;           // Write decoded byte
    if (uc != 0) {            // If the byte wasn't in position 0
        list.move(uc, 0, 1);  // Move bytes down
        list[0] = out;        // Put read byte in position 0
    }
}

Huffman Compression

    unsigned char s = 0;

    for (int i = 255; i >= 0; i--) {
        starting[i] = s;
        s += codelengthfreqs[i];
        s >>= 1;
    }

    for (int i = 255; i >= 0; i--) {
        unsigned char c = starting[i];

        // Fill in the codes with codelength i
        for (int j = 0; j < 256; j++) {
            if (codelength[j] == i) {
                codes[j] = c++;
            }
        }
    }

Rationale

...
VAVEJSTEPHANTLA
VEJSTEPHANTLAVA

MTF-2

Zero Length Encoding

Introduction to Suffix Trees

Here is the color key used in my suffix tree diagrams. There is no actual difference between nodes with multiple children, nodes with one child, or nodes with no children (i.e. leaf nodes). However, for clarity, I have used different colors. Furthermore, different colors indicate edges and edge labels. These diagrams should be easy to follow despite my lack of drawing talent.

Let us first work with the string DEADBEEF. We will make the first generation suffix tree for this string. We do this by listing all of the string's suffixes, making chains of nodes and edges for each suffix, and then attaching each chain to the root. Each edge is labeled with a symbol from the original string. The first symbols of a suffix appear on the edges closest to the root. In a first generation suffix tree, only the root has multiple children. Also, there is no real concept of the order of the children - I arbitrarily put the longest suffixes on the left, but this is only for illustration. It is a big mess.

We can make the messy first generation tree a little neater. Any time a node has multiple children edges labeled with the same symbol, combine those edges (and the nodes they lead to) into one. However, you must also preserve subtrees, so you may create multiple-children nodes in the process. Repeat until no nodes have multiple children edges labeled with the same symbol. This produces the second-generation suffix tree. Note that in the first generation suffix tree for DEADBEEF, the root has two D edges leading out from one. One edge leads to a node which has a B-E-E-F subchain, while the other edge leads to a node with a E-A-D-B-E-E-F subchain. When we combine these, the root ends up with a single D edge leading to a single node. That node, in turn, has two subchains as its children. The chains start with different symbols, so no further combination can be done here. For DEADBEEF, only a little combination has to be done, but in general, many multiple-children nodes can be created. Here, I have ordered the edges leading out of any node lexicographically - A edges appear to the left of B edges, and so forth. Second generation suffix trees have the property that each node can have at most Q children edges, where Q is the number of symbols in the alphabet, and no node can have multiple children edges labeled with the same symbol (otherwise, they would have been combined together). This is a fairly nice property.

This is a third generation (for real this time) suffix tree. We relax the requirement that edges are labeled by single symbols of the original string. Instead, edges are labeled by substrings of the original string. We "path compress" the second generation suffix tree, and remove all single-children nodes. A [real] suffix tree has only multiple-children nodes and leaf nodes, never single-children nodes. We can still use the substring-matching algorithm with a real suffix tree, though we might not leap to a new node after looking at every symbol. It can be proven that the number of nodes in a real suffix tree is linear in the number of symbols of the original string. What may [should!] concern you is the space required to store the labels for the edges! After all, that's a lot of symbols. Luckily, any given edge can be stored in constant space. Instead of storing the symbols themselves, we store indices into the original string. We only need two, and we can define any substrings we like. This is a linear-space suffix tree, just as useful (more useful!) than a second generation suffix tree, and we can use it for substring matching or Burrows-Wheeler sorting. How can we use it for Burrows-Wheeler sorting? Look at the leaf nodes of the suffix tree for DEADBEEF. They exactly correspond to the suffixes of DEADBEEF. Furthermore, by doing a simple depth-first search (visiting edges with lexicographically lesser first symbols before edges with lexicographically greater first symbols), we will hit the leaf nodes/suffixes in lexicographic order! So, if we build this linear-space suffix tree in linear time (with Ukkonen's algorithm) and then do a depth-first search (also linear time), we will have sorted the suffixes of the string, which is exactly what the Burrows-Wheeler Transformation needs!
Well, not quite. There is a problem, and if you paid attention to the Circular Shifts = Suffixes section, you may be catching on. What happens when one suffix is the prefix of another suffix? Here is the first generation suffix tree for MOOMOO.
And here is the second-generation suffix tree for MOOMOO. Uh oh, six suffixes and only three leaf nodes.
The real suffix tree for MOOMOO also has three leaf nodes, of course. What has happened? If one suffix is the prefix of another suffix, then it will end midway through the tree, and it will not get a leaf node of its own. It may not even end on an internal node - it could end (conceptually) in the middle of an edge! While we can still do substring matching no problemo, we are in for some trouble if we expect the leaf nodes to exactly correspond to suffixes.
The solution, as before, is to add a sentinel character. Not only does a sentinel character make sorting the suffixes of the augmented string identical to sorting the circular shifts of the augmented string, but adding a sentinel character ensures that suffixes in a suffix tree correspond exactly to leaf nodes! This is the best of both worlds! Here is the first generation suffix tree for MOOMOO$. (Hopefully it is not necessary to see this; I include it for completeness).
Here is the second generation suffix tree for MOOMOO$.
And here is the real, path-compressed, third generation suffix tree for MOOMOO$. Note: seven suffixes, seven leaf nodes. (I have defined $ to be greater than all other symbols.) Depth-first traversal of this tree gives the suffixes of MOOMOO$ in sorted order. Note that DEADBEEF ended with F, which didn't appear anywhere else in the string. This fake sentinel hid the problems with making a suffix tree for a bare string. As before, always add a sentinel to a string before making a suffix tree for that string, if you want suffixes to correspond exactly with leaf nodes. It hurts nothing, even in the case of DEADBEEF.

References

Source Code

Documentation

Known Issues

• An adaptive Huffman coder, using the same probability model as the current arithmetic coder, would be interesting to see. Unfortunately, a naive implementation of adaptive Huffman using the present routines proved to be extraordinarily inefficient. Joergen Ibsen's implemention of adaptive Huffman does not yet use the exact same probability model as the arithmetic coding routines.
• The suffix tree algorithm still consumes a large amount of memory, about 50 bytes per input byte. This can theoretically be reduced to 20. I would settle for 40.
• The suffix tree algorithm currently performs a lot of small allocations and deletions.
• bwtzip lacks the Bentley-Sedgewick and Larsson-Sadakane algorithms.

Corpuses

1dfre10.txt  - The History of The Decline and Fall of the Roman Empire, Volume 1 by Edward Gibbon
2000010a.txt - 20,000 Leagues Under the Sea by Jules Verne
2city12.txt  - A Tale of Two Cities by Charles Dickens
2dfre11.txt  - The History of The Decline and Fall of the Roman Empire, Volume 2 by Edward Gibbon
3dfre10.txt  - The History of The Decline and Fall of the Roman Empire, Volume 3 by Edward Gibbon
4dfre10.txt  - The History of The Decline and Fall of the Roman Empire, Volume 4 by Edward Gibbon
5dfre11.txt  - The History of The Decline and Fall of the Roman Empire, Volume 5 by Edward Gibbon
6dfre10.txt  - The History of The Decline and Fall of the Roman Empire, Volume 6 by Edward Gibbon
7crmp10.txt  - Crime and Punishment by Fyodor Dostoyevsky
blkhs10.txt  - Bleak House by Charles Dickens
cnmmm10.txt  - On the Economy of Machinery and Manufacture by Charles Babbage
cprfd10.txt  - David Copperfield by Charles Dickens
cwgen11.txt  - The Memoirs of Ulysses S. Grant, William T. Sherman, and Philip H. Sheridan
dosie10.txt  - Reflections on the Decline of Science in England by Charles Babbage
dscmn10.txt  - The Descent of Man by Charles Darwin
dyssy10b.txt - The Odyssey of Homer, translated by Alexander Pope
feder16.txt  - The Federalist Papers
flat10a.txt  - Flatland: A Romance of Many Dimensions by Edwin Abbott Abbott
grexp10.txt  - Great Expectations by Charles Dickens
grimm10a.txt - Household Tales by The Brothers Grimm
iliab10.txt  - The Iliad of Homer, translated by Lang, Leaf, and Myers
jargon.html  - The Jargon File 4.3.3
lnent10.txt  - The Entire Writings of Abraham Lincoln
lwmen10.txt  - Little Women by Louisa May Alcott
mtent13.txt  - The Entire Writings of Mark Twain
nkrnn11.txt  - Anna Karenina by Leo Tolstoy, translated by Constance Garnett
otoos610.txt - On the Origin of Species, 6th Edition, by Charles Darwin
pandp12.txt  - Pride and Prejudice by Jane Austen
pwprs10.txt  - The Pickwick Papers by Charles Dickens
sense11.txt  - Sense and Sensibility by Jane Austen
slstr10.txt  - Sidelights on Astronomy and Kindred Fields of Popular Science by Simon Newcomb
suall10.txt  - All State of the Union Addresses up to January 29, 2002
tmwht10.txt  - The Man Who Was Thursday by G. K. Chesterton
trabi10.txt  - Theodore Roosevelt, An Autobiography
twtp110.txt  - The Writings of Thomas Paine, Volume 1
twtp210.txt  - The Writings of Thomas Paine, Volume 2
vbgle11a.txt - A Naturalist's Voyage Round the World by Charles Darwin
warw11.txt   - The War of the Worlds by H. G. Wells
world02.txt  - The 2002 CIA World Factbook
wrnpc10.txt  - War and Peace by Leo Tolstoy

gcc-3.2.1.tar    - gcc 3.2.1 source code
linux-2.4.20.tar - Linux kernel 2.4.20 source code

01hgp10a.txt - The Human Genome, Chromosome 1
02hgp10a.txt - The Human Genome, Chromosome 2
03hgp10a.txt - The Human Genome, Chromosome 3
04hgp10a.txt - The Human Genome, Chromosome 4
05hgp10a.txt - The Human Genome, Chromosome 5
06hgp10a.txt - The Human Genome, Chromosome 6
07hgp10a.txt - The Human Genome, Chromosome 7
08hgp10a.txt - The Human Genome, Chromosome 8
09hgp10a.txt - The Human Genome, Chromosome 9
0xhgp10a.txt - The Human Genome, Chromosome X
0yhgp10a.txt - The Human Genome, Chromosome Y
10hgp10a.txt - The Human Genome, Chromosome 10
11hgp10a.txt - The Human Genome, Chromosome 11
12hgp10a.txt - The Human Genome, Chromosome 12
13hgp10a.txt - The Human Genome, Chromosome 13
14hgp10a.txt - The Human Genome, Chromosome 14
15hgp10a.txt - The Human Genome, Chromosome 15
16hgp10a.txt - The Human Genome, Chromosome 16
17hgp10a.txt - The Human Genome, Chromosome 17
18hgp10a.txt - The Human Genome, Chromosome 18
19hgp10a.txt - The Human Genome, Chromosome 19
20hgp10a.txt - The Human Genome, Chromosome 20
21hgp10a.txt - The Human Genome, Chromosome 21
22hgp10a.txt - The Human Genome, Chromosome 22

https://nuwen.net/bwtzip.html (updated 2/13/2006)
Stephan T. Lavavej
Home: stl@nuwen.net
Work: stl@microsoft.com
This is my personal website. I work for Microsoft, but I don't speak for them.