19
\$\begingroup\$

Write a program or function that estimates the Shannon entropy of a given string.

If a string has n characters, d distinct characters, xi is the i th distinct character, and P(xi) is the probability of that character occuring in the string, then our Shannon entropy estimate for that string is given by:

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

For the estimation in this challenge we assume that the probability of a character occurring in a string is simply the number of times it occurs divided by the total number of characters.

Your answer must be accurate to at least 3 digits after the period.


Test cases:

"This is a test.", 45.094
"00001111", 8.000
"cwmfjordbankglyphsvextquiz", 122.211
"             ", 0.0
\$\endgroup\$
  • \$\begingroup\$ Opposed to my usual challenges, this one looks complicated, but is actually quite simple :) \$\endgroup\$ – orlp Apr 25 '16 at 17:28
  • \$\begingroup\$ Related: codegolf.stackexchange.com/q/24316 \$\endgroup\$ – msh210 Apr 25 '16 at 17:56
  • \$\begingroup\$ Is it safe to assume printable ASCII for the input string? \$\endgroup\$ – AdmBorkBork Apr 25 '16 at 18:00
  • \$\begingroup\$ @TimmyD No. Any string that your language's string type supports. \$\endgroup\$ – orlp Apr 25 '16 at 18:02
  • \$\begingroup\$ Unfortunately, Mathematica's Entropy counts bits per character, not total for the string; oh well... \$\endgroup\$ – 2012rcampion Apr 26 '16 at 2:47

20 Answers 20

2
\$\begingroup\$

Jelly, 11 8 bytes

ċЀ÷Ll.S

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Can I ask, how you enter those characters? With copy and paste? \$\endgroup\$ – Bálint Apr 26 '16 at 9:49
  • \$\begingroup\$ At least on Linux, they can all be typed on the US international keyboard. \$\endgroup\$ – Dennis Apr 26 '16 at 14:44
11
\$\begingroup\$

Python 3.3+, 64 bytes

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

Got math.log2 from mbomb007's solution.

\$\endgroup\$
  • \$\begingroup\$ So @orlp didn't give us a fully simplified formula, eh...? \$\endgroup\$ – mbomb007 Apr 25 '16 at 20:37
  • \$\begingroup\$ @mbomb007 Depends for what purpose you're simplifying. Writing it in terms of probabilities and distinct characters is natural as a definition, but for golfing it's shorter to work with counts and iterate over all characters. \$\endgroup\$ – xnor Apr 25 '16 at 20:41
  • 1
    \$\begingroup\$ Pyth answer with your formula: pyth.herokuapp.com/… 8 bytes \$\endgroup\$ – Maltysen Apr 25 '16 at 20:54
2
\$\begingroup\$

APL, 18 14 bytes

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

This is an unnamed, monadic function train that accepts a string on the right and returns a real.

Like all good things in life, this uses xnor's formula. We get a matrix of booleans corresponding to the occurrences of each character in the string using ∘.=⍨, sum this along the first axis (+/) to get the number of occurrences of each character, divide the length of the string by each, then take log base 2 (2⍟) and sum.

Try it here

Saved 4 bytes thanks to Dennis!

\$\endgroup\$
1
\$\begingroup\$

MATL, 17 bytes

S4#Y'ts/tZl*sGn_*

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You may be able to save some bytes with Ym \$\endgroup\$ – Luis Mendo Apr 25 '16 at 21:55
1
\$\begingroup\$

JavaScript (ES6), 67 bytes

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

I need to use ~-s.split because that accepts strings rather than regexps. As usual, map beats reduce by a byte.

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

Perl 5, 58 bytes

A subroutine:

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

A tip of my hat to xnor for the formula.

\$\endgroup\$
  • \$\begingroup\$ -F doesn't work (in Strawberry, anyway) because it includes the $/. \$\endgroup\$ – msh210 Apr 25 '16 at 17:59
1
\$\begingroup\$

MATL, 14 bytes

!Gu=stGn/Zl*s|

Try it online!

!      % 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
\$\endgroup\$
1
\$\begingroup\$

Julia, 37 bytes

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

Takes a character array as input. Try it online!

\$\endgroup\$
1
\$\begingroup\$

J - 18 16 14 bytes

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

Shortened using the idea in Dennis' method.

Usage

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

Explanation

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
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think this counts as a function. If you assign the code to a variable, it does something entirely different. \$\endgroup\$ – Dennis Apr 26 '16 at 6:00
  • \$\begingroup\$ @Dennis From what I gather, it appears J interprets it as a chain of compositions, using 3 : '... y' with the same syntax would be a valid way to define it as a function. J states that it evaluates from right-to-left, so I've refactored my code as a train. I don't like caps [: but I can't find any other way to make a train. \$\endgroup\$ – miles Apr 26 '16 at 9:19
0
\$\begingroup\$

Pyth - 17 bytes

*_lQsm*FlBc/QdlQ{

Try it online here.

\$\endgroup\$
0
\$\begingroup\$

Jolf, 26 bytes

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

Try it here! (Note that the test suite function is borked.)

Explanation

_*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
\$\endgroup\$
0
\$\begingroup\$

Python 3.3+, 95 91 89 85 bytes

Simple solution. Version 3.3 is required to use 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))

Try it online

\$\endgroup\$
  • \$\begingroup\$ Do you think there's anything unnecessary here? n*sum(s.count(c)/n \$\endgroup\$ – orlp Apr 25 '16 at 20:11
  • \$\begingroup\$ @orlp Thanks. I originally had a separate function for finding the probability, but had pasted it inside twice and deleted it to save chars. \$\endgroup\$ – mbomb007 Apr 25 '16 at 20:16
  • \$\begingroup\$ You don't have to store n in a variable now that you only use it once. \$\endgroup\$ – Maltysen Apr 25 '16 at 20:32
0
\$\begingroup\$

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

Detailed try online

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;
}
\$\endgroup\$
0
\$\begingroup\$

Factor, 98 bytes

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

This is a direct translation of this Python answer. I'll add an explanation over dinner.

\$\endgroup\$
0
\$\begingroup\$

Racket, 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))))

Translation of my Factor answer, so it's an indirect translation of Kenny Lau's Python answer.

\$\endgroup\$
0
\$\begingroup\$

k (32 bytes)

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

Or in q, the translation is not all that short but clearer:

{neg sum c*2 xlog c%n:sum c:count each group x}
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 45 bytes

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

Usage

This returns exact results so we approximate them with 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.
\$\endgroup\$
0
\$\begingroup\$

R, 67 bytes

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

Explanation

Take input from stdin and split it into a list of characters. (This clunky syntax is why string golf challenges are so tough in R...)

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

This assignment is hidden inside of a length command, so we get two assignments for the price of one. We have i, the list of characters, and l, its length.

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

Now we calculate the entropy. R has a nice function table which returns the counts of all unique values. For input This is a test, table(i) returns

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

This is indexed by characters, which is nice, as we can then use i as an index to get the count of each character, like so:

> 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 

The rest of the code is then a simple implementation of the entropy formula, flipped around a little.

                                           -sum(log2(l/table(i)[i]))
\$\endgroup\$
0
\$\begingroup\$

C#, 159 bytes

Golfed:

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

Ungolfed:

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

Test:

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
\$\endgroup\$
0
\$\begingroup\$

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}

Tests:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.