Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We're calculating entropy of a string a few places in Stack Overflow as a signifier of low quality.

I whipped up this simple method which counts unique characters in a string, but it is quite literally the first thing that popped into my head. It's the "dumbest thing that works".

/// <summary>
/// returns the # of unique characters in a string as a rough 
/// measurement of entropy
/// </summary>
public static int Entropy(this string s)
  var d = new Dictionary<char, bool>();
  foreach (char c in s)
      if (!d.ContainsKey(c)) d.Add(c, true);
  return d.Count();

Is there a better / more elegant / more accurate way to calculate the entropy of a string?

Efficiency is also good, though we never call this on large strings so it is not a huge concern.

share|improve this question
Your question reminded me of a Dr Dobbs article I read about 20 years ago. Fortunately, it's available online. It include simple .c code – Carlos Gutiérrez Feb 21 '11 at 19:05
Jeff, please tell me you are not trying to use this code to make it even harder to post short comments like “Yes.” by preventing users from adding dots or dashes... – Timwi Feb 23 '11 at 4:14
I don't know what you want to do with it, but one way to estimate entropy in data is to compress it, and take the length of the result. Length of the data is the upper bound of the entropy. The better the compressor program - the better estimate. – user9758 Jan 6 '12 at 18:16
Technically, a known string has no entropy; a process of producing strings has an entropy. What you are doing is hypothesizing a space of processes, estimating which process produced this string, and giving the entropy of that process. – Owen Jul 14 '13 at 14:06

13 Answers 13

Won't this work too?

string name = "lltt";
int uniqueCharacterCount = name.Distinct().Count();

will return 2

share|improve this answer
Given Distinct probably uses a HashSet, I think this is the most concise and clear implementation. – ICR Feb 20 '11 at 21:43
This is missing the point. The goal is to calculate the entropy of the string, not find a fancy way to count characters. Counting characters was one attempt (in the OP): counting characters more elegantly is not significantly better at calculating entropy. – Yakk Jan 13 '15 at 14:37
public static int Entropy(this string s)
    HashSet<char> chars = new HashSet<char>(s);
    return chars.Count;
share|improve this answer
I am always amazed at how simple algorithms can get, or, as in this case, completely vanish, by just using the right data structures. My favorite example is computing a histogram of discrete values, which is literally just new MultiSet(sourceData). – Jörg W Mittag Feb 21 '11 at 17:56

in theory you can measure entropy only from the point of view of a given model. For instance the PI digits are well distributed, but actually is the entropy high? Not at all since the infinite sequence can be compressed into a small program calculating all the digits.

I'll not dig further in the math side, since I'm not an expert in the field. But I want to suggest to you a few things that can make a very simple but practical model.

Short strings

To start, distribution. Comparing characters that are the same is exactly this in some way, but the generalization is to build a frequency table and check the distribution.

Given a string of length N, how many A chars should I expect in average, given my model (that can be the english distribution, or natural distribution)?

But then what about "abcdefg"? No repetition here, but this is not random at all. So what you want here is to take also the first derivative, and check the distribution of the first derivative.

it is as trivial as subtracting the second char from the first, the thrid from the second, so in our example string this turns into: "abcdefg" => 1,1,1,1,1,1

Now what aobut "ababab"... ? this will appear to have a better distribution, since the derivative is 1,-1,1,-1,... so what you actually want here is to take the absolute value.

Long strings

If the string is long enough the no brainer approach is: try to compress it, and calculate the ratio between the compression output and the input.

share|improve this answer
its tricky ... asdfghjkl; is a pretty crappy string as well – Sam Saffron Feb 20 '11 at 22:17
@Sam: your string will be actually flagged as low entropy by the first derivative test. Of course here you are changing the model, that is, accordingly to the position of chars in a keyboard, that is also a good model. You can add it to the mix as well of course. – antirez Feb 20 '11 at 22:19
very interesting approach. keep in mind our entropy tests are mainly there for really short strings. Here is the classic example of where we use it (… ) in conjunction with a few other algorithms – Sam Saffron Feb 20 '11 at 22:24
You cannot tell from looking at a string whether it is randomly produced (abc). If you pick 3 characters from an equal distribution, abc, aaa, zzz, zur and apk are of equal chance. Of course, in your example, you choosed the abcdef intentionally and not randomly, but this doesn't prove a random generator couldn't have formed it. – user unknown Feb 21 '11 at 11:59

