6
\$\begingroup\$

I have written a prefix-free compressor that assigns the shortest bit-strings to the most common characters. It works very well for natural language as some characters (SPACE, "a", "e" ...) are much more common than others ("y", "z" ...)

This method of compression does not work on random text where each letter is equally likely as all characters would get a same length bit-string with no compression at all.

The compression factor \$0.5791185\$ is impressive given how simple this code is (the compressed text + the dictionary necessary for decompression is 0.579... times as long as the original message).

The file "commedia.txt" is just the integral text of the Commedia of Dante Alighieri taken from here. This file should be in the same directory as the script.

Each function has documentation and at least one doctest to ease your reading and reviewing.

"""
Implementation of prefix-free compression and decompression.
"""
import doctest
from itertools import islice
from collections import Counter
import random
import json

INPUT_FILE = "commedia.txt"
COMPRESSED_OUTPUT_FILE = "commedia.pfc"
DICTIONARY_OUTPUT_FILE = "commedia.pfcd"

def binary_strings(s):
    """
    Given an initial list of binary strings `s`,
    yield all binary strings ending in one of `s` strings.

    >>> take(9, binary_strings(["010", "111"]))
    ['010', '111', '0010', '1010', '0111', '1111', '00010', '10010', '01010']
    """
    yield from s
    while True:
        s = [b + x for x in s for b in "01"]
        yield from s


def take(n, iterable):
    """
    Return first n items of the iterable as a list.

    >>> take(5, range(10))
    [0, 1, 2, 3, 4]
    """
    return list(islice(iterable, n))


def chunks(xs, n, pad='0'):
    """
    Yield successive n-sized chunks from xs.

    >>> list(chunks([1, 2, 3, 4, 5, 6], 2))
    [[1, 2], [3, 4], [5, 6]]
    """
    for i in range(0, len(xs), n):
        yield xs[i:i + n]


def reverse_dict(dictionary):
    """
    >>> sorted(reverse_dict({1 : "a", 2 : "b"}).items())
    [('a', 1), ('b', 2)]
    """
    return {value: key for key, value in dictionary.items()}


def prefix_free(generator):
    """
    Given a `generator`, yield all the items from it
    that do not start with any preceding element.

    >>> take(6, prefix_free(binary_strings(["00", "01"])))
    ['00', '01', '100', '101', '1100', '1101']
    """
    seen = []
    for x in generator:
        if not any(x.startswith(i) for i in seen):
            yield x
            seen.append(x)


def build_translation_dict(text, starting_binary_codes=["000", "100", "111"]):
    """
    Builds a dict for `prefix_free_compression` where
       More common char -> More short binary strings
    This is compression as the shorter binary strings will be seen more times than
    the long ones.

    Univocity in decoding is given by the binary_strings being prefix free.

    >>> sorted(build_translation_dict("aaaaa bbbb ccc dd e", ["01", "11"]).items())
    [(' ', '001'), ('a', '01'), ('b', '11'), ('c', '101'), ('d', '0001'), ('e', '1001')]
    """
    binaries = sorted(list(take(
        len(set(text)), prefix_free(binary_strings(starting_binary_codes)))), key=len)
    frequencies = Counter(text)
    # char value tiebreaker to avoid non-determinism                     v
    alphabet = sorted(
        list(set(text)), key=(lambda ch: (frequencies[ch], ch)), reverse=True)
    return dict(zip(alphabet, binaries))


def prefix_free_compression(text, starting_binary_codes=["000", "100", "111"]):
    """
    Implements `prefix_free_compression`, simply uses the dict
    made with `build_translation_dict`.

    Returns a tuple (compressed_message, tranlation_dict) as the dict is needed
    for decompression.

    >>> prefix_free_compression("aaaaa bbbb ccc dd e", ["01", "11"])[0]
    '010101010100111111111001101101101001000100010011001'
    """
    translate = build_translation_dict(text, starting_binary_codes)
    return ''.join(translate[i] for i in text), translate


def prefix_free_decompression(compressed, translation_dict):
    """
    Decompresses a prefix free `compressed` message in the form of a string
    composed only of '0' and '1'.

    Being the binary codes prefix free,
    the decompression is allowed to take the earliest match it finds.

    >>> message, d = prefix_free_compression("aaaaa bbbb ccc dd e", ["01", "11"])
    >>> message
    '010101010100111111111001101101101001000100010011001'
    >>> sorted(d.items())
    [(' ', '001'), ('a', '01'), ('b', '11'), ('c', '101'), ('d', '0001'), ('e', '1001')]
    >>> ''.join(prefix_free_decompression(message, d))
    'aaaaa bbbb ccc dd e'
    """
    decoding_translate = reverse_dict(translation_dict)
    word = ''
    for bit in compressed:
        if word in decoding_translate:
            yield decoding_translate[word]
            word = ''
        word += bit
    yield decoding_translate[word]


