Entropy of String in C

Question

I have written a C program that calculates Shannon entropy for a C-String (const char *). It works well but in many implementation the code uses some-kind of map like structures which are available by default in their respective language. But we all know C does not have maps. My code is very fast even for 100 megabytes of data.

Here's the formula to calculate Shannon entropy

$$ {\displaystyle \mathrm {H} (X)=-\sum _{i=1}^{n}{\mathrm {P} (x_{i})\log \mathrm {P} (x_{i})}} $$

Can anyone suggest me even more efficient way to calculate the entropy in C? Any kind of suggestion or improvement is appreciated.

Here's my code: TRY IT ONLINE

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

static double entropy(const char *str)
{
    if (!str) // return -1 is str is NULL
        return -1.0;

    size_t len = strlen(str); // get the length of str

    /*
     * cnt -> iterate over the str
     * map_append -> stores the index of unique character in str
     * imap_append -> stores the index of non-unique character in str
     */
    size_t cnt = 0, map_append = 0, imap_append = 0;

    int check = false; // boolean type value to store whether char is unique or not

    char *map_char = (char *)calloc(len + 1, sizeof(char));      // heap allocation to store unique characters
    size_t *map_cnt = (size_t *)calloc(len + 1, sizeof(size_t)); // heap allocation to store the freq. of unique characters

    for (cnt = 0; cnt < len; cnt++)
    {
        check = false;
        for (imap_append = 0; map_char[imap_append] != '\0'; imap_append++)
        {
            if (map_char[imap_append] == str[cnt])
            {
                check = true; // char is not unique
                break;
            }
        }
        if (check == false) // char is unique
        {
            map_char[map_append] = str[cnt];
            map_cnt[map_append] = 1;
            map_append++;
            // add it to the `map_char` and set `map_cnt` value to 1
        }
        else
            map_cnt[imap_append] += 1; // just increment the freq. of that not-unique char, at `imap_append`
    }

    /* just the application of the formula */
    double result = 0.0;
    double freq = 0.0;
    for (size_t i = 0; map_char[i] != '\0'; i++)
    {
        freq = (double)map_cnt[i] / (double)len;
        result -= freq * (log10(freq) / log10(2.0));
    }
    free(map_char); // no mem leaks
    free(map_cnt);  // no mem leaks
    return result;
}

int main(int argc, char const **argv)
{
    if (argc == 1)
    {
        fprintf(stderr, "no file input\n");
        return EXIT_FAILURE;
    }
    FILE *f = fopen(argv[1], "r");
    if (!f)
    {
        fprintf(stderr, "`%s` could not be opened or was not found.\n", argv[1]);
        return EXIT_FAILURE;
    }
    fseek(f, 0, SEEK_END);
    size_t len = ftell(f);
    fseek(f, 0, SEEK_SET);
    char *data = (char *)calloc(len, sizeof(char));
    fread(data, sizeof(char), len, f);
    fclose(f);
    printf("Length of file: `%s` = %zu\n", argv[1], len);
    printf("Entropy of file: `%s` = %f\n", argv[1], entropy((const char *)data));
    return EXIT_SUCCESS;
}

I compiled the above program using the command:

gcc -Og -O3 -Ofast -Os -s main.c -lm -o main

My output was: (That 100MB file was generated by random ASCII characters)

Length of file: `./temp.txt` = 104857600
Entropy of file: `./temp.txt` = 6.569855

Here's a benchmark on a 100 megabytes file on zsh shell on Intel i5-7200U:

./main ./temp.txt  4.54s user 0.06s system 99% cpu 4.598 total

Answer 1

Some general remarks

You include <stdbool.h>, but still use int check to hold a boolean value. That should be bool check.

The check if (check == false) can be shorted to if (!check).

Memory allocation can fail, you have to check the return value of the calloc() calls. In the case of a failure you have to decide how to report that to the caller.

Some variables can be declared at a narrower scope, e.g.

double freq = 0.0;
for (size_t i = 0; map_char[i] != '\0'; i++)
{
    freq = (double)map_cnt[i] / (double)len;
    // ...
}

should be

for (size_t i = 0; map_char[i] != '\0'; i++)
{
    double freq = (double)map_cnt[i] / (double)len;
    // ...
}

Possible improvements of the algorithm

A char has 8 bits on most platforms (including all POSIX platforms). In that case there are only 255 different characters, plus the null character as the terminator.

