4
\$\begingroup\$

This is exercise 3.1.34. from the book Computer Science An Interdisciplinary Approach by Sedgewick & Wayne:

The Shannon entropy measures the information content of an input string and plays a cornerstone role in information theory and data compression. Given a string of n characters, let f(c) be the frequency of occurrence of character c. The quantity p(c) = f(c)/n is an estimate of the probability that c would be in the string if it were a random string, and the entropy is defined to be the sum of the quantity -p(c)*log2(p(c)), over all characters that appear in the string. The entropy is said to measure the information content of a string: if each character appears the same number times, the entropy is at its minimum value among strings of a given length. Write a program that takes the name of a file as a command-line argument and prints the entropy of the text in that file. Run your program on a web page that you read regularly, a recent paper that you wrote, and the E. coli genome found on the website.

Here is my program:

public class ShannonEntropy
{
    public static String removeUnnecessaryChars()
    {
        String text = "";
        while (!StdIn.isEmpty())
        {
            String word = StdIn.readString();
            int wordLength = word.length();
            String newWord = "";
            for (int i = 0; i < wordLength; i++)
            {
                if (word.charAt(i) != '.' &&
                    word.charAt(i) != '!' &&
                    word.charAt(i) != '?' &&
                    word.charAt(i) != ',' &&
                    word.charAt(i) != '"' &&
                    word.charAt(i) != ':' &&
                    word.charAt(i) != ';' &&
                    word.charAt(i) != '(' &&
                    word.charAt(i) != ')')
                    {
                        newWord += word.charAt(i);
                    } 
            }
            text += newWord;
        }
        return text.toLowerCase();
    }
    // this method (below) is written specifically for texts without
    // unnecessary characters (e.g. E. coli genome)
    public static String convertTextToString() 
    {
        String text = "";
        while (!StdIn.isEmpty())
        {
            String word = StdIn.readString();
            text = word;
        }
        return text;
    }
    public static int[] findFrequencies(String text)
    {
        int textLength = text.length();
        /*
        char[] ALPHABET = {'a','b','c','d','e','f','g','h','i','j','k','l',
                           'm','n','o','p','q','r','s','t','u','v','w','x',
                           'y','z'};
        */
        char[] ALPHABET = {'a','c','g','t'}; // specifically used for genes and genomes
        int[] frequencies = new int[ALPHABET.length];
        for (int i = 0; i < textLength; i++)
        {
            for (int j = 0; j < ALPHABET.length; j++)
            {
                if (text.charAt(i) == ALPHABET[j])
                {
                    frequencies[j]++;
                    break; // to speed up the computation
                }
            }
        }
        return frequencies;
    }
    public static double[] findProbabilities(String text, int[] frequencies)
    {
        int textLength = text.length();
        int n = frequencies.length;
        double[] probabilities = new double[n];
        for (int i = 0; i < n; i++)
        {
            probabilities[i] = (double) frequencies[i]/textLength;
        } 
        return probabilities;
    }
    public static double log2(double x)
    {
        return (Math.log(x)/Math.log(2));
    }
    public static double calculateEntropy(double[] probabilities)
    {
        double shannonEntropy = 0;
        int n = probabilities.length;
        for (int i = 0; i < n; i++)
        {
            if (probabilities[i] != 0)
            {
                shannonEntropy += probabilities[i]*log2(probabilities[i]);
            }
        }
        return -1*shannonEntropy;
    }
    public static void main(String[] args)
    {
        //final long time1 = System.currentTimeMillis();
        //String text = removeUnnecessaryChars();
        String text = convertTextToString();
        //final long time2 = System.currentTimeMillis();
        //System.out.println("Time to remove unnecessary characters: " + (time2-time1) + " ms");
        int[] frequencies = findFrequencies(text);
        //final long time3 = System.currentTimeMillis();
        //System.out.println("Time to calculate character frequencies: " + (time3-time2) + " ms");
        double[] probabilities = findProbabilities(text, frequencies);
        System.out.println("Shannon entropy of the E. coli genome: " + calculateEntropy(probabilities));
        String randomGene = "";
        for (int i = 0; i < 1000000; i++)
        {
            double r = Math.random();
            if      (r < 0.25) randomGene += "a";
            else if (r < 0.50) randomGene += "c";
            else if (r < 0.75) randomGene += "g";
            else if (r < 1.00) randomGene += "t";
        }
        int[] rFrequencies = findFrequencies(randomGene);
        double[] rProbabilities = findProbabilities(randomGene, rFrequencies);
        System.out.println("Shannon entropy of the random genome: " + calculateEntropy(rProbabilities));
    }
}

