From: madler@cco.caltech.edu (Mark Adler)
Newsgroups: alt.folklore.computers,sci.math,comp.compression
Subject: Re: Compressing decimal expansion of pi (was Re: PI)
Date: 22 Dec 1992 08:38:43 GMT
Organization: California Institute of Technology, Pasadena
NNTP-Posting-Host: sandman.caltech.edu


Interesting that this subject should come up.  I was just playing with
"compressing" pi myself.

>> A Huffman encoder would probably do  better on this
>> particular file - anybody care to try?

Sure.  First, I calculated what to expect.  Huffman coding bytes that
are just digits can be done with six 3-bit codes and four 4-bit codes,
which gives 3.4 bits per byte.  If you need an escape code of some
sort also, then perhaps five 3-bit codes, five 4-bit codes, and then
you have one code left for end-of-block or whatever.  That gives 3.5
bits per byte.

zip uses byte huffman coding, so I tried it on the first million or
so digits of pi:

1014396  Deflate 477191  53%  10-20-92  11:43  b8da0c9d   pi6.raw

This is about 3.76 bits per byte.  A little high.  Probably what's
happening is zip is occasionally finding matching strings, and then
wasting valuable Huffman codes on the length of the matches (almost
certainly 3 and maybe 4 since it searches a 32K space).

I wrote a quickie compressor geared entirely towards strings of
digits.  Digits are coded close to ideal in about 3.326 bits per
byte (the ideal is 3.322 bits per byte).  On the above it gives
a compressed file of 421696 bytes, which is only 477 bytes more
than the ideal 421219 bytes.

I have appended the source of the digit compressor and decompressor
(dig-in and dig-out) for your entertainment.

Mark Adler
madler@cco.caltech.edu
---- dig-in.c ----
/*
   dig-in	not copyrighted (n) by Mark Adler	21 Dec 1992

   dig-in compresses text files expected to consist almost entirely of
   decimal digits.  It is non-adaptive, fast, and simple, and comes close
   to getting ideal compression for random decimal digits.

   The basic strategy is to convert triples of decimal digits into
   10-bit binary values, since 1000 is less than, but close to 2^10.
   This codes three digits per 10 bits, or 3.333 bits per digit.  This
   is quite close to the ideal coding ratio of lg(10), which is 3.322
   bits per digit.  To do even better, a few of those are coded as
   nine bits (23 of them to be exact), which gives 3.3257 bits/digit.

   The remaining 10-bit value simply prefixes an arbitrary byte (eight
   bits).

   The coding is as follows:

      9 bits:   0..22		three digit values from 0..22
     10 bits:	23..511		three-digit values from 23..511
     10 bits:	535..1022	three-digit values from 512..999
     10 bits:	1023		prefix for eight bits that follow

   dig-in can be macro-ized to avoid function calls for faster execution.

 */

#include <stdio.h>

unsigned long bitbuf;
int bitcnt;


void putbits(b, n)
unsigned b, n;
/* write the n-bit value in b to stdout */
{
  bitbuf |= ((unsigned long)b) << bitcnt;
  bitcnt += n;				/* accumulate on top */
  while (bitcnt > 7)			/* write out from bottom */
  {
    putchar((int)bitbuf & 0xff);
    bitbuf >>= 8;
    bitcnt -= 8;
  }
}


void flush()
/* empty out the bit buffer */
{
  if (bitcnt)
    putchar((int)bitbuf & 0xff);
}


void putbyte(b)
int b;
/* write a byte prefix and the byte to the bit stream */
{
  putbits(1023, 10);
  putbits((unsigned)(b & 0xff), 8);
}


void putdigs(d, n)
unsigned d, n;
/* write one or two digits coded as bytes */
{
  if (n == 2)
  {
    putbyte('0' + d/10);
    putbyte('0' + d%10);
  }
  else		/* n == 1 */
    putbyte('0' + d);
}


void main()
/* real simple decimal digit compressor, stdin to stdout */
{
  int c;		/* last character read */
  unsigned d;		/* last digits read */
  unsigned n;		/* how many digits in d */

  bitcnt = 0;
  d = n = 0;
  while ((c = getchar()) != EOF)
  {
    if (c >= '0' && c <= '9')		/* accumulate digit */
    {
      d = (d << 3) + (d << 1) + c - '0';
      if (++n == 3)			/* write out digit triple */
      {
	putbits(d > 511 ? d + 23 : d, d < 23 ? 9 : 10);
	d = n = 0;
      }
    }
    else
    {
      if (n)
      {
	putdigs(d, n);			/* write out one or two digits */
	d = n = 0;
      }
      putbyte(c);			/* write non-digit */
    }
  }
  if (n)				/* write out leftover digits */
    putdigs(d, n);
  flush();				/* empty bit buffer */
}
---- dig-out.c ----
/*
   dig-out	not copyrighted (n) by Mark Adler	21 Dec 1992

   dig-out decompresses text files made by dig-in.  See the source
   file dig-in.c for the coding.

 */

#include <stdio.h>

void main(void)
/* real simple digit decompressor, stdin to stdout */
{
  unsigned long b;		/* bit buffer */
  int k;			/* bits in bit buffer */
  int c;			/* byte from stdin */
  int d;			/* three digits */

  b = 0;				/* clear bit buffer */
  k = 0;
  while (1)				/* do until we run out of input */
  {
    while (k < 9)			/* get at least 9 bits in buffer */
      if ((c = getchar()) == EOF)
	return;
      else
      {
	b |= ((unsigned long)c) << k;
	k += 8;
      }
    if ((d = (int)(b & 0x1ff)) < 23)	/* see if 9-bit code */
    {
      putchar('0');			/* decode 9 bits to three digits */
      putchar(d / 10 + '0');
      putchar(d % 10 + '0');
      b >>= 9;				/* pull 9 bits off buffer */
      k -= 9;
    }
    else				/* must be a 10-bit code */
    {
      if (k < 10)			/* get at least 10 bits in buffer */
	if ((c = getchar()) == EOF)
	  return;
	else
	{
	  b |= ((unsigned long)c) << k;
	  k += 8;
	}
      d = (int)(b & 0x3ff);		/* get 10-bit code */
      b >>= 10;				/* pull 10 bits off buffer */
      k -= 10;
      if (d != 1023)			/* see if byte prefix */
      {
        if (d > 511)			/* not byte prefix--decode digits */
	  d -= 23;			/* skip over codes 512..534 */
	putchar(d / 100 + '0');
	d = d % 100;
	putchar(d / 10 + '0');
	putchar(d % 10 + '0');
      }
      else				/* byte-prefix--get next eight bits */
      {
	if (k < 8)			/* get at least 8 bits in buffer */
	  if ((c = getchar()) == EOF)
	    return;
	  else
	  {
	    b |= ((unsigned long)c) << k;
	    k += 8;
	  }
	putchar((int)(b & 0xff));	/* write 8 bits */
	b >>= 8;			/* pull 8 bits from buffer */
	k -= 8;
      }
    }
  }
}
---- end ----