I also came up with this, based on Shannon entropy.

In information theory, entropy is a measure of the uncertainty associated with a random variable. In this context, the term usually refers to the Shannon entropy, which quantifies the expected value of the information contained in a message, usually in units such as bits.

It is a more "formal" calculation of entropy than simply counting letters:

/// <summary>
/// returns bits of entropy represented in a given string, per 
/// </summary>
public static double ShannonEntropy(string s)
    var map = new Dictionary<char, int>();
    foreach (char c in s)
        if (!map.ContainsKey(c))
            map.Add(c, 1);
            map[c] += 1;

    double result = 0.0;
    int len = s.Length;
    foreach (var item in map)
        var frequency = (double)item.Value / len;
        result -= frequency * (Math.Log(frequency) / Math.Log(2));

    return result;

Results are:

"abcdefghijklmnop" = 4.00
"Hello, World!" = 3.18
"hello world" = 2.85
"123123123123" = 1.58
"aaaa" = 0
share|improve this answer
There are some subtleties here. What you're calculating there isn't the entropy of the string but the entropy of a character in the string. You should consider whether to include a pseudo-character with frequency 1 for the string terminator (a unary number has some content), and whether to multiply by the length of the string. – Peter Taylor Feb 22 '11 at 16:42
Sorry, just noticed this, this is equivalent to the code I later posted. Jeff, this is definitely a better solution; I think the most upvoted answer to this question is missing the point. – BlueRaja - Danny Pflughoeft Feb 24 '11 at 2:03
Here we see another case where a frequency data structure would be useful. var map = new FrequencyTable<char>(); foreach (char c in s) { map.Add(c); } – ICR Feb 27 '11 at 14:14
If you're not using the keys, would it not be more clear to do foreach (var value in map.Values)? – ICR Feb 27 '11 at 14:15
Not that it'd be a huge thing, but I'd lift the Math.Log(2) calculation out of the loop. – Jesse C. Slicer Nov 21 '11 at 19:15

How about actually computing entropy? Also, it's not clear that character-level entropy will help, but here goes. It's in my mother tongue C++, but surely you can convert this to Java using Array instead of std::vector.

