Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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
    
Why a Dictionary as opposed to a List? –  Alex Humphrey Feb 20 '11 at 21:25
1  
1  
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 drdobbs.com/security/184408492 –  Carlos Gutiérrez Feb 21 '11 at 19:05
9  
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
3  
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

16 Answers 16

Won't this work too?

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

will return 2

share|improve this answer
14  
Given Distinct probably uses a HashSet, I think this is the most concise and clear implementation. –  ICR Feb 20 '11 at 21:43
public static int Entropy(this string s)
{
    HashSet<char> chars = new HashSet<char>(s);
    return chars.Count;
}
share|improve this answer
    
This is the way to go. –  John Gietzen Feb 21 '11 at 1:31
8  
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 neither an expert in the field, but want to suggest you a few things that can be 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.

Hope this helps.

share|improve this answer
    
its tricky ... asdfghjkl; is a pretty crappy string as well –  Sam Saffron Feb 20 '11 at 22:17
2  
@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 ( stackoverflow.com/review/… ) 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
1  
+1 for calculating the entropy after compressing the string. It is the best approach possible. –  Diego Sevilla Aug 29 '11 at 18:16

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 
/// http://en.wikipedia.org/wiki/Entropy_(information_theory) 
/// </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);
        else
            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
1  
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

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

share|improve this answer
5  
unfortunately for small strings this does not work, otherwise is an excellent idea. That is, just compress the string and check the difference in length with the plaintext. –  antirez Feb 20 '11 at 22:01

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}",
        "~~~~~~No.~~~~~~",
        "asdasdasdasdasdasd",
        "abcdefghijklmnopqrstuvwxyz",
        "Fuuuuuuu-------",                
    };
    foreach(string str in testStrings)
    {
        Console.WriteLine("{0}\nEntropy: {1:0.000}\n", str, CalculateEntropy(str));
    }
}

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

~~~~~~No.~~~~~~
Entropy: 0.720

asdasdasdasdasdasd
Entropy: 1.099

abcdefghijklmnopqrstuvwxyz
Entropy: 3.258

Fuuuuuuu-------
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

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

Well, just for fun, here is what I did on Woofer:

        // Too few characters.
        var distinctChars = status.ToCharArray().Distinct().Where(c=>!Char.IsWhiteSpace(c)).ToArray();
        if (distinctChars.Length < 12)
        {
            String chars = String.Empty; foreach(var @char in distinctChars) chars += @char + "-"; chars = chars.TrimEnd('-').Trim();
            return Error("Really?! 1400 characters and you can only use {0}? You can do better than that...", chars);
        }

The rest of this method also has some fun checks (all borne out of real pathological usage, sadly):

        // Is it pi or e?
        if (status.StartsWith("3.14159")) return Error("Hey math nerd... go read about Pi here: http://en.wikipedia.org/wiki/Pi");
        if (status.StartsWith("2.71828")) return Error("Hey math nerd... go read about e here: http://en.wikipedia.org/wiki/E_(mathematical_constant)");

        // Is it all numbers?
        Boolean anyLetters = false;
        foreach (var ch in distinctChars)
        {
            if (Char.IsLetter(ch)) { anyLetters = true; break; }
        }
        if (!anyLetters) return Error("Hey math nerd... woofer is for WORDS not just numbers!");

        // Is it all hex characters?
        Boolean allHex = true;
        foreach (var ch in distinctChars)
        {
            if (!"0123456789abcdefABCDEF".ToCharArray().Contains(ch)) { allHex = false; break; }
        }
        if (allHex) return Error("Are you a human or a computer? It looks like you're speaking in hex...");
share|improve this answer
    
Haha, very funny! –  Diego Sevilla Aug 29 '11 at 18:23

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
  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)
        hs.Add(c);
    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

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 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
1  
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

I see a lot of answers providing a way to count unique chars using linq, dictionaries, etc, and thought I should provide an option at the other end the other end of the scale ... just for the hell of it :)

if (string.IsNullOrEmpty(inString))
{
    return 0;
}
else
{
    char[] buffer = inString.ToCharArray();
    Array.Sort(buffer);
    int count = 1;

    for (int i = 1; i < buffer.Length; i++)
    {
        if (buffer[i - 1] != buffer[i]) count++
    }

    return count;
}
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);
            }
            else
            {
                // 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!",
            "ababababababababababababab",
            @"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

protected by Jamal Jan 8 at 5:51

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

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.