Algorithm to transform a string according to occurrence count of each character

Question

I have this algorithm that counts the frequency of character occurrence in a string, and outputs a new string based on that.

For example,

input = 'aabbcccaaa'
output = 'a5b2c2'

Here is my implementation in python

def compression(string):
    string = string.lower()
    freq_count = {}

    for index, char in enumerate(string):
        if char not in freq_count:
            freq_count[char] = 1
        else:
            freq_count[char] += 1

    return_string = ''
    for key in freq_count:
        return_string += key + str(freq_count[key])
    print(return_string)

    return return_string

compression('aabccccaaa')

My question is, am I making this algorithm less efficient by using dict to memoize values.

Also, I know that creating a new string takes up memory allocation, so is there a way to improve on that?

Answer 1

def compression(string):

Naming can be hard, but it is important to get right. If I were to call compression('abcd'), I would expect the result length to be at-most the length of the input string. "compression" doesn't really describe what is happening within the function. So what exactly is your function doing? From your description:

I have this algorithm that counts the frequency of character occurrence in a string, and outputs a new string based on that.

A lot of nice verbs in that description you can use for a function name (serialize_frequencies?).

---

string = string.lower()

Does case-sensitivity have anything to do with your stated goals of calculating and serializing the frequency of characters? It depends on the context in which this function is used. Case-sensitivity isn't always required. If you really want to provide a mechanism for case-insensitive frequency generation, consider a toggle parameter or another function that transforms the input then calls this function.

serialize_frequencies(string, case_insensitive = False):
    if case_insensitive:
        string = string.lower()

---

    freq_count = {}

    for index, char in enumerate(string):
        if char not in freq_count:
            freq_count[char] = 1
        else:
            freq_count[char] += 1

A function that performs a single operation is simpler to understand, test, and reuse. Don't be afraid to break functions up into suitable logical parts and parameterize.

enumerate is a nice utility when you need to iterate through a sequence but also want to know the index. Since you don't need the index, you can just iterate through the string itself.

    for char in string:
        if char not in freq_count:
            freq_count[char] = 1
        else:
            freq_count[char] += 1

With that said, Python's collections includes a dictionary sub-class to count frequencies (Counter).

    freq_count = Counter(string)

---

    return_string = ''
    for key in freq_count:
        return_string += key + str(freq_count[key])

If you want to iterate a dictionary by its key-value pair, Python's built-in dictionary includes the method items().

    return_string = ''
    for key, value in freq_count.items():
        return_string += key + str(value)

You can write the loop that appends each pair using the string method join.

    return_string = ''.join(k+str(v) for k,v in freq_count.items())

---

    print(return_string)

Debugging artifact?

---

My question is, am I making this algorithm less efficient by using dict to memoize values.

No. But as 200_success has noted, calling compression('abcd') might result in 'a1b1c1d1' or 'c1d1b1a1' depending on the implementation. Ordering for the built-in dictionary is arbitrary and could change between implementations, versions, or possibly application executions. If ordering matters, then you should use a sorted container (OrderedDict, SortedDict) or manually sort the resulting dictionary before serializing.