BARF - Revision history

Jsummers at 19:49, 6 June 2017

2017-06-06T19:49:58Z

Dan Tobias at 00:29, 4 August 2013

2013-08-04T00:29:42Z

Dan Tobias at 04:16, 21 December 2012

2012-12-21T04:16:41Z

Dan Tobias: Credit where credit due

2012-12-21T04:14:49Z

Credit where credit due

Dan Tobias at 14:40, 20 December 2012

2012-12-20T14:40:02Z

Dan Tobias at 14:18, 20 December 2012

2012-12-20T14:18:44Z

Dan Tobias at 13:56, 20 December 2012

2012-12-20T13:56:04Z

Dan Tobias at 13:53, 20 December 2012

2012-12-20T13:53:39Z

Dan Tobias: Created page with "{{FormatInfo |formattype=electronic |subcat=Compression |extensions={{ext|x}}, {{ext|x??}} }} '''BARF''' (Better Archiver with Recursive Functionality) is a sort of ''reducti..."

2012-12-20T13:49:36Z

Created page with "{{FormatInfo |formattype=electronic |subcat=Compression |extensions={{ext|x}}, {{ext|x??}} }} '''BARF''' (Better Archiver with Recursive Functionality) is a sort of ''reducti..."

New page

{{FormatInfo
|formattype=electronic
|subcat=Compression
|extensions={{ext|x}}, {{ext|x??}}
}}

'''BARF''' (Better Archiver with Recursive Functionality) is a sort of ''reductio ad absurdum'' of compression techniques, able to be run repeatedly on a file and always achieve greater compression, until you get a file of zero bytes in all cases. How do you decompress those files? Well, BARF kind of cheats.

Its algorithm consists of picking which one of 257 algorithms best compresses the file. The first algorithm is one which assigns each of the 14 files in the Calgary corpus (one benchmark test of compression algorithms) a single-byte compressed value from 0-13, and uses a simple LZ77 code with header byte 255 for all other files. (This can be expandable to a corpus of up to 255 files by using bytes 14-254 as well.) Thus you get maximum compression for the targeted test suite, some compression for much other data, and (as with all single compression algorithms), some files that actually expand in size on "compression" due to the pigeonhole principle showing that there just aren't a sufficient number of shorter bit sequences to encode all of a longer one.

