Écrivez un programme ou une fonction qui estime l'entropie de Shannon d'une chaîne donnée.

Si une chaîne a n caractères, d caractères distincts , x _i est le i ème caractère distinct et P (x _i ) est la probabilité que ce caractère se produise dans la chaîne, alors notre estimation d'entropie de Shannon pour cette chaîne est donnée par:

Pour l'estimation dans ce défi, nous supposons que la probabilité qu'un caractère apparaisse dans une chaîne est simplement le nombre de fois où il se produit divisé par le nombre total de caractères.

Votre réponse doit être précise à au moins 3 chiffres après la période.

Cas de test:

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

Gelée, 11 8 octets

ċЀ÷Ll.S

Essayez-le en ligne!

Python 3.3+, 64 octets

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

Vous avez math.log2de la solution de mbomb007 .

APL, 18 14 octets

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

Il s'agit d'un train de fonctions monadique sans nom qui accepte une chaîne à droite et renvoie un réel.

Comme toutes les bonnes choses de la vie, cela utilise la formule de xnor . Nous obtenons une matrice de booléens correspondant aux occurrences de chaque caractère dans la chaîne en utilisant ∘.=⍨, additionnons ceci le long du premier axe ( +/) pour obtenir le nombre d'occurrences de chaque caractère, divisons la longueur de la chaîne par chacun, puis prenons la base de log 2 ( 2⍟) et somme.

Essayez-le ici

4 octets enregistrés grâce à Dennis!

MATL, 17 octets

S4#Y'ts/tZl*sGn_*

Essayez-le en ligne!

JavaScript (ES6), 67 octets

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

Je dois utiliser ~-s.splitcar cela accepte les chaînes plutôt que les expressions régulières. Comme d'habitude, mapbat reduced'un octet.

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

Perl 5, 58 octets

Un sous-programme:

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

Un petit coup de chapeau à xnor pour la formule.

MATL , 14 octets

!Gu=stGn/Zl*s|

Essayez-le en ligne!

!      % 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 octets

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

Prend un tableau de caractères en entrée. Essayez-le en ligne!

J - 18 16 14 octets

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

Raccourci en utilisant l'idée de la méthode de Dennis.

Usage

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

Explication

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 octets

*_lQsm*FlBc/QdlQ{

Essayez-le en ligne ici .

Jolf, 26 octets

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

Essayez-le ici! (Notez que la fonction de la suite de tests est borked.)

Explication

_*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 octets

Solution simple. La version 3.3 est requise pour utiliser 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))

Essayez-le en ligne

Java 7, 207 octets

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;}

Essai détaillé en ligne

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;
}

Facteur, 98 octets

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

Ceci est une traduction directe de cette réponse Python . Je vais ajouter une explication au cours du dîner.

Raquette, 130 octets

: 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))))

Traduction de ma réponse Factor, c'est donc une traduction indirecte de la réponse Python de Kenny Lau.

k (32 octets)

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

Ou bien q, la traduction n'est pas si courte mais plus claire:

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

Mathematica, 45 octets

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

Usage

Cela renvoie des résultats exacts, nous les rapprochons donc de 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 octets

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

Explication

Prenez l'entrée de stdin et divisez-la en une liste de caractères. (Cette syntaxe maladroite est la raison pour laquelle les défis du golf à cordes sont si difficiles dans R ...)

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

Cette affectation est cachée à l'intérieur d'une lengthcommande, nous obtenons donc deux affectations pour le prix d'une. Nous avons i, la liste des caractères et lsa longueur.

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

Maintenant, nous calculons l'entropie. R a une belle fonction tablequi renvoie le nombre de toutes les valeurs uniques. Pour l'entrée This is a test, table(i)renvoie

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

Ceci est indexé par caractères, ce qui est bien, car nous pouvons ensuite l'utiliser icomme index pour obtenir le nombre de chaque caractère, comme ceci:

> 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 

Le reste du code est alors une simple implémentation de la formule d'entropie, retournée un peu.

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

C #, 159 octets

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)+"";}}

Non 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) + "";
}

Tester:

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 octets

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

Tests:

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