if __name__ == "__main__":
    doctest.testmod()
    with open(INPUT_FILE) as f:
        text = f.read()
    compressed, d = prefix_free_compression(text)
    with open(COMPRESSED_OUTPUT_FILE, "wb") as f:
        t = bytes((int(b, base=2) for b in chunks(compressed, 8)))
        print(len(t))
        f.write(t)
    with open(DICTIONARY_OUTPUT_FILE, "w") as f:
        f.write(json.dumps(d))
    # dividing by 8 goes from bit length to byte length
    print("Compressed / uncompressed ratio is {}".format(
        (len(json.dumps(d)) + len(compressed) // 8) / len(text)))
    original = ''.join(prefix_free_decompression(compressed, d))
    assert original == text
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Great job, this code does a lot of things in few lines, is easy to read, and the results are quite impressive. But who's going to upvote me if only say this?

One general comment: this is not Python, but Haskell. :) Unfortunately Python really does not want us to write functional code (two examples: no tail call optimizations, Python 3 hiding reduce() in functools). This is reflected in the culture and the community as well: nobody writes such code and you can't expect it to be liked by other Python programmers. But it's okay if you're writing for yourself!

Another comment: Thank you for the docstrings, they're really useful. 👍

"""
Implementation of prefix-free compression and decompression.
"""

Use a one-liner docstring or expand the docstring (see PEP 257).

import doctest
from itertools import islice
from collections import Counter
import random
import json

INPUT_FILE = "commedia.txt"
COMPRESSED_OUTPUT_FILE = "commedia.pfc"
DICTIONARY_OUTPUT_FILE = "commedia.pfcd"

PEP 8: You need two spaces between those constants and the function below. Also, you don't use random. Consider using flake8 and yapf by integrating them into your text editor.

def binary_strings(s):
    """
    Given an initial list of binary strings `s`,
    yield all binary strings ending in one of `s` strings.

    >>> take(9, binary_strings(["010", "111"]))
    ['010', '111', '0010', '1010', '0111', '1111', '00010', '10010', '01010']
    """
    yield from s
    while True:
        s = [b + x for x in s for b in "01"]
        yield from s

Even though take is obvious for functional programmers, you should define it before binary_strings.

def take(n, iterable):
    """
    Return first n items of the iterable as a list.

    >>> take(5, range(10))
    [0, 1, 2, 3, 4]
    """
    return list(islice(iterable, n))

You're reversing the order of arguments of islice() for no real reason.

def prefix_free(generator):
    """
    Given a `generator`, yield all the items from it
    that do not start with any preceding element.

    >>> take(6, prefix_free(binary_strings(["00", "01"])))
    ['00', '01', '100', '101', '1100', '1101']
    """
    seen = []
    for x in generator:
        if not any(x.startswith(i) for i in seen):
            yield x
            seen.append(x)

This is elegant but inefficient: O(n^2) when you could probably do this in O(n). See Prime sieve in Haskell for a similar issue where the elegant code is slow.

Also, this algorithm cannot beat Huffman coding because the structure of the tree does not depend on the actual frequency of letters. However, on natural language it will probably be close to Huffman codes because of the Zipf law.

def build_translation_dict(text, starting_binary_codes=["000", "100", "111"]):
    """
    Builds a dict for `prefix_free_compression` where
       More common char -> More short binary strings
    This is compression as the shorter binary strings will be seen more times than
    the long ones.

    Univocity in decoding is given by the binary_strings being prefix free.

    >>> sorted(build_translation_dict("aaaaa bbbb ccc dd e", ["01", "11"]).items())
    [(' ', '001'), ('a', '01'), ('b', '11'), ('c', '101'), ('d', '0001'), ('e', '1001')]
    """
    binaries = sorted(list(take(
        len(set(text)), prefix_free(binary_strings(starting_binary_codes)))), key=len)
    frequencies = Counter(text)
    # char value tiebreaker to avoid non-determinism                     v
    alphabet = sorted(
        list(set(text)), key=(lambda ch: (frequencies[ch], ch)), reverse=True)
    return dict(zip(alphabet, binaries))

This is where we really miss Haskell. And I'm glad that I don't have to debug this. :)

Nothing to say about the functions that follow: they make sense and are very easy to read.

    with open(DICTIONARY_OUTPUT_FILE, "w") as f:
        f.write(json.dumps(d))

pickle is probably going to be more space efficient than JSON.

Now, for your next challenge, try to build an efficient language model with low perplexity on your input file. :)

\$\endgroup\$
1
  • \$\begingroup\$ Your first two links redirect to the same post \$\endgroup\$ Aug 31, 2016 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.