float CharacterEntropy(const char *str) {
  std::vector<unsigned> counts(256);
  for (const char *i = str; *i; ++i)
    ++counts[static_cast<unsigned char>(*i)];
  unsigned int total = 0;
  for (unsigned i = 0; i < 256; ++i)
    total += counts[i];
  float total_float = static_cast<float>(total);
  float ret = 0.0;
  for (unsigned i = 0; i < 256; ++i) {
    float p = static_cast<float>(counts[i]) / total_float;
    ret -= p * logf(p);
  return p * M_LN2;
share|improve this answer
be careful that 0 * log(0) -> 0 – Neil G Feb 21 '11 at 0:25
It's not Java - I guess it's C#. In Java it is 'String' not 'string'. :) – user unknown Feb 21 '11 at 13:18

Similar to zngu's answer, I think better than just counting the number of characters would be calculating the character-entropy of the message:

public double CalculateEntropy(string entropyString)
    Dictionary<char, int> characterCounts = new Dictionary<char, int>();
    foreach(char c in entropyString.ToLower())
        if(c == ' ') continue;
        int currentCount;
        characterCounts.TryGetValue(c, out currentCount);
        characterCounts[c] = currentCount + 1;

    IEnumerable<double> characterEntropies = 
        from c in characterCounts.Keys
        let frequency = (double)characterCounts[c]/entropyString.Length
        select -1*frequency*Math.Log(frequency);

    return characterEntropies.Sum();

It seems to work well with both code and text, but note that it is not calculating the actual entropy of the string, only the entropy of the character-distribution; sorting the characters within the string should reduce the entropy of the string, but it does not reduce the result of this function.

Here are some tests:

private void CalculateEntropyTest(object sender, EventArgs e)
    string[] testStrings = {
        "Hello world!",
        "This is a typical english sentence containing all the letters of the english language - The quick brown fox jumped over the lazy dogs",
        String.Join("", "This is a typical english sentence containing all the letters of the english language - The quick brown fox jumped over the lazy dogs".ToCharArray().OrderBy(o => o).Select(o => o.ToString()).ToArray()),
        "Won't this work too?\nstring name = \"lltt\";\nint uniqueCharacterCount = name.Distinct().Count();\nwill return 2",
        "Pull the entropy finding source from any compression algotithm, i.e. Huffman",
        "float CharacterEntropy(const char *str) {\n  std::vector<unsigned> counts(256);\n  for (const char *i = str; *i; ++i)\n    ++counts[static_cast<unsigned char>(*i)];\n  unsigned int total = 0;\n  for (unsigned i = 0; i < 256; ++i)\n    total += counts[i];\n  float total_float = static_cast<float>(total);\n  float ret = 0.0;\n  for (unsigned i = 0; i < 256; ++i) {\n    float p = static_cast<float>(counts[i]) / total_float;\n    ret -= p * logf(p);\n  }\n  return p * M_LN2;\n}",
    foreach(string str in testStrings)
        Console.WriteLine("{0}\nEntropy: {1:0.000}\n", str, CalculateEntropy(str));

Hello world!
Entropy: 1.888

This is a typical english sentence containing all the letters of the english language - The quick brown fox jumped over the lazy dogs
Entropy: 2.593

-TTaaaaaaabccccddeeeeeeeeeeeeeeffgggggghhhhhhhiiiiiiiijk lllllllmnnnnnnnnnooooooppqrrrsssssssttttttttuuuvwxyyz
Entropy: 2.593

Won't this work too? string name = "lltt"; int uniqueCharacterCount = name.Distinct().Count(); will return 2
Entropy: 2.838

Pull the entropy finding source from any compression algotithm, i.e. Huffman
Entropy: 2.641

float CharacterEntropy(const char *str) { std::vector counts(256); for (const char *i = str; *i; ++i) ++counts[static_cast(*i)]; unsigned int total = 0; for (unsigned i = 0; i < 256; ++i) total += counts[i]; float total_float = static_cast(total); float ret = 0.0; for (unsigned i = 0; i < 256; ++i) { float p = static_cast(counts[i]) / total_float; ret -= p * logf(p); } return p * M_LN2; }
Entropy: 2.866

Entropy: 0.720

Entropy: 1.099

Entropy: 3.258

Entropy: 0.892

Actually, I think it would be better to do some frequency analysis, but I don't know anything about the frequencies of symbols used in code. The best place to determine that would be the stackoverflow data-dump - I'll have to get back to you after it finishes downloading, in 2 years.

share|improve this answer
  1. I don't understand the point of the bool. You never appear to set it to false, so we can use a List<T> instead.
  2. Given that you want just unique items, we can just use HashSet<T> instead.

Haven't tested, but this method should be equivalent and faster:

/// <summary>
/// returns the # of unique characters in a string as a rough 
/// measurement of entropy
/// </summary>
public static int Entropy(this string s)
    var hs = new HashSet<char>();
    foreach (char c in s)
    return hs.Count();
share|improve this answer
While I agree that using a HashSet is clearer than using a Dictionary and just ignoring its values, I don't see any reason why it would be faster. – sepp2k Feb 20 '11 at 21:45

Why not divide the number of unique characters in the given string by the total number of characters in that string. That would give a more accurate measure of entropy.

For example, going by your formula, an entropy of 3 for a string of 5 characters should be fine but an entropy of 3 for a string of 8 characters is poor. But, your formula wouldn't be able to differentiate between the two results. Whereas, the above given formula would do so to give a more accurate measure.

share|improve this answer

I think antirez is right in suggesting that an entropy approach needs a model. So assuming we're talking English, then examining the string's character distribution and how closely it aligns with "average" will likely show that the text is mostly English. But is this what you want to achieve? Presumable many things are code or pseudo-code. Compression is a great idea, but this'll give the highest entropy for random text - is high entropy bad? Low entropy would indicate lots of repetition, maybe verbosity, but one can write long drawn out sentences with frilly words and transmit little information (e.g. this comment).

share|improve this answer

You can probably expand this to something like bi-grams and tri-grams to get things like "sdsdsdsdsdsdsdsdsdsd" (although yours would catch this as well). Would a bayesian approach like spam filters do be appropriate for something like what you're trying to achieve?

share|improve this answer
the first derivative will catch this easily as well – antirez Feb 20 '11 at 22:04

I'm going to assume this is English (seeing as that's all we do). Wouldn't it be better to keep a HashSet<string> of stop words (the most common words in English that don't convey meaning), tokenize the string into words, and count the number of words that aren't stop words?

share|improve this answer

I just whipped this algorithm together, so I have no idea how good this is. I fear that it will cause an overflow exception if used on very long strings.

Key concepts of this algorithm:

  • When encountering a character for the first time, the maximum value is added to the un-normalized entropy total. The "maximum value" is the length of the string.
  • If a character is encountered again, then we count the number of positions between this occurrence and the last occurrence, then we subtract the total number of times this character has appeared in the string. We then add that value to the un-normalized entropy total.
  • Once the final un-normalized entropy total has been calculated, it is divided by the length of the string in order to "normalize" it.

    public static int Entropy(this string s)
        int entropy = 0;
        var mapOfIndexByChar = new Dictionary<char, CharEntropyInfo>();
        int index = 0;
        foreach (char c in s)
            CharEntropyInfo charEntropyInfo;
            if (mapOfIndexByChar.TryGetValue(c, out charEntropyInfo))
                // If this character has occurred previously, then only add the number of characters from
                // the last occurrence to this occurrence, and subtract the number of previous occurrences.
                // Many repeated characters can actually result in the entropy total being negative.
                entropy += ((index - charEntropyInfo.LastIndex) - charEntropyInfo.Occurrences);
                // update the last index and number of occurrences of this character
                mapOfIndexByChar[c] = new CharEntropyInfo(index, charEntropyInfo.Occurrences + 1);
                // each newly found character adds the maximum possible value to the entropy total
                entropy += s.Length;
                // record the first index of this character
                mapOfIndexByChar.Add(c, new CharEntropyInfo(index, 1));
        // divide the entropy total by the length of the string to "normalize" the result
        return entropy / s.Length;
    struct CharEntropyInfo
        int _LastIndex;
        int _Occurrences;
        public int LastIndex
            get { return _LastIndex; }
        public int Occurrences
            get { return _Occurrences; }
        public CharEntropyInfo(int lastIndex, int occurrences)
            _LastIndex = lastIndex;
            _Occurrences = occurrences;

A quick test:

        var inputs = new[]{
            "Hi there!",
            "Hi there, bob!",
            @"We're calculating entropy of a string a few places in Stack Overflow as a signifier of low quality.

I whipped up this simple method which counts unique characters in a string, but it is quite literally the first thing that popped into my head. It's the ""dumbest thing that works""."

        foreach (string s in inputs)
            System.Console.WriteLine("{1}: \"{0}\"", s, s.Entropy());

Resulting entropy values:

  • 7: "Hi there!"
  • 10: "Hi there, bob!"
  • -4: "ababababababababababababab"
  • 25: "We're calculating entropy of a string ..."
share|improve this answer

I would try to count each character and verify that it roughly matches the normal frequency of English letters. It could be more precise (on sufficiently large inputs) than counting the number of letters.

If you sort letters by their number of appearences, you should, statistically speaking, get something like ETAONRISHDLFCMUGYPWBVKXJQZ. You could use the edit distance between this string and the letters sorted by order of appearance to give a rough measurement of entropy.

Also, you could possibly catch non-English posts that way. (If you do go this way, I recommend you exclude code fragments from the count...)

share|improve this answer
As a second cut of the original count of unique characters, I was going to suggest calculating the variance of the count of each unique character. This way you won't bias it towards English and against code, but only require that some characters appear less often than others. – David Harkness Feb 20 '11 at 23:29

protected by Jamal Jan 8 '14 at 5:51

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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