Uma vez eu precisei escrever uma função que calcula a entropia de bloco de uma determinada série de símbolos para um determinado tamanho de bloco e fiquei surpreso com o quão curto o resultado foi. Portanto, estou desafiando você a codificar essa função. Não estou lhe dizendo o que fiz por enquanto (e em que idioma), mas falarei daqui a uma semana, se ninguém tiver as mesmas ou melhores idéias primeiro.

Definição da entropia do bloco:

Dada uma sequência de símbolos A = A_1,…, A_n e um tamanho de bloco m:

• Um bloco de tamanho m é um segmento de m elementos consecutivos da sequência de símbolos, ou seja, A_i,…, A_ (i + m-1) para qualquer i apropriado.
• Se x é uma sequência de símbolos de tamanho m, N (x) indica o número de blocos de A que são idênticos a x.
• p (x) é a probabilidade de um bloco de A ser idêntico a uma sequência de símbolos x de tamanho m, ou seja, p (x) = N (x) / (n − m + 1)
• Finalmente, a entropia de bloco para o tamanho do bloco m de A é a média do log (p (x)) sobre todos os blocos x do tamanho m em A ou (o que é equivalente) a soma de -p (x) · log (p (x)) em cada x de tamanho m ocorrendo em A. (Você pode escolher qualquer logaritmo razoável que desejar.)

Restrições e esclarecimentos:

• Sua função deve usar a sequência de símbolos A e o tamanho do bloco m como argumento.
• Você pode assumir que os símbolos são representados como números inteiros baseados em zero ou em outro formato conveniente.
• Seu programa deve ser capaz de adotar qualquer argumento razoável em teoria e, na realidade, ser capaz de calcular o caso de exemplo (veja abaixo) em um computador padrão.
• Funções e bibliotecas integradas são permitidas, desde que não executem grandes partes do procedimento em uma chamada, ou seja, extraindo todos os blocos de tamanho m de A, contando o número de ocorrências de um determinado bloco x ou calculando as entropias a partir de uma sequência de valores p - você mesmo deve fazer essas coisas.

Teste:

[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]

As primeiras entropias de bloco desta sequência são (para o logaritmo natural):

• 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

Eu nunca joguei nada no Mathematica antes, então acho que há espaço para melhorias. Este não está de acordo com as regras devido às funções Partitione Tally, mas é bem legal, então pensei em publicá-lo de qualquer maneira.

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

Isso funciona com qualquer conjunto de símbolos e pode ser usado como

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]

> 4.06663

Aqui está uma versão um pouco não-destruída:

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

Provavelmente funcionará mais rápido se eu aplicar Ndiretamente ao resultado de Tally.

A propósito, o Mathematica realmente tem uma Entropyfunção, que reduz isso para 28 bytes , mas isso definitivamente é contra as regras.

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

Por outro lado, aqui está uma versão de 128 bytes que reimplementa Partitione Tally:

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

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___} :> {p,{s,x+y},q,r};
    probabilities = Apply[#2/n &, blocks, {1}];
    N[Tr[-Log[probabilities]*probabilities]]
)

Perl, 140 bytes

O script Perl a seguir define uma função Eque aceita a sequência de símbolos, seguida pelo tamanho do segmento como argumentos.

sub E{$m=pop;$E=0;%h=();$"=',';$_=",@_,";for$i(0..@_-$m){next
if$h{$s=",@_[$i..$i+$m-1],"}++;$E-=($p=s|(?=$s)||g/(@_-$m+1))*log$p;}return$E}

Versão ungolfed com teste

sub E { # E for "entropy"
    # E takes the sequence and segment size as arguments
    # and returns the calculated entropy.
    $m = pop;    # get segment size (last argument)
    $E = 0;      # initialize entropy
    %h = ();     # hash that remembers already calculated segments
    $" = ',';#"  # comma is used as separator
    $_ = ",@_,"; # $_ takes sequence as string, with comma as delimiters
    for $i (0 .. @_-$m) {
        $s = ",@_[$i..$i+$m-1],"; # segment
        next if$h{$s}++;          # check, if this segment is already calculated
        $p = s|(?=\Q$s\E)||g / (@_ - $m + 1); # calculate probability
             # N(x) is calculated using the substitution operator
             # with a zero-width look-ahead pattern
             # (golfed version without "\Q...\E", see below)
        $E -= $p * log($p); # update entropy
    }
    return $E
}

# Test

my @A = (
    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
);

print "m = $_: ", E(@A, $_), "\n" for 1 .. @A;

Resultado:

m = 1: 1.59938036027528
m = 2: 3.06545141203611
m = 3: 4.06663334311518
m = 4: 4.41210802885304
m = 5: 4.53546705894451
m = 6: 4.55387689160055
m = 7: 4.54329478227001
m = 8: 4.53259949315326
m = 9: 4.52178857704904
...
m = 97: 1.38629436111989
m = 98: 1.09861228866811
m = 99: 0.693147180559945
m = 100: 0

Símbolos:

Os símbolos não estão restritos a números inteiros, porque a correspondência de padrões com base em seqüências de caracteres é usada. A representação em cadeia de um símbolo não deve conter vírgula, pois é usada como delimitador. Obviamente, símbolos diferentes devem ter representações de cadeias diferentes.

Na versão golfed, a representação em cadeia dos símbolos não deve conter caracteres especiais de padrões. Os quatro bytes adicionais \Q... \E não são necessários para números.

Python 127 152B 138B

import math
def E(A,m):N=len(A)-m+1;R=range(N);return sum(math.log(float(N)/b) for b in [sum(A[i:i+m]==A[j:j+m] for i in R) for j in R])/N

Ajustado para não violar mais as regras e ter um algoritmo um pouco mais bonito. Ajustado para ser menor

Versão antiga:

import math
def E(A,m):
 N=len(A)-m+1
 B=[A[i:i+m] for i in range(N)]
 return sum([math.log(float(N)/B.count(b)) for b in B])/N

Meu primeiro script Python! Veja em ação: http://pythonfiddle.com/entropy

Python com Numpy, 146 143 bytes

Como prometido, aqui está minha própria solução. Requer uma entrada de números inteiros não negativos:

from numpy import*
def e(A,m):
    B=zeros(m*[max(A)+1]);j=0
    while~len(A)<-j-m:B[tuple(A[j:j+m])]+=1;j+=1
    return -sum(x*log(x)for x in B[B>0]/j)

A desvantagem é que isso explode sua memória por um grande mou max(A).

Aqui está a versão mais não comentada e comentada:

from numpy import *
def e(A,m):
    B = zeros(m*[max(A)+1])          # Generate (max(A)+1)^m-Array of zeroes for counting.
    for j in range(len(A)-m+1):
        B[tuple(A[j:j+m])] += 1      # Do the counting by directly using the array slice
                                     # for indexing.
    C = B[B>0]/(len(A)-m+1)          # Flatten array, take only non-zero entries,
                                     # divide for probability.
    return -sum(x*log(x) for x in C) # Calculate entropy

MATLAB

function E =BlockEntropy01(Series,Window,Base )

%-----------------------------------------------------------
% Calculates BLOCK ENTROPY of Series
% Series: a Vector of numbers
% Base: 2 or 10 (affects logarithm of the Calculation)
% for 2 we use log2, for 10 log10
% Windows: Length of the "Sliding" BLOCK
% E: Entropy
%-----------------------------------------------------------
% For the ENTROPY Calculations
% http://matlabdatamining.blogspot.gr/2006/....
% 11/introduction-to-entropy.html
% BlogSpot: Will Dwinnell
%-----------------------------------------------------------
% For the BLOCK ENTROPY
% http://codegolf.stackexchange.com/...
% questions/24316/calculate-the-block-entropy
%-----------------------------------------------------------
% Test (Base=10)
% Series=[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]';
%
% Results 
%
% Window=1: 1.599
% Window=2: 3.065
% Window=3: 4.067
% Window=4: 4.412
% Window=5: 4.535
% Window=6: 4.554
%-----------------------------------------------------------
n=length(Series);
D=zeros(n,Window); % Pre Allocate Memory
for k=1:Window;    D(:,k)=circshift(Series,1-k);end
D=D(1:end-Window+1,:); % Truncate Last Part
%
% Repace each Row with a "SYMBOL"
% in this Case a Number ...............
[K l]=size(D);
for k=1:K; MyData(k)=polyval(D(k,:),Base);end
clear D
%-----------------------------------------------------------
% ENTROPY CALCULATIONS on MyData
% following  Will Dwinnell
%-----------------------------------------------------------
UniqueMyData = unique(MyData);
nUniqueMyData = length(UniqueMyData);
FreqMyData = zeros(nUniqueMyData,1); % Initialization
for i = 1:nUniqueMyData
    FreqMyData(i) = ....
        sum(double(MyData == UniqueMyData(i)));
end
% Calculate sample class probabilities
P = FreqMyData / sum(FreqMyData);
% Calculate entropy in bits
% Note: floating point underflow is never an issue since we are
%   dealing only with the observed alphabet
if Base==10
    E= -sum(P .* log(P));
elseif BASE==2
    E= -sum(P .* log2(P));
else
end
end

WITH TEST SCRIPT 
%-----------------------------------------------------------
Series=[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]';
Base=10;
%-----------------------------------------------------------
for Window=1:6
    E =BlockEntropy01(Series,Window,Base )
end