Simple string compression in Python

Question

This is my solution to exercise 1.6 in Cracking the Coding Interview. I am interested in receiving feedback on the coding style and time/space complexity.

The exercise statement is:

Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the compressed string would not become smaller than the original string your method should return the original string. You can assume the string has only uppercase and lowercase letters (a-z).

import unittest
from collections import defaultdict
from math import log10, floor 


def compress_string(data: str) -> str:
    """A function to perform basic string compression using the counts of repeated characters
     If the compressed string is not smaller than the original string the function returns
     the original string.  The assumption is that the string has only uppercase and lowercase letters (a-z)."""
     curr_char_pos = 0
     frequencies = defaultdict(int)
     compressed_string = []
     compressed_string_size = 0

     for idx in range(len(data)):
        if compressed_string_size >= len(data):
            break
        if data[idx] == data[curr_char_pos]:
            frequencies[curr_char_pos] += 1
        else:
            compressed_string.append(data[curr_char_pos])
            compressed_string.append(frequencies[curr_char_pos])
            compressed_string_size += floor(log10(frequencies[curr_char_pos])) + 2
            curr_char_pos = idx
            frequencies[curr_char_pos] = 1

        compressed_string.append(data[curr_char_pos])
        compressed_string.append(frequencies[curr_char_pos])
        compressed_string_size += floor(log10(frequencies[curr_char_pos])) + 2

        if compressed_string_size < len(data):
            compressed_data = ''.join(str(char) for char in compressed_string)
            return compressed_data
       else:
            return data


class MyTest(unittest.TestCase):
    def test_compress_string(self):
        self.assertEqual(compress_string('aabcccccaaa'), 'a2b1c5a3')
        self.assertEqual(compress_string('abcd'), 'abcd')
        self.assertEqual(compress_string('tTTttaAbBBBccDd'), 'tTTttaAbBBBccDd')

Answer 1

This is called Run-length-encoding and there are many implementations of this on the Internet, for example: http://rosettacode.org/wiki/Run-length_encoding#Python

I have written a solution myself just now but posting it would not really help (it would be like adding another drop in the ocean) so I will comment your code thoroughly instead:

optimization?

This was probably added as an optimization:

    if compressed_string_size >= len(data):
        break

But except for inputs with no consecutive runs whatsoever, the compressed size will exceed the real size only near the end of the compression. Does the overhead of the additional conditional check each loop iteration take less time than the iterations saved? If it does, does it save enough time to justify adding complexity? I suggest you first worry about writing a working program and then apply optimizations with profiling (execution timing).

Additional variable not needed

compressed_string_size = 0

This was probably added as an optimization too, but is it worth it? No, because len runs in O(1) time complexity that is, len does not need to scan the whole list, because lists remember their length, so calling len is almost instantaneous, in fact using that variable is likely a pessimization as log is a very expensive mathematical operation.

Answer 2

Your problem could be solved with something like this:

import unittest
from itertools import groupby


def compress_string(data):
    compressed = "".join(["{0}{1}".format(k, sum(1 for i in g))
                          for k, g in groupby(data)])

    if len(compressed) > len(data):
        return data
    else:
        return compressed


class MyTest(unittest.TestCase):

    def test_compress_string(self):
        self.assertEqual(compress_string('aabcccccaaa'), 'a2b1c5a3')
        self.assertEqual(compress_string('abcd'), 'abcd')
        self.assertEqual(compress_string('tTTttaAbBBBccDd'), 'tTTttaAbBBBccDd')

if __name__ == '__main__':
    unittest.main()

Some hints about your code:

• I'd recommend you stick to PEP8
• Use flake.
• Try to reduce the size of your code and don't use unnecesary variables.
• Consider proper iteration of lists (normal iteration, enumeration) instead using that for index in len(range(whatever_list))
• Before coding your own thing, examine whether the standard library is already implementing that somewhere