[r-t] Complexity of extents

[Alexander Holroyd]

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, 
Philip?

A

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.
>>
>> MBD
>>
>> _______________________________________________
>> ringing-theory mailing list
>> ringing-theory at bellringers.net
>> http://bellringers.net/mailman/listinfo/ringing-theory_bellringers.net
>
> DISCLAIMER:
>
> 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
> http://bellringers.net/mailman/listinfo/ringing-theory_bellringers.net
>