Citizendia
Your Ad Here

bzip2
File name extension . A filename extension is a suffix to the name of a Computer file applied to indicate the encoding convention ( File format) of its contents bz2
Internet media type application/x-bzip
Type code Bzp2
Magic number BZh
Developed by Julian Seward
Type of format Data compression
bzip2
Developed by Julian Seward
Latest release 1. An Internet media type, originally called a MIME type after MIME and sometimes a Content-type after the name of a header in several protocols whose value A type code is the only mechanism used in pre- Mac OS X versions of the Macintosh Operating system to denote a file's format, in a manner similar A file format is a particular way to encode information for storage in a Computer file. Julian Seward is a Compiler writer and Free Software contributor A software developer is a person or organization concerned with facets of the software development process wider than design and coding a somewhat broader scope of Julian Seward is a Compiler writer and Free Software contributor A software release is the distribution whether public or private of an initial or new and upgraded version of a Computer software product 0. 5 / March 17, 2008
OS Cross-platform
Genre data compression
License Bzip2
Website bzip.org

bzip2 is a free and open source lossless data compression algorithm and program developed by Julian Seward. Events 45 BC - In his last victory Julius Caesar defeats the Pompeian forces of Titus Labienus and Pompey the Younger 2008 ( MMVIII) is the current year in accordance with the Gregorian calendar, a Leap year that started on Tuesday of the Common An operating system (commonly abbreviated OS and O/S) is the software component of a Computer system that is responsible for the management and coordination In computing cross-platform (also known as multi-platform) is a term used to refer to Computer software or computing methods and concepts that are implemented Computer software can be organized into categories based on common function type or field of use A software license (or software licence in commonwealth usage is a Legal instrument governing the usage or redistribution of copyright protected software A website (alternatively web site or Web site, a back-construction from the Proper noun World Wide Web) is a collection of Web pages Free software or software libre is Software that can be used studied and modified without restriction and which can be copied and redistributed in modified or unmodified Open source software (OSS began as a marketing campaign for Free software. Lossless data compression is a class of Data compression Algorithms that allows the exact original data to be reconstructed from the compressed data In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation Julian Seward is a Compiler writer and Free Software contributor Seward made the first public release of bzip2, version 0. 15, in July 1996. The compressor's stability and popularity grew over the next several years, and Seward released version 1. 0 in late 2000.

Contents

Compression efficiency

bzip2 compresses most files more effectively than more traditional gzip or ZIP but is slower. gzip is a Software application used for File compression. gzip is short for GNU zip; the program is a Free software replacement for the The ZIP File format is a Data compression and archival format. In this manner it is fairly similar to other recent-generation compression algorithms. Unlike other formats such as RAR or ZIP (but similar to gzip), bzip2 is only a data compressor, not an archiver. The program itself has no facilities for multiple files, encryption or archive-splitting, in the UNIX tradition instead relying on separate external utilities such as tar and GnuPG for these tasks. Unix (officially trademarked as UNIX, sometimes also written as Unix with Small caps) is a computer In Computing, tar (derived from tape archive) is both a File format (in the form of a type of archive Bitstream) and the name GNU Privacy Guard ( GnuPG or GPG) is a replacement for the PGP suite of cryptographic software

As stated in the front page of the bzip2 Web site, in most cases bzip2 is surpassed by PPM algorithms in terms of absolute compression efficiency. Prediction by Partial Matching ( PPM) is an adaptive statistical Data compression technique based on Context modeling and Prediction According to the author, bzip2 gets within ten to fifteen percent of PPM, while being roughly twice as fast at compression and six times faster at decompression.

bzip2 uses the Burrows-Wheeler transform to convert frequently recurring character sequences into strings of identical letters, and then applies a move-to-front transform and finally Huffman coding. The Burrows-Wheeler transform ( BWT, also called block-sorting compression) is an Algorithm used in Data compression techniques such as The move-to-front (or MTF) transform is an encoding of Data (typically a stream of Bytes designed to improve the performance of History In 1951 David A Huffman and his MIT information theory classmates were given In bzip2 the blocks are generally all the same size in plaintext, which can be selected by a command-line argument between 100 kB–900 kB. A kilobyte (derived from the SI prefix Kilo -, meaning 1000 is a unit of Information or Computer storage equal to either 1024 Compression blocks are delimited by a 48-bit sequence (magic number) derived from the binary-coded decimal representation of π, 0x314159265359, with the end-of-stream similarly delimited by a value representing sqrt(π), 0x177245385090. In Computer programming, the term magic number has multiple meanings In Computing and electronic systems binary-coded decimal ( BCD) is an encoding for decimal numbers in which each digit is represented by its own binary IMPORTANT NOTICE Please note that Wikipedia is not a database to store the millions of digits of π please refrain from adding those to Wikipedia as it could cause technical problems In Mathematics, a square root of a number x is a number r such that r 2 = x, or in words a number r whose IMPORTANT NOTICE Please note that Wikipedia is not a database to store the millions of digits of π please refrain from adding those to Wikipedia as it could cause technical problems

Originally, bzip2's ancestor bzip used arithmetic coding after the blocksort; this was discontinued because of the patent restriction to be replaced by the Huffman coding currently used in bzip2. Arithmetic coding is a method for Lossless data compression. Normally a string of characters such as the words "hello there" is represented using a fixed number of Software patent does not have a universally accepted definition History In 1951 David A Huffman and his MIT information theory classmates were given

bzip2 is known to be quite slow at compressing, making people opt for alternatives such as gzip when time is an issue. gzip is a Software application used for File compression. gzip is short for GNU zip; the program is a Free software replacement for the This problem is asymmetric, as decompression is relatively fast. Motivated by the large CPU time required for compression, a modified version was created in 2003 that supported multi-threading, giving significant speed improvements on multi-cpu and multi-core computers. A thread in Computer science is short for a thread of execution. As of January 2008 this functionality has not been incorporated into the main project.

Compression stack

Bzip2 uses several layers of compression techniques stacked on top of each other, which occur in the following order during compression and the reverse order during decompression:

  1. Run-length encoding (RLE): any sequence of 4 to 255 consecutive duplicate symbols is replaced by the first four symbols and a repeat length between 0 and 251. Run-length encoding ( RLE) is a very simple form of Data compression in which runs of data (that is sequences in which the same data value occurs in many Thus the sequence "AAAAAAABBBBCCCD" is replaced with "AAAA\3BBBB\0CCCD". Runs of symbols are always transformed after four consecutive symbols, even if the run-length is set to zero, to keep the transformation reversible. In the worst case, it can cause a pre-BWT expansion of 1. 25 and in the best case a reduction to <0. 02 of original size. Note that while the specification theoretically allows for runs of length 256–259 to be encoded, the reference encoder will not produce such output. The author of bzip2 has stated that the RLE step was a historical mistake[1] and was only intended to protect the original BWT implementation from pathological cases.
  2. Burrows-Wheeler transform (BWT): this is the reversible block-sort that is at the core of bzip2. The Burrows-Wheeler transform ( BWT, also called block-sorting compression) is an Algorithm used in Data compression techniques such as The block is entirely self contained, with input and output buffers remaining the same size—in bzip2, the operating limit for this stage is 900 kB. For the block-sort, a (notional) matrix is created in which row i contains the whole of the buffer, rotated to start from the ith symbol. Following rotation, the rows of the matrix are sorted into alphabetic (numerical) order. A 24-bit pointer is stored marking the starting position for when the block is untransformed. In practice, it is not necessary to construct the full matrix, rather the sort is performed using pointers for each position in the buffer. The output buffer is the last column of the matrix; this contains the whole buffer, but reordered so that it is likely to contain large runs of identical symbols.
  3. Move to front (MTF): again, this transform does not alter the size of the processed block. The move-to-front (or MTF) transform is an encoding of Data (typically a stream of Bytes designed to improve the performance of Each of the symbols in use in the document is placed in an array. When a symbol is processed, it is replaced by its subscript (offset) in the array and that symbol is shuffled to the front of the array. The effect is that immediately recurring symbols are replaced by zero symbols (long runs of any arbitrary symbol thus become runs of zero symbols), while other symbols are remapped according to their local frequency.
    A lot of "natural" data contains identical symbols that recur within a limited range (text is a good example). As the MTF transform assigns low values to symbols that reappear frequently, this results in a data stream which contains a lot of symbols in the low integer range, many of them being identical (different recurring input symbols can actually map to the same output symbol). Such data can be very efficiently encoded by any legacy compression method.
  4. Run-length encoding (RLE): long strings of repeated symbols in the output (normally zeros by this time) are replaced by a combination of the symbol and a sequence of two special codes, RUNA and RUNB, which represent the run-length as a binary number greater than one (1). Run-length encoding ( RLE) is a very simple form of Data compression in which runs of data (that is sequences in which the same data value occurs in many The sequence 0,0,0,0,0,1 would be represented as 0,RUNB,RUNA,1; RUNB and RUNA representing the value 4 in decimal. The run-length code is terminated by reaching another normal symbol. This RLE process is more flexible than the RLE of step 1, as it is able to encode arbitrarily long integers (in practice, this is usually limited by the block size, so that this step does not encode a run of more than 900000 bytes). The run-length is encoded in this fashion: assigning place values of 1 to the first bit, 2 to the second, 4 to the third, etc. in the RUNA/RUNB sequence, multiply each place value in a RUNB spot by 2, and add all the resulting place values (for RUNA and RUNB values alike) together. Thus, the sequence RUNB, RUNA results in the value (1*2 + 2) = 4. As a more complicated example:
    RUNA RUNB RUNA RUNA RUNB (ABAAB)
       1    2    4    8   16
       1    4    4    8   32 = 49
  5. Huffman coding: this process replaces fixed length symbols (8-bit bytes) with variable length codes based on the frequency of use. History In 1951 David A Huffman and his MIT information theory classmates were given More frequently used codes end up shorter (2-3 bits) whilst rare codes can be allocated up to 20 bits. The codes are selected carefully so that no sequence of bits can be confused for a different code.
    The end-of-stream code is particularly interesting. If there are n different bytes (symbols) used in the uncompressed data, then the Huffman code will consist of two RLE codes (RUNA and RUNB), n-1 symbol codes and one end-of-stream code. Because of the combined result of the MTF and RLE encodings in the previous two steps, there is never any need to explicitly reference the first symbol in the MTF table, thus saving one symbol for the end-of-stream marker (and explaining why only n-1 symbols are coded in the Huffman tree). In the extreme case where only one symbol is used in the uncompressed data, there will be no symbol codes at all in the Huffman tree, and the entire block will consist of RUNA and RUNB (implicitly repeating the single byte) and an end-of-stream marker with value 2.
    0: RUNA
    1: RUNB
    2-257: byte values 0-255
    258: end of stream, finish processing. (could be as low as 2).
  6. Multiple Huffman tables: several identically-sized Huffman tables can be used with a block if the gain from using them is greater than the cost of including the extra table. History In 1951 David A Huffman and his MIT information theory classmates were given At least two (2) and up to six (6) tables can be present, with the most appropriate table being reselected before every 50 symbols processed. This has the advantage of having very responsive Huffman dynamics without having to continuously supply new tables, as would be required in DEFLATE. Run-length encoding in the previous step is designed to take care of codes that have an inverse probability of use higher than the shortest code Huffman code in use.
  7. Unary base 1 encoding: if multiple Huffman tables are in use, the selection of each table (numbered 0. The unary numeral system is the bijective base - 1 Numeral system. . 5) is done from a list by a zero-terminated bit run between one (1) and six (6) bits in length. The selection is into a MTF list of the tables. The move-to-front (or MTF) transform is an encoding of Data (typically a stream of Bytes designed to improve the performance of Using this feature results in a maximum expansion of around 1. 015, but generally less. This expansion is likely to be greatly over-shadowed by the advantage of selecting more appropriate Huffman tables and the common-case of continuing to use the same Huffman table is represented as a single bit. Rather than unary encoding, effectively this is an extreme form of a Huffman tree where each code has half the probability of the previous code.
  8. Delta encoding (Δ): Huffman code bit-lengths are required to reconstruct each of the used Canonical Huffman tables. Delta encoding is a way of storing or transmitting Data in the form of differences between sequential data rather than complete files Each bit-length is stored as an encoded difference against the previous code bit-length. A zero-bit (0) means that the previous bit-length should be duplicated for the current code, whilst a one-bit (1) means that a further bit should be read and the bit-length incremented or decremented based on that value. In the common case a single bit is used per symbol per table and the worst case—going from length one (1) to length twenty (20)—would require approximately 37 bits. As a result of the earlier MTF encoding, code lengths would start at 2-3bits long (very frequently used codes) and gradually increase, meaning that the delta format is fairly efficient—requiring around 300-bits (38 bytes) per full Huffman table.
  9. Sparse bit array: a bitmap is used to show which symbols are used inside the block and should be included in the Huffman trees. A bit array (or bitmap, in some cases is an Array Data structure which compactly stores individual bits ( Boolean values. Binary data is likely to use all 256 symbols representable by a byte, whereas textual data may only use a small subset of available values, perhaps covering the ASCII range between 32 and 126. American Standard Code for Information Interchange ( ASCII) Storing 256 zero bits would be inefficient if they were mostly unused. A sparse method is used, the 256 symbols are divided up into 16 ranges and only if symbols are used within that block is a 16-bit array included. The presence of each of these 16 ranges is indicated by an additional 16-bit bit array at the front. The total bitmap uses between 32 and 272 bits of storage (4–34 bytes). For contrast, the DEFLATE algorithm would show the absence of a symbol by encoding the symbol as having zero bit-length; this is very inefficient with the Delta-encoding used in bzip2 which is the reason for bzip2 having a separate bit array.

File format

A . bz2 stream consists of a 4-byte header, followed by zero or more compressed blocks, immediately followed by an end-of-stream marker containing a 32-bit CRC for the plaintext whole stream processed. The compressed blocks are bit-aligned and no padding occurs. 

. magic:16                       = 'BZ' signature/magic number
. version:8                      = 'h' for Bzip2 ('H'uffman coding), '0' for Bzip1 (deprecated)
. hundred_k_blocksize:8          = '1'. . '9' block-size 100 kB-900 kB

. compressed_magic:48            = 0x314159265359 (BCD (pi))
. crc:32                         = checksum for this block
. randomised:1                   = 0=>normal, 1=>randomised (deprecated)
. origPtr:24                     = starting pointer into BWT for after untransform
. huffman_used_map:16            = bitmap, of ranges of 16 bytes, present/not present
. huffman_used_bitmaps:0. . 256    = bitmap, of symbols used, present/not present (multiples of 16)
. huffman_groups:3               = 2. . 6 number of different Huffman tables in use
. selectors_used:15              = number of times that the Huffman tables are swapped (each 50 bytes)
*. selector_list:1. . 6            = zero-terminated bit runs (0. . 62) of MTF'ed Huffman table (*selectors_used)
. start_huffman_length:5         = 0. . 20 starting bit length for Huffman deltas
*. delta_bit_length:1. . 40        = 0=>next symbol; 1=>alter length
                                                { 1=>decrement length;  0=>increment length } (*(symbols+2)*groups)
. contents:2. . ∞                  = Huffman encoded data stream until end of block

. eos_magic:48                   = 0x177245385090 (BCD sqrt(pi))
. crc:32                         = checksum for whole stream
. padding:0. . 7                   = align to whole byte

Note for implementors: Because of the first-stage RLE compression (see above), the maximum length of plaintext that a single 900 kB bzip2 block can contain is around 46 MB (45,899,235 bytes). This can occur if the whole plaintext consists entirely of repeated values (the resulting . bz2 file in this case is 46 bytes long). [2]

Use

In Unix, bzip2 can be used combined with or independently of tar: bzip2 file to compress and bzip2 -d file. Unix (officially trademarked as UNIX, sometimes also written as Unix with Small caps) is a computer bz2 to uncompress (the alias bunzip2 for decompression may also be used).

bzip2's command line flags are mostly the same as in gzip. gzip is a Software application used for File compression. gzip is short for GNU zip; the program is a Free software replacement for the So, to extract from a bzip2-compressed tar-file:

bzip2 -d <archivefile. tar. bz2 | tar -xf -     or
bunzip2 <archivefile. tar. bz2 | tar -xf -

To create a bzip2-compressed tar-file:

tar -cf - filenames | bzip2 >archivefile. tar. bz2

GNU tar supports a -j flag, which allows creation of tar. GNU ( pronounced) is a computer Operating system composed entirely of Free software. bz2 files without a pipeline:

tar -cjf archivefile. tar. bz2 file-list

Decompressing in GNU tar:

tar -xjf archivefile. tar. bz2

Implementations

See also

External links

References

  1. ^ bzip2
  2. ^ $ dd if=/dev/zero bs=45899235 count=1 | bzip2 -vvvv | wc -c

    An even smaller file of 40 bytes can be achieved by using an input containing entirely values of 251, an apparent compression ratio of 1147480:1. The Lempel-Ziv-Markov chain-Algorithm ( LZMA) is an Algorithm used to perform Data compression. Mac OS is the trademarked name for a series of Graphical user interface -based Operating systems developed by Apple Inc Mac OS X (mæk oʊ ɛs tɛn is a line of computer Operating systems developed marketed and sold by Apple Inc, the latest of which is pre-loaded on all currently

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic