[r-t] Complexity of extents
holroyd at math.ubc.ca
Thu Jun 13 22:34:20 UTC 2013
This is an interesting and ptoentially tricky area.
In some sense the "true" measure is Kolmogorov Complexity, but that is a a
non-computable function. If you want something you can actually compute
and compare, then as Mark says, the size of the output of a standard
compression algorithm is probably your best bet. The obvious choice
Lempel-Ziv encoding, which is very simple to implement. (If you want to
do it properly, it's probably best to actually implement the algorithm and
understand what it is doing - existing file-compression programs probably
use all sorts of additional heuristics and add ons, so the output file
size may be a poor approximation to what we actually what, particularly
for the small file sizes that are relevant).
See e.g. wikipedia for deinitions of all these things.
It would be quite interesting, for example, to compare the sizes of the
Lempel-Ziv encodings of all the minimus extents (viewed as a lists of
place-notations). One complication is that extents are best viewed as
cycles, without a canonical starting point. One natural way to deal with
this is simply to use the rotation with the shortest compression.
But don't you have a monkey to work out these sort of things for you now,
On Thu, 13 Jun 2013, Philip Earis wrote:
> Give me some results, then, Marky!
> Sent from my iPad
> On 13 Jun 2013, at 22:34, "Mark Davies" <mark at snowtiger.net> wrote:
>> GACJ writes,
>>> Neat idea, Mark.
>> Claude Shannon, not me! I still remember that lecture at college - rocket.
>> ringing-theory mailing list
>> ringing-theory at bellringers.net
> This communication (including any attachments) is intended for the use of the addressee only and may contain confidential, privileged or copyright material. It may not be relied upon or disclosed to any other person without the consent of the RSC. If you have received it in error, please contact us immediately. Any advice given by the RSC has been carefully formulated but is necessarily based on the information available, and the RSC cannot be held responsible for accuracy or completeness. In this respect, the RSC owes no duty of care and shall not be liable for any resulting damage or loss. The RSC acknowledges that a disclaimer cannot restrict liability at law for personal injury or death arising through a finding of negligence. The RSC does not warrant that its emails or attachments are Virus-free: Please rely on your own screening. The Royal Society of Chemistry is a charity, registered in England and Wales, number 207890 - Registered office: Thomas Graham House, Science Park, Milton Road, Cambridge CB4 0WF
> ringing-theory mailing list
> ringing-theory at bellringers.net
More information about the ringing-theory