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
