Escriba un programa o función que calcule la entropía de Shannon de una cadena dada.

Si una cadena tiene n caracteres, d caracteres distintos , x _i es el i carácter distinto y P (x _i ) es la probabilidad de que ese carácter ocurra en la cadena, entonces nuestra estimación de entropía de Shannon para esa cadena viene dada por:

Para la estimación en este desafío, suponemos que la probabilidad de que un carácter ocurra en una cadena es simplemente el número de veces que ocurre dividido por el número total de caracteres.

Su respuesta debe tener una precisión de al menos 3 dígitos después del período.

Casos de prueba:

"This is a test.", 45.094
"00001111", 8.000
"cwmfjordbankglyphsvextquiz", 122.211
"             ", 0.0

Jalea, 11 8 bytes

ċЀ÷Ll.S

Pruébalo en línea!

Python 3.3+, 64 bytes

import math
lambda s:sum(math.log2(len(s)/s.count(c))for c in s)

Conseguido math.log2de solución de mbomb007 .

APL, 18 14 bytes

+/2⍟≢÷(+/∘.=⍨)

Este es un tren de funciones monádicas sin nombre que acepta una cadena a la derecha y devuelve un real.

Como todas las cosas buenas de la vida, esto usa la fórmula de xnor . Obtenemos una matriz de booleanos correspondiente a las ocurrencias de cada carácter en la cadena usando ∘.=⍨, sumamos esto a lo largo del primer eje (+/ ) para obtener el número de ocurrencias de cada carácter, divide la longitud de la cadena por cada uno, luego toma la base de registro 2 ( 2⍟) y suma.

Pruébalo aquí

¡Guardado 4 bytes gracias a Dennis!

MATL, 17 bytes

S4#Y'ts/tZl*sGn_*

Pruébalo en línea!

JavaScript (ES6), 67 bytes

s=>[...s].map(c=>t+=Math.log2(s.length/~-s.split(c).length),t=0)&&t

Necesito usar ~-s.splitporque eso acepta cadenas en lugar de expresiones regulares. Como de costumbre, maplate reducepor un byte.

s=>[...s].reduce((t,c)=>t+Math.log2(s.length/~-s.split(c).length),0)

Perl 5, 58 bytes

Una subrutina:

{for$a(@a=split'',pop){$t+=(log@a/grep/\Q$a/,@a)/log 2}$t}

Una punta de mi sombrero para xnor para la fórmula.

MATL , 14 bytes

!Gu=stGn/Zl*s|

Pruébalo en línea!

!      % transpose implicit input into column vector
Gu     % row vector with unique elements of input
=      % test for equality, element-wise with broadcast
s      % sum of each column
tGn/   % duplicate. Divide by number of input characters
Zl     % binary logarithm
*      % element-wise multiplication
s      % sum of array
|      % absolute value. Display implicitly

Julia, 37 bytes

