Algorithm for Run Length Encoding - String Compression

Question

I attempted a problem from the Cracking the Coding Interview book. The following input: aabcccaaa should give the following output: a2b1c3a3. Any advice is much appreciated!

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

char* compress(char*);

int main(int argc, char** argv)
{   
    if(argc==2)
    {
        printf("The compression of %s is %s \n", argv[1],
            compress(argv[1]));
    }
    else
        printf("Not correct number of inputs.");
}

char* compress(char* str)
{
    const size_t len = strlen(str);
    char result[len];

    //initialized to 0, so length check can be done later
    memset(result, 0, len); 

    int counter;
    int j = 0;

    if(str==NULL || len == 0)
        return 0; 

    result[0] = str[0];
    for(size_t i = 0; i < len; i++)
    {   
        counter = 1;//reset counter

        //to make sure no array out of bounds exception occurs
        if(result[j+1]==0)
            result[++j] = counter + '0';
        else
            return str;

        while(str[i] == str[i+1])
        {
            //to store number in char array, add the asci value 
            // of 0.
            result[j] = (++counter + '0'); 
            i++;
        }
        if(result[j+1]==0)
            result[++j] = str[i+1];
        else 
            return str;
    }

    result[++j] = '0';

    //to avoid "function returns address of local variable" error
    //to also avoid altering original argument
    char* str1 = (char*)malloc(sizeof(result));
    strcpy(str1, result);
    return str1;
}

Answer 1

• You can eliminate that function prototype by defining main() last, but it's up to you.

• It's more common to first check the command line usage and then exit with a non-zero value if it's invalid. You should also print all errors to stderr, not stdout (the latter is always used with printf()).

  if (argc != 2)
  {
      fprintf(stderr, "Not correct number of inputs.");
      return -1;
  }
  

• You can probably check str right at the start, especially with the len assignment. If there is an error, then it may be clearer to return NULL instead of 0. At least that's what many library functions return specifically.

• The while loop can instead be a for loop:

  for (; str[i] == str[i+1]; i++)
  {
      //to store number in char array, add the asci value 
      // of 0.
      result[j] = (++counter + '0');
  }
  

• The NULL character for result is wrong; it should be '\0'.

• There's actually no need to cast the return type of malloc() in C. Although malloc() does return a void*, it's not required because any pointer type can be assigned to a void* and is done "automatically" here.

  Moreover, you can avoid that aforementioned error by allocating result after making sure that the original string is valid. This will also avoid the need to call strcpy() at the end and risk other bugs. Since result will not be local this way, you can return it from the function without losing the data.

  char* compress(char* str)
  {
      // check to make sure str is valid...
  
      // assuming len is also valid
      char* result = malloc(len);
  
      // OR, use calloc() instead to get the memory zeroed
      //   thus no need for memset() or anything else
      char* result = calloc(len, sizeof(char));
  
      // probably also good to check for sufficient memory
      // if insufficient, print error and abort
      if (!result)
      {
          perror("malloc"); // or "calloc"
          abort();
      }
  
      // do the compression...
  
      // return it right away; no need to copy anything
      return result;
  }
  

• You never call free() on str1, so this function leaks memory. You would have to do this in main() with the returned string, and it may be necessary to assign compress() to a const char* to display before freeing afterward. This also means that compress() should return a const char*, not a char*, preventing it from being modified further.

  It may work to have something like this in main():

  int main(int argc, char** argv)
  {
      if (argc != 2)
      {
          // let the user know of the correct input
          fprintf(stderr, "usage: %s string\n", argv[0]);
          return -1;
      }
  
      const char* original = argv[1];
      const char* compressed = compress(original);
  
      printf("The compression of %s is %s \n", original, compressed);
  
      free(compressed);
  }
  

Answer 2

1. Bug: you assume that the result will never be longer than the original string while in fact it could be twice as long. For example abcd would yield a1b1c1d1.

2. Instead of using memset to initialize result you can also initialize it to 0 like this:

   char result[len] = { 0 };
   

3. You don't have to assign the counter on every iteration to the result. Simply increment the counter while the letter doesn't change and then add the count afterwards.

4. Another bug: the way you convert the counter into a string will stop working for any number larger than 9. You want sprintf.

5. Also strlen returns the length of the string excluding the terminating NULL character so your result is short by 1 in any case.

6. Given the fairly severe bugs you really ought to test your code better.

Answer 3

Don't speak of one

I know it is against what the problem expects, but an improvement in your compression algorithm would be to not print any number if there is only one occurrence of the letter.

This way, it would impossible to encounter that first bug mentioned in ChrisWue's answer. And, in files that don't have that many consecutive letters, they will have less added bytes from the compression.

However, as noted in two comments, if the digits are numbers, you can run into some issues. However, after reading the next section, you can see that, if you have consecutive numbers, they will be ASCII numbers, where the values accompanying the characters will not be ASCII.

---

ASCII numbers

This is also against the challenge output.

Most compression services don't leave an intentionally readable output file in the end. In that case, there is not much need to have the numbers accompanying the letters be ASCII. That way, when it comes to large repetitions of characters (at least > 10), you will not be spending an extra byte or two.

Now, you may think: if the number got high enough, it might interfere with the file content. That is true; but your code will do this now too. However, when decompressing, it can be kept in mind that the compression will result in two byte pairs: one byte for the character, one byte the character occurrences.

---

UTF

Right now, your compression algorithm won't do so well when it comes to UTF files. Since some UTF characters actually exceed 1 byte, this algorithm would probably end up not compressing anything at all.

Now, this may be out of the scope of your problem, but it would be a nice addition. If you look at the UTF-8 wiki page, you can see that it is somewhat possible to detect if a character is UTF, judging by the binary digits at the beginning of the digit.

This, of course, would raise complications as UTF-8 characters are variable length and you would have to determine the length in bytes of the character by the first binary digits.

To ease things up, you could have the user specify whether or not the file is UTF encoded (or, you might be able to find out by reading the file).

---

Misc

• Always use braces.

Answer 4

Bug. What happens if your input contains more than nine consecutive instances of the same character? What if it contains a lot more than nine? You don't do any bounds checking before assigning ++counter + '0' into a char variable and then printf-ing it back in main.