Re: Compression, encoding, entropy

From: David Mertz <voting-project_at_gnosis_dot_cx>
Date: Tue May 04 2004 - 03:10:58 CDT

Arthur Keller <arthur@kellers.org> wrote:
|I thought I did. I learned "base arithmetic" (like binary, base 4,
|base 8, etc.) in grade school.

Me too. But I didn't learn in grade school what particular quantity
every use of the word "base" refers to. :-)

I assumed (obviously incorrect now that I know what was unstated) that
you were establishing an (arbitrary) base to use relative to the log
bases in other parts of the formula. If it were arbitrary, e is as good
as anything else.

However, I'm pretty sure I didn't know about non-integer bases until
well after grade school. Actually, quite possibly I didn't even know
about integer bases until junior high... my recollection is fuzzy.

Anyway, trying octal rather than hexidecimal, I get the following (4
bits better for the demo). I'll post a generalized version tomorrow
that lets you indicate an alphabet size as an optional command-line
argument. But it's way too late now, and I should be asleep:

  % python election-entropy.py < demo-election.data
  Election summary for OVC demo ballot (write-ins count as candidate)

  269995136716800 distinct votes are possible
  Optimal encoding is approximately 48 bits
  Contests at bit-boundaries, approx 53 bits
  Contests self-delimited, approx 84 bits

  Vote Space Optimal Self-Delim
  ---------- ------- ----------
        9 4 6
        9 4 6
        4 2 3
        4 2 3
        5 3 6
        4 2 3
        5 3 6
        4 2 3
        3 2 3
        3 2 3
        3 2 3
      176 8 12
   109601 17 27
==================================================================
= The content of this message, with the exception of any external
= quotations under fair use, are released to the Public Domain
==================================================================
Received on Mon May 31 23:17:09 2004

This archive was generated by hypermail 2.1.8 : Mon May 31 2004 - 23:18:15 CDT