x->sum(log2(endof(x)./sum(x.==x',1)))

Toma una matriz de caracteres como entrada. Pruébalo en línea!

J - 18 16 14 bytes

1#.2^.#%1#.=/~

Acortado usando la idea en el método de Dennis.

Uso

   f =: 1#.2^.#%1#.=/~
   f 'This is a test.'
45.0936
   f '00001111'
8
   f 'cwmfjordbankglyphsvextquiz'
122.211
   f '             '
0

Explicación

1#.2^.#%1#.=/~  Input: string S
           =/~  Create a table testing for equality
        1#.     Convert each row from a list of base 1 digits to decimal
                This is equivalent to taking the sum and forms a list of tallies
      #         Get the length of S
       %        Divide the length by each tally
   2^.          Log base 2 of each
1#.             "Sum" those values and return

Pyth - 17 bytes

*_lQsm*FlBc/QdlQ{

Pruébelo en línea aquí .

Jolf, 26 bytes

_*liuΜGμiEd*γ/l miLeHlimzγ

Pruébalo aquí! (Tenga en cuenta que la función del conjunto de pruebas está modificada)

Explicación

_*liuΜGμiEd*γ/l miLeHlimzγ
       μi                   unique members of i
      G  E                  split on ""
     Μ    d                 map over function
               _miLeH       match i with regex escaped member
             /l      li     divide length of (^) by length of i
            γ               γ = (^)
           *           mzγ  (^) * log_2(γ)
 *li                        (^) * length of i
_                           negate

Python 3.3+, 95 91 89 85 bytes

Solución simple. Se requiere la versión 3.3 para usar math.log2.

import math
def f(s):C=s.count;return-sum(C(x)*math.log2(C(x)/len(s))for x in set(s))

Pruébalo en línea

Java 7, 207 bytes

double C(String x,Map<Character,Integer>f){double H=0,g;for(char c:x.toCharArray())f.put(c,f.containsKey(c)?f.get(c)+1:1);for(char c:f.keySet()){g=f.get(c);H+=g*Math.log(g/x.length())/Math.log(2);}return-H;}

Prueba detallada en línea

double log2(double d) { return Math.log(d) / Math.log(2); }

double C(String x, Map<Character,Integer>f)
{
    double H=0,g;

    // frequency
    for(char c : x.toCharArray())
    {
        f.put(c, f.containsKey(c) ? f.get(c)+1 : 1);
    }

    // calculate entropy
    for(char c : f.keySet())
    {
        g = f.get(c);
        H += g * log2(g / x.length());
    }

    return -H;
}

Factor, 98 bytes

[ [ length ] [ dup [ [ = ] curry dupd count ] { } map-as nip ] bi [ / log 2 log / ] with map sum ]

Esta es una traducción directa de esta respuesta de Python . Agregaré una explicación durante la cena.

Raqueta, 130 bytes

:C

#lang racket
(require math)(λ(S)(let([s(string->list S)])(sum(map(λ(c)(/(log(/(length s)(count(λ(x)(char=? c x))s)))(log 2)))s))))

Traducción de mi respuesta Factor, por lo que es una traducción indirecta de la respuesta Python de Kenny Lau.

k (32 bytes)

{-+/c*(log c%n:+/c:#:'=x)%log 2}

O en q, la traducción no es tan corta sino más clara:

{neg sum c*2 xlog c%n:sum c:count each group x}

Mathematica, 45 bytes

Tr[Log[2,Tr@#/#]#]&@Values@CharacterCounts@#&

Uso

Esto devuelve resultados exactos, por lo que los aproximamos con N.

  f = Tr[Log[2,Tr@#/#]#]&@Values@CharacterCounts@#&
  f["This is a test."]//N
45.0936
  f["00001111"]//N
8.
  f["cwmfjordbankglyphsvextquiz"]//N
122.211
  f["             "]//N
0.

R, 67 bytes

l=length(i<-strsplit(readline(),"")[[1]]);-sum(log2(l/table(i)[i]))

Explicación

Tome la entrada de stdin y divídala en una lista de caracteres. (Esta sintaxis torpe es la razón por la cual los desafíos del golf de cuerdas son tan difíciles en R ...)

         i<-strsplit(readline(),"")[[1]])

Esta asignación está oculta dentro de un lengthcomando, por lo que obtenemos dos asignaciones por el precio de una. Tenemos ila lista de caracteres y lsu longitud.

l=length(i<-strsplit(readline(),"")[[1]]);

Ahora calculamos la entropía. R tiene una buena función tableque devuelve los recuentos de todos los valores únicos. Para entrada This is a test, table(i)devuelve

> table(i)
i
  . a e h i s t T 
3 1 1 1 1 2 3 2 1

Esto está indexado por caracteres, lo cual es bueno, ya que luego podemos usarlo icomo índice para obtener el recuento de cada carácter, de esta manera:

> table(i)[i]
i
T h i s   i s   a   t e s t . 
1 1 2 3 3 2 3 3 1 3 2 1 3 2 1 

El resto del código es entonces una implementación simple de la fórmula de entropía, volteada un poco.

                                           -sum(log2(l/table(i)[i]))

C #, 159 bytes

Golfizado:

string f(string s){var l=s.Length;double sum=0;foreach(var item in s.GroupBy(o=>o)){double p=(double)item.Count()/l;sum+=p*Math.Log(p,2);}return(sum*=-l)+"";}}

Sin golf:

string f(string s)
{
  var l = s.Length;
  double sum = 0;
  foreach (var item in s.GroupBy(o => o))
  {
    double p = (double)item.Count() / l;
    sum += p * Math.Log(p, 2);
  }
  return (sum *= -l) + "";
}

Prueba:

var codeGolf = new StringHistogramEntropyEstimation();
    Console.WriteLine(codeGolf.f("This is a test.")); //45.0935839298008
    Console.WriteLine(codeGolf.f("00001111")); //8
    Console.WriteLine(codeGolf.f("cwmfjordbankglyphsvextquiz")); //122.211432671668
    Console.WriteLine(codeGolf.f("             ")); //0

Groovy, 100 bytes

{a->n=a.size();a.toList().unique().collect{p=a.count(it)/n;p*(Math.log(p)/Math.log(2.0f))}.sum()*-n}

Pruebas:

This is a test. = 45.09358393449714
00001111 = 8.0
cwmfjordbankglyphsvextquiz = 122.21143275636976
aaaaaaaa = -0.0