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!

| improve this answer | |
\$\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.

| improve this answer | |
\$\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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

MATL, 17 bytes

S4#Y'ts/tZl*sGn_*

Try it online!

| improve this answer | |
\$\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)
| improve this answer | |
\$\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.

| improve this answer | |
\$\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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Julia, 37 bytes

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

Takes a character array as input. Try it online!

| improve this answer | |
\$\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
| improve this answer | |
\$\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.

| improve this answer | |
\$\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
| improve this answer | |
\$\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

| improve this answer | |
\$\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;
}
| improve this answer | |
\$\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.

| improve this answer | |
\$\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.

| improve this 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}
| improve this answer | |
\$\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.
| improve this answer | |
\$\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]))
| improve this answer | |
\$\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
| improve this answer | |
\$\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
| improve this answer | |
\$\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.