From turk@Apple.COM (KenTurkowski) Thu May 2 20:46:11 1991 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1587" "" " 2" "May" "1991" "00:09:09" "GMT" "Ken \"Turk\" Turkowski" "turk@Apple.COM" nil "39" "Re: Compressing real values?" "^From:" nil nil "5" nil nil nil nil] nil) Newsgroups: comp.compression Organization: Advanced Technology Graphics, Apple Computer, Cupertino, CA, USA From: turk@Apple.COM (Ken "Turk" Turkowski) Subject: Re: Compressing real values? Date: 2 May 91 00:09:09 GMT jbaker@gmuvax2.gmu.edu (John Baker) writes: >We need to compress a series of real values to transfer over a network >for a parallel program in Linda. The values are somewhat related, >but a maximum difference is not always guaranteed. >What I would like is a program to compress the differences such that >smaller differences take fewer bytes. This is trivial for integers, >but not necessarily reals. I would think there would be some variant of >arithmetic coding to do this. >Alternatively, we could assume differences fit into n bits with a >special case if the value is too large, but this method probably would >be less effective. Here's a few methods: * Why don't you just not send the least significant zeros? * Another way is to subtract two floating-point numbers as though they were integers (i.e. hack it with a union). IEEE floating-point numbers are very similar to integers for comparison purposes: if two numbers have the same sign, then comparing them as integers produces the same results as subtracting them as floats and checking the sign. If two floating-point numbers are close to each other, then subtracting them as integers will produce a small integer. You then throw out the most significant zeros. * Scan the data set for the dynamic range of the data or their differences, convert to fixed-point, and compress them as integers. This method, unlike the previous two (which are lossless), is inherently lossy. -- Ken Turkowski @ Apple Computer, Inc., Cupertino, CA Internet: turk@apple.com Applelink: TURK UUCP: sun!apple!turk From spencer@eecs.umich.edu Thu May 30 23:41:29 1991 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["169" "" "29" "May" "1991" "16:29:38" "GMT" "Spencer W. Thomas" "spencer@eecs.umich.edu" nil "5" "Re: JPEG compression" "^From:" nil nil "5" nil nil nil nil] nil) Newsgroups: comp.compression Organization: University of Michigan EECS Dept In-Reply-To: pshuang@athena.mit.edu's message of Sun, 26 May 91 23: 18:55 GMT From: spencer@eecs.umich.edu (Spencer W. Thomas) Subject: Re: JPEG compression Date: 29 May 91 16:29:38 GMT See Communications of the ACM, April, 1991. -- =Spencer W. Thomas EECS Dept, U of Michigan, Ann Arbor, MI 48109 spencer@eecs.umich.edu 313-936-2616 (8-6 E[SD]T M-F) From ross@spam.ua.oz.au Thu May 30 23:44:26 1991 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["2511" "" "29" "May" "1991" "15:53:31" "GMT" "Ross Williams" "ross@spam.ua.oz.au" nil "50" "Re: SAKDC availability?" "^From:" nil nil "5" nil nil nil nil] nil) Newsgroups: comp.compression Summary: SAKDC won't be out for a while folks... Keywords: sakdc data compression algorithm ppm ppmc Followup-To: comp.compression Organization: Statistics, Pure & Applied Mathematics, University of Adelaide From: ross@spam.ua.oz.au (Ross Williams) Subject: Re: SAKDC availability? Date: 29 May 91 15:53:31 GMT >Are there any freely available implementations of Ross Williams' SAKDC? >How does it compare with other compressors? SAKDC is at this stage not very accessible or portable. Reasons: * It is written in Ada. * It has some VMS specific code. * From memory, it is about 5000 lines of code. * It was written using a preprocessor called FunnelWeb (like Knuth's Web). * FunnelWeb is written in Ada. * FunnelWeb is highly VMS specific (e.g. it $crmpsc the input file). * The whole lot is on a VAX backup tape somewhere along with a whole lot of other stuff. * I don't have easy access to a VMS VAX or a VAX Ada compiler. I will release the sources eventually (probably in a year or so). If anyone wants them earlier, they are welcome to throw money at me. Alternatively they could re-implement the algorithm based on my book. As far as I am aware, SAKDC gives the best compression of ANY algorithm in existence (if you can do better - scream out!). Evidence for this can be found in my book and the Bell book. Table B-1 of the Bell book gives the compression performance on the Calgary (Bell) corpus for 18 algorithms. The best compression is given by the Markov algorithms of which PPMC is the best, yielding 2.48 bits per symbol (the next closest is 2.74). From the O20000 column of Table 39 of my book (and omitting the files paper3..paper6 as Bell Cleary and Witten did) SAKDC yielded 2.464 bits per symbol. This was using a large amount of memory. For a small amount of memory (200 nodes), SAKDC yields about 18% (absolute) better compression than PPMC (3.344b/s vs 4.784b/s (includes paper3-paper6)). Most of the credit for the performance of SAKDC belongs to Cleary and Witten who devised the basic engine of SAKDC (PPM) and Moffat who tuned the engine (PPMC). I just gave the engine a thorough tune up and introduced structural adaptivity. You can read all about it in Chapter four of my book... Of course SAKDC runs as fast as a sedated sloth - what did you expect? The best speed ever obtained was about 300 bytes per second on a Vax750. I am sure it could be made much faster though - at the time I was not much interested in speed. Moffat has clocked PPMC (which has similar data structures) at 4K/sec on a Sun3 so it should be possible to get SAKDC up around there too. SAKDC stands for Swiss Army Knife Data Compression because the algorithm has so many parameters. Ross Williams ross@spam.ua.oz.au