Calcule la estimación de entropía del histograma de una cadena

19

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:

H = -n \ sum \ limits_ {i = 1} ^ d P (x_i) \ log_2 P (x_i)

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
orlp
fuente
En oposición a mis desafíos habituales, este parece complicado, pero en realidad es bastante simple :)
orlp
¿Es seguro asumir ASCII imprimible para la cadena de entrada?
AdmBorkBork
@TimmyD No. Cualquier cadena que admita el tipo de cadena de su idioma.
orlp
Desafortunadamente, Mathematica Entropycuenta bits por carácter, no total para la cadena; oh bien ...
2012 Arcampion

Respuestas:

2

Jalea, 11 8 bytes

ċЀ÷Ll.S

Pruébalo en línea!

Dennis
fuente
¿Puedo preguntar cómo ingresas esos caracteres? Con copiar y pegar?
Bálint
Al menos en Linux, todos se pueden escribir en el teclado internacional de EE. UU.
Dennis
11

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 .

xnor
fuente
Entonces @orlp no nos dio una fórmula completamente simplificada, ¿eh ...?
mbomb007
@ mbomb007 Depende del propósito que esté simplificando. Escribirlo en términos de probabilidades y caracteres distintos es una definición natural, pero para jugar al golf es más corto trabajar con conteos e iterar sobre todos los caracteres.
xnor
1
Pyth responde con tu fórmula: pyth.herokuapp.com/… 8 bytes
Maltysen
2

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!

Alex A.
fuente
1

MATL, 17 bytes

S4#Y'ts/tZl*sGn_*

Pruébalo en línea!

cubilete
fuente
Es posible que pueda guardar algunos bytes conYm
Luis Mendo
1

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)
Neil
fuente
1

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.

msh210
fuente
-Fno funciona (en fresa, de todos modos) porque incluye el $/.
msh210
1

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
Luis Mendo
fuente
1

Julia, 37 bytes

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

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

Dennis
fuente
1

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
millas
fuente
1
No creo que esto cuente como una función. Si asigna el código a una variable, hace algo completamente diferente.
Dennis
@ Dennis De lo que deduzco, parece que J lo interpreta como una cadena de composiciones, usar 3 : '... y'con la misma sintaxis sería una forma válida de definirlo como una función. J afirma que se evalúa de derecha a izquierda, por lo que he refactorizado mi código como tren. No me gustan las gorras [:pero no puedo encontrar otra forma de hacer un tren.
millas
0

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
Conor O'Brien
fuente
0

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

mbomb007
fuente
¿Crees que hay algo innecesario aquí? n*sum(s.count(c)/n
orlp
@orlp Gracias. Originalmente tenía una función separada para encontrar la probabilidad, pero la pegué dentro dos veces y la eliminé para guardar caracteres.
mbomb007
No tiene que almacenar nen una variable ahora que solo la usa una vez.
Maltysen
0

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;
}
Khaled.K
fuente
0

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.

gato
fuente
0

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.

gato
fuente
0

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}
skeevey
fuente
0

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.
millas
fuente
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]))
rturnbull
fuente
Guarde dos bytes (también su envío no funciona en TIO)
JayCe
0

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
Pete Arden
fuente
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
Urna de pulpo mágico
fuente