StdIn is a simple API written by the authors of the book. Here is one instance of my program:

Input: E. coli genome

Output:


Shannon entropy of the E. coli genome: 1.9998212455541713 (which is exactly compatible with the answer from Online Shannon entropy calculator)

Shannon entropy of the random genome: 1.9999979438235416


Is there any way that I can improve my program (especially its performance (especially the method removeUnnecessaryChars))?

Thanks for your attention.

\$\endgroup\$
2
  • \$\begingroup\$ Not your fault, and not really relevant to the question I suppose, but this is not "the Shannon entropy". It's the entropy of the string according to an order-0 model trained on the string itself. It's fine as an exercise, but you shouldn't use it in production code unless someone who understands information theory clears you to use it. Anyone who calls it "the Shannon entropy" probably doesn't understand information theory. \$\endgroup\$ – benrg Sep 6 '20 at 21:13
  • \$\begingroup\$ @benrg Thank you very much for the clarification. I haven't studied information theory yet. \$\endgroup\$ – Khashayar Baghizadeh Sep 6 '20 at 21:53
3
\$\begingroup\$

In Java, we typically place open braces on the same line, not a newline.

Since you're specifically interested in removeUnnecessaryChars...

  • using a Set<Character> to hold the collection would be cleaner than enumerating them in the method.

  • You've got a nested loop, but then you're just smooshing everything together into one string anyway.

  • This method is only called inside its containing class, so it should be private. Minimize scope where possible.

  • It would be preferable if it took an argument rather than relying on the static class StdIn, but I'll assume this is an artifact of the assignment.

  • Note that convertTextToString and removeUnnecessaryChars operate differently on an identical input with no unnecessary characters. I expect there's a bug in convertTextToString.

  • The streaming version could be prettier if StdIn gives useful streaming methods, but I don't know the API of that class. Using only what you've revealed, I took a stab at it. I'm pretty sure you could also make the Set a Set<Integer>, keep the rest of that declaration, and skip the mapToObj step, but it's past my bedtime.

If I were to rewrite it, it might look something like (untested!)

private static final Set<Character> CHARACTERS_TO_IGNORE = Set.of('.', '!', '?', ',', '"', ':', ';', '(', ')');

public static String removeUnnecessaryChars() {
    String text = "";
    while (!StdIn.isEmpty()) {
        for (char c : StdIn.readString().toCharArray()) {
            if (!CHARACTERS_TO_IGNORE.contains(c)) {
                text += c;
            }
        }
    }
    return text;
}

public static String removeUnnecessaryChars() {
    String text = "";
    while (!StdIn.isEmpty()) {
        text += StdIn.readString()
            .chars()
            .mapToObj(i -> (char)i)
            .filter(c -> !CHARACTERS_TO_IGNORE.contains(c))
            .collect(Collectors.joining);
    }
    return text;
}
\$\endgroup\$
3
\$\begingroup\$

The thinking behind the code is very good. You have split the tasks into the required methods very well. You could make some improvements still.

For example, this line is a little off, looks like negation. It's just an interesting way to do it.

return -1*shannonEntropy;

This line, you could derive the alphabet from the text, the distinct characters.

char[] ALPHABET = {'a','c','g','t'};

You are doing a large amount of looping over the text, and the alphabet, then the frequencies, then the probabilities, etc. Is there any way to do it all with minimal looping?

Your first loops, there is no need for the inner loop on alphabet. Just increment the count of a characters in the text and accumulate a count of the characters present - no need to even specify an alphabet - ... something like this.

Dictionary<char, int> frequencies = new Dictionary<char, int>();
for (int i = 0; i < text.Length; i++)
{
    if (!frequencies.ContainsKey(text[i]))
    {
        frequencies.Add(text[i], 0);
    }
    frequencies[text[i]]++;
}

Next, there is no need for separate loops to calculate probability and character entropy. Both those calculations can be done on the same loop and a running total kept.

double totalEntropy;
foreach (KeyValuePair<char, int> frequency in frequencies)
{
    double probability = ...;
    double entropy = ...;

    totalEntropy += entropy;
}

That would keep looping to a minimal.

\$\endgroup\$
3
  • \$\begingroup\$ Thank you very much. :) \$\endgroup\$ – Khashayar Baghizadeh Sep 6 '20 at 19:46
  • 3
    \$\begingroup\$ This looks like C# rather than Java. \$\endgroup\$ – ggorlen Sep 6 '20 at 20:33
  • \$\begingroup\$ it is c#; pretty sure it can be translated. \$\endgroup\$ – null Sep 7 '20 at 7:29

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.