The other 256 "algorithms" (#2-257) simply consist of removing the first byte from the file if it is equal to the algorithm number minus 2, and leaving the file alone otherwise. This is, as you can see, guaranteed to produce a file less than or equal to the size of the original, and one of them will always reduce the file size by one byte.

By picking the best compression of these algorithms at each stage, you can thus recursively compress any file to zero bytes. Exactly which algorithms are needed to reverse the compression are denoted by the file extensions, which are recursively appended to produce a potentially very long filename. The first algorithm above is noted by the extension '''.x''', while the others use '''.x''' followed by a two-digit base-26 encoding of n-2 (where n is the algorithm number), using digits 0-9 for the first digit and letters a-z for the second.

Thus, it cheats in two ways, by moving the bytes of arbitrary files into the filename (thus not actually achieving compression in most cases if the filenames need to be stored along with the data), and by using a specially-tailored high compression for the specific files of the benchmark test the author intended to win with this algorithm.

== References ==
* [http://mattmahoney.net/dc/barf.html Official site]

← Older revision		Revision as of 19:49, 6 June 2017
Line 23:		Line 23:
	* [http://mattmahoney.net/dc/barf.html Official site]		* [http://mattmahoney.net/dc/barf.html Official site]

−	[[Category:~~Geek humor~~]]	+	[[Category:Humor]]

@@ Line 8: / Line 8: @@
 '''BARF''' (Better Archiver with Recursive Functionality) is a sort of ''reductio ad absurdum'' of compression techniques, able to be run repeatedly on a file and always achieve greater compression, until you get a file of zero bytes in all cases. How do you decompress those files? Well, BARF kind of cheats.
-Its algorithm consists of picking which one of 257 algorithms best compresses the file. The first algorithm is one which assigns each of the 14 files in the Calgary corpus (one benchmark test of compression algorithms) a single-byte compressed value from 0-13, and uses a simple LZ77 code with header byte 255 for all other files. (This can be expandable to a corpus of up to 255 files by using bytes 14-254 as well.) Thus you get maximum compression for the targeted test suite, some compression for much other data, and (as with all single compression algorithms), some files that actually expand in size on "compression" due to the pigeonhole principle showing that there just aren't a sufficient number of shorter bit sequences to encode all of a longer one.
+Its algorithm consists of picking which one of 257 algorithms best compresses the file. The first algorithm is one which assigns each of the 14 files in the Calgary corpus (one benchmark test of compression algorithms) a single-byte compressed value from 0-13, and uses a simple LZ77 code with header byte 255 for all other files. (This can be expandable to a corpus of up to 255 files by using byte values 14-254 as well.) Thus you get maximum compression for the targeted test suite, some compression for much other data, and (as with all single compression algorithms), some files that actually expand in size on "compression" due to the pigeonhole principle showing that there just aren't a sufficient number of shorter bit sequences to encode all of a longer one.
 The other 256 "algorithms" (#2-257) simply consist of removing the first byte from the file if it is equal to the algorithm number minus 2, and leaving the file alone otherwise. (Well, actually, nitpickers would note that this action would produce a file indistinguishable from one where a byte was removed, and hence not a fully reversable step, so some scheme of adding flag bytes might have to be done... this is irrelevant, though, since none of the algorithms other than the one that removes a byte would ever be selected due to the meta-algorithm of picking only the smallest size.) This is, as you can see, guaranteed to produce a file less than or equal to the size of the original, and one of them will always reduce the file size by one byte.

@@ Line 18: / Line 18: @@
 A later program, BARF2 (linked on the same page as BARF, below), achieves compression down to zero bytes without expanding the filename, but this requires storing the number of times the compression algorithm was applied recursively, which ends up encoding the entire file as a huge number.
-BARF was created by the author of [[PAQ]].
+BARF was created by the author of [[PAQ]], Matt Mahoney.
 == References ==

← Older revision		Revision as of 14:40, 20 December 2012
Line 22:		Line 22:
	== References ==		== References ==
	* [http://mattmahoney.net/dc/barf.html Official site]		* [http://mattmahoney.net/dc/barf.html Official site]
		+
		+	[[Category:Geek humor]]

← Older revision		Revision as of 14:18, 20 December 2012
Line 15:		Line 15:

	Thus, it cheats in two ways, by moving the bytes of arbitrary files into the filename (thus not actually achieving compression in most cases if the filenames need to be stored along with the data), and by using a specially-tailored high compression for the specific files of the benchmark test the author intended to win with this algorithm.		Thus, it cheats in two ways, by moving the bytes of arbitrary files into the filename (thus not actually achieving compression in most cases if the filenames need to be stored along with the data), and by using a specially-tailored high compression for the specific files of the benchmark test the author intended to win with this algorithm.
		+
		+	A later program, BARF2 (linked on the same page as BARF, below), achieves compression down to zero bytes without expanding the filename, but this requires storing the number of times the compression algorithm was applied recursively, which ends up encoding the entire file as a huge number.

	BARF was created by the author of [[PAQ]].		BARF was created by the author of [[PAQ]].

@@ Line 10: / Line 10: @@
 Its algorithm consists of picking which one of 257 algorithms best compresses the file. The first algorithm is one which assigns each of the 14 files in the Calgary corpus (one benchmark test of compression algorithms) a single-byte compressed value from 0-13, and uses a simple LZ77 code with header byte 255 for all other files. (This can be expandable to a corpus of up to 255 files by using bytes 14-254 as well.) Thus you get maximum compression for the targeted test suite, some compression for much other data, and (as with all single compression algorithms), some files that actually expand in size on "compression" due to the pigeonhole principle showing that there just aren't a sufficient number of shorter bit sequences to encode all of a longer one.
-The other 256 "algorithms" (#2-257) simply consist of removing the first byte from the file if it is equal to the algorithm number minus 2, and leaving the file alone otherwise. This is, as you can see, guaranteed to produce a file less than or equal to the size of the original, and one of them will always reduce the file size by one byte.
+The other 256 "algorithms" (#2-257) simply consist of removing the first byte from the file if it is equal to the algorithm number minus 2, and leaving the file alone otherwise. (Well, actually, nitpickers would note that this action would produce a file indistinguishable from one where a byte was removed, and hence not a fully reversable step, so some scheme of adding flag bytes might have to be done... this is irrelevant, though, since none of the algorithms other than the one that removes a byte would ever be selected due to the meta-algorithm of picking only the smallest size.) This is, as you can see, guaranteed to produce a file less than or equal to the size of the original, and one of them will always reduce the file size by one byte.
 By picking the best compression of these algorithms at each stage, you can thus recursively compress any file to zero bytes. Exactly which algorithms are needed to reverse the compression are denoted by the file extensions, which are recursively appended to produce a potentially very long filename. The first algorithm above is noted by the extension '''.x''', while the others use '''.x''' followed by a two-digit base-26 encoding of n-2 (where n is the algorithm number), using digits 0-9 for the first digit and letters a-z for the second.

@@ Line 3: / Line 3: @@
 |subcat=Compression
 |extensions={{ext|x}}, {{ext|x??}}
 }}

@@ Line 14: / Line 14: @@
 Thus, it cheats in two ways, by moving the bytes of arbitrary files into the filename (thus not actually achieving compression in most cases if the filenames need to be stored along with the data), and by using a specially-tailored high compression for the specific files of the benchmark test the author intended to win with this algorithm.
 == References ==
 * [http://mattmahoney.net/dc/barf.html Official site]