Which means that it always suffices to allocate the tables which space for 256 entries (or 1 << CHAR_BIT, in general). CHAR_BIT and related constants are defined in <limits.h>.

That saves a lot of space if the input string is long. It also allows to make the tables local stack arrays and get rid of calloc():

char map_char[1 << CHAR_BIT] = { 0 };
size_t map_cnt[1 << CHAR_BIT] = { 0 };

Even better: Use the character itself as the index into the table, so that the inner loop becomes obsolete:

size_t frequencies[1 << CHAR_BIT] = { 0 };
for (const char *p = str; *p != 0; p++) {
    frequencies[*p - CHAR_MIN]++;
}

The computation of the entropy then works are before, only that zero frequencies must be skipped:

size_t len = strlen(str);
double result = 0.0;
for (int i = 0; i < 1 << CHAR_BIT; i++) {
    if (frequencies[i] != 0) {
        double freq = (double)frequencies[i] / (double)len;
        result -= freq * (log(freq) / log(2.0));
    }
}

Processing large files

It is not necessary to read the entire file into memory. You can read it in chunks, update the frequency table for each chunk, and finally compute the entropy.

That saves a lot of space for large input files.

Answer 2

This code allocates memory (using calloc()) but fails to handle a null pointer that can be returned if the allocation fails. We need to fix that.

However, the good news is that we don't need to allocate memory at all. We only need to look at each character at a time, so we can iterate over it using getc(), without needing to store it after that.

As we're considering the input to be independently distributed (i.e. P(xₙ) independent of preceding values), then what we're creating is a histogram of the input characters. We can do that with a fixed-size array of UINT_MAX + 1 counts (I'd probably use size_t for the counts, although it's possible for a file to exceed the range of size_t, so might need to consider uintmax_t).

---

A few minor points:

• calloc() and similar functions return void* which can be assigned to a variable of any object-pointer type, so no need for those casts.
• sizeof (char) is always 1, by definition.
• Prefer p = malloc(sizeof *p) so readers don't have to match up the type of *p and there's less to edit if you change your mind about its type.
• Good use of stderr and EXIT_FAILURE in the error reporting.
• Consider using stdin as default if no filename is provided.
• We should be opening the file in binary mode ("rb").
• We can give the user more information about fopen() failure, by using perror().
• fread() can return less than you asked for - you need a loop to read a whole file (or look into memory-mapping).
• In general, a file can contain null characters, so treating its contents as a C string can cause us to consider a much shorter stream than we should.

---

Modified code

This looks very different, having changed from linear lookup to the histogram with direct access. I haven't verified it gives consistent results, so it may have bugs!

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>

static void fill_histogram(size_t histogram[], FILE *file)
{
    int c;
    while ((c = getc(file)) != EOF) {
        /* c must be positive and in range */
        ++histogram[c];
    }
}

/* Histogram array length must be UCHAR_MAX+1 */
static size_t total(const size_t histogram[])
{
    size_t sum = 0;
    for (size_t i = 0;  i <= UCHAR_MAX;  ++i) {
        sum += histogram[i];
    }
    return sum;
}

/* Histogram array length must be UCHAR_MAX+1 */
static double entropy(const size_t histogram[])
{
    size_t len = total(histogram);

    double result = 0.0;
    for (size_t i = 0;  i <= UCHAR_MAX;  ++i) {
        if (!histogram[i]) {
            continue;
        }
        double freq = (double)histogram[i] / (double)len;
        result -= freq * log10(freq) / log10(2.0);
    }

    return result;
}


int main(int argc, char const **argv)
{
    FILE *f = stdin;
    if (argc > 2) {
        fprintf(stderr, "too many arguments\n");
        return EXIT_FAILURE;
    } else if (argc == 1) {
        f = fopen(argv[1], "rb");
        if (!f) {
            perror(argv[1]);
            return EXIT_FAILURE;
        }
    }

    size_t histogram[UCHAR_MAX+1] = { 0 };
    fill_histogram(histogram, f);

    if (f != stdin) {
        if (fclose(f)) {
            perror("close");
            return EXIT_FAILURE;
        }
    }

    printf("Length of file: %zu\n", total(histogram));
    printf("Entropy of file: %f\n", entropy(histogram));
    return EXIT_SUCCESS;
}