aboutsummaryrefslogtreecommitdiff
path: root/ALGORITHMS
diff options
context:
space:
mode:
Diffstat (limited to 'ALGORITHMS')
-rw-r--r--ALGORITHMS47
1 files changed, 0 insertions, 47 deletions
diff --git a/ALGORITHMS b/ALGORITHMS
deleted file mode 100644
index 7c7d2ca..0000000
--- a/ALGORITHMS
+++ /dev/null
@@ -1,47 +0,0 @@
1
2Bzip2 is not research work, in the sense that it doesn't present any
3new ideas. Rather, it's an engineering exercise based on existing
4ideas.
5
6Four documents describe essentially all the ideas behind bzip2:
7
8 Michael Burrows and D. J. Wheeler:
9 "A block-sorting lossless data compression algorithm"
10 10th May 1994.
11 Digital SRC Research Report 124.
12 ftp://ftp.digital.com/pub/DEC/SRC/research-reports/SRC-124.ps.gz
13
14 Daniel S. Hirschberg and Debra A. LeLewer
15 "Efficient Decoding of Prefix Codes"
16 Communications of the ACM, April 1990, Vol 33, Number 4.
17 You might be able to get an electronic copy of this
18 from the ACM Digital Library.
19
20 David J. Wheeler
21 Program bred3.c and accompanying document bred3.ps.
22 This contains the idea behind the multi-table Huffman
23 coding scheme.
24 ftp://ftp.cl.cam.ac.uk/pub/user/djw3/
25
26 Jon L. Bentley and Robert Sedgewick
27 "Fast Algorithms for Sorting and Searching Strings"
28 Available from Sedgewick's web page,
29 www.cs.princeton.edu/~rs
30
31The following paper gives valuable additional insights into the
32algorithm, but is not immediately the basis of any code
33used in bzip2.
34
35 Peter Fenwick:
36 Block Sorting Text Compression
37 Proceedings of the 19th Australasian Computer Science Conference,
38 Melbourne, Australia. Jan 31 - Feb 2, 1996.
39 ftp://ftp.cs.auckland.ac.nz/pub/peter-f/ACSC96paper.ps
40
41All three are well written, and make fascinating reading. If you want
42to modify bzip2 in any non-trivial way, I strongly suggest you obtain,
43read and understand these papers.
44
45I am much indebted to the various authors for their help, support and
46advice.
47