By CodeCrack


2016-01-08 04:40:01 8 Comments

I implemented basic string compression algorithm that uses the counts of repeated characters. For example: the string aabcccccaaa would become a2b1c5a3. What do you think about this, is there a better way to do this?

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

char* compressString(char* arr, int size);

int main() {

  char arr[] = "aabcccccaa";
  char *str;
  printf("Before compression: %s\n", arr);
  str = compressString(arr, strlen(arr));
  printf("After compression: %s\n", str);
  // free allocated memory
  free(str);
  return 0;
}

char* compressString(char* str, int len) {
  char last = str[0];
  char *buf = (char *)malloc(len * sizeof(char));
  int count = 1;
  int j = 0;

  for (int i = 1; i < len; i++) {
    if (last == str[i]) {
      count++;
    } else {
      buf[j++] = last;
      buf[j++] += count + '0';
      last = str[i];
      count = 1;
    }
  }
  buf[j++] = last;
  buf[j] += count + '0';
  buf[j] = '\0';
  return buf;
}

1 comments

@JS1 2016-01-08 05:50:22

A couple problems

  • You don't allocate enough space for the return buffer. You need to allocate 2*len + 1 bytes to handle the worst cast scenario. The +1 is for the null terminating byte.

  • If the count goes above 9, you will output a non-digit character instead of a digit. If the count goes above 256, the digit will wrap around back to '1' and your compression will have failed to encode the original string.

@DarthGizka 2016-01-08 07:01:47

@CodeCrack: perhaps you should get a rough overview of existing compression algorithms before reinventing the wheel in a particularly non-circular shape. For one thing this would show you all the ways that have been invented for storing counts efficiently (variable-length encodings based on bytes, nibbles or bits, Huffman-encoding of counts, arithmetic coding of counts, and so on). Run-length encodings like yours are often found in bitmaps (unsurprisingly called RLE bitmaps); looking at those might give you interesting ideas. Most of your questions have already been answered ages ago...

Related Questions

Sponsored Content

2 Answered Questions

[SOLVED] String Compression

4 Answered Questions

[SOLVED] Algorithm for Run Length Encoding - String Compression

2 Answered Questions

[SOLVED] Simple string compression in Python

2 Answered Questions

[SOLVED] Naive string compression

2 Answered Questions

[SOLVED] Basic string compression implementation in C

  • 2017-11-12 17:39:34
  • Emre Can Kucukoglu
  • 1149 View
  • -1 Score
  • 2 Answer
  • Tags:   c strings compression

2 Answered Questions

[SOLVED] Simple string compression reloaded

  • 2016-01-03 00:04:46
  • ChrisWue
  • 149 View
  • 4 Score
  • 2 Answer
  • Tags:   c compression

3 Answered Questions

[SOLVED] String compression by using repeated characters count

2 Answered Questions

[SOLVED] String compression using repeated character counts

3 Answered Questions

[SOLVED] String compression implementation in C#

Sponsored Content