# Compute the histogram entropy estimation of a string

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:

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

• Opposed to my usual challenges, this one looks complicated, but is actually quite simple :) – orlp Apr 25 '16 at 17:28
• – msh210 Apr 25 '16 at 17:56
• Is it safe to assume printable ASCII for the input string? – AdmBorkBork Apr 25 '16 at 18:00
• @TimmyD No. Any string that your language's string type supports. – orlp Apr 25 '16 at 18:02
• Unfortunately, Mathematica's Entropy counts bits per character, not total for the string; oh well... – 2012rcampion Apr 26 '16 at 2:47

# Jelly, 11 8 bytes

ċÐ€÷Ll.S


Try it online!

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

## 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.

• So @orlp didn't give us a fully simplified formula, eh...? – mbomb007 Apr 25 '16 at 20:37
• @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. – xnor Apr 25 '16 at 20:41
• Pyth answer with your formula: pyth.herokuapp.com/… 8 bytes – Maltysen Apr 25 '16 at 20:54

# 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!

# MATL, 17 bytes

S4#Y'ts/tZl*sGn_*


Try it online!

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

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


# 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.

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

# 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


# Julia, 37 bytes

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


Takes a character array as input. Try it online!

# J - 1816 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

• I don't think this counts as a function. If you assign the code to a variable, it does something entirely different. – Dennis Apr 26 '16 at 6:00
• @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. – miles Apr 26 '16 at 9:19

# Pyth - 17 bytes

*_lQsm*FlBc/QdlQ{


# 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


# Python 3.3+, 959189 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

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

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


# 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.

# 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.

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


# 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.


# 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]))


# 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


# 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