Calculate the block entropy I once needed to write a function that calculates the block entropy of a given symbol series for a given block size and was surprised how short the result was. Thus I am challenging you to codegolf such a function. I am not telling you what I did for now (and in which language), but I will in a week or so, if nobody came up with the same or better ideas first.

Definition of the block entropy:

Given a symbol sequence A = A_1, …, A_n and a block size m:


A block of size m is a segment of m consecutive elements of the symbol sequence, i.e., A_i, …, A_(i+m−1) for any appropriate i.
If x is a symbol sequence of size m, N(x) denotes the number of blocks of A which are identical to x.
p(x) is the probability that a block from A is identical to a symbol sequence x of size m, i.e., p(x) = N(x)/(n−m+1)
Finally, the block entropy for block size m of A is the average of −log(p(x)) over all blocks x of size m in A or (which is equivalent) the sum of −p(x)·log(p(x)) over every x of size m occurring in A. (You can choose any reasonable logarithm you want.)


Restricions and clarifications:


Your function should take the symbol sequence A as well as the block size m as an argument.
You may assume that the symbols are represented as zero-based integers or in another convenient format.
Your program should be capable of taking any reasonable argument in theory and in reality should be able to calculate the example case (see below) on a standard computer.
Built-in functions and libraries are allowed, as long as they do not perform big portions of the procedure in one call, i.e., extracting all blocks of size m from A, counting the number of occurrences of a given block x or calculating the entropies from a sequence of p values – you have to do those things yourself.


Test:

[2, 3, 4, 1, 2, 3, 0, 0, 3, 2, 3, 0, 2, 2, 4, 4, 4, 1, 1, 1, 0, 4, 1,
2, 2, 4, 0, 1, 2, 3, 0, 2, 3, 2, 3, 2, 0, 1, 3, 4, 4, 0, 2, 1, 4, 3,
0, 2, 4, 1, 0, 4, 0, 0, 2, 2, 0, 2, 3, 0, 0, 4, 4, 2, 3, 1, 3, 1, 1,
3, 1, 3, 1, 0, 0, 2, 2, 4, 0, 3, 2, 2, 3, 0, 3, 3, 0, 0, 4, 4, 1, 0,
2, 3, 0, 0, 1, 4, 4, 3]


The first block entropies of this sequence are (for the natural logarithm):


m = 1: 1.599
m = 2: 3.065
m = 3: 4.067
m = 4: 4.412
m = 5: 4.535
m = 6: 4.554
Mathematica - 81 78 75 72 67 65 62 56 bytes

I haven't golfed anything in Mathematica before, so I suppose there's room for improvement. This one doesn't quite conform to the rules due to the Partition and Tally functions, but it's quite neat so I thought I'd post it anyway.

f=N@Tr[-Log[p=#2/Length@b&amp;@@@Tally[b=##~Partition~1]]p]&amp;


This works with any set of symbols, and can be used like

sequence = {2, 3, 4, 1, 2, 3, 0, 0, 3, 2, 3, 0, 2, 2, 4, 4, 4, 1, 1, 
   1, 0, 4, 1, 2, 2, 4, 0, 1, 2, 3, 0, 2, 3, 2, 3, 2, 0, 1, 3, 4, 4, 
   0, 2, 1, 4, 3, 0, 2, 4, 1, 0, 4, 0, 0, 2, 2, 0, 2, 3, 0, 0, 4, 4, 
   2, 3, 1, 3, 1, 1, 3, 1, 3, 1, 0, 0, 2, 2, 4, 0, 3, 2, 2, 3, 0, 3, 
   3, 0, 0, 4, 4, 1, 0, 2, 3, 0, 0, 1, 4, 4, 3};
f[sequence, 3]

&gt; 4.06663


Here is a somewhat ungolfed version:

f[sequence_, m_] := (
    blocks = Partition[sequence, m, 1];
    probabilities = Apply[#2/Length[blocks] &amp;, Tally[blocks], {1}];
    N[Tr[-Log[probabilities]*probabilities]]
)


It will probably run faster if I apply N directly to the result of Tally.

By the way, Mathematica does actually have an Entropy function, that reduces this to 28 bytes, but that's definitely against the rules.

f=N@Entropy@Partition[##,1]&amp;


On the other hand, here is a 128 byte version that reimplements Partition and Tally:

f=N@Tr[-Log[p=#2/n&amp;@@@({#[[i;;i+#2-1]],1}~Table~{i,1,(n=Length@#-#2+1)}//.{p___,{s_,x_},q___,{s_,y_},r___}:&gt;{p,{s,x+y},q,r})]p]&amp;


Ungolfed:

f[sequence_, m_] := (
    n = Length[sequence]-m+1; (*number of blocks*)
    blocks = Table[{Take[sequence, {i, i+m-1}], 1},
                   {i, 1, n}];
    blocks = b //. {p___, {s_, x_}, q___, {s_, y_}, r___} :&gt; {p,{s,x+y},q,r};
    probabilities = Apply[#2/n &amp;, blocks, {1}];
    N[Tr[-Log[probabilities]*probabilities]]
)