# -*- coding: utf-8 -*-
"""Encode and decode a representation using a reduced-charset version of ASCII.

My theory is that you can make text more compressible by encoding it
in a modeful way, like the old Baudot codes.  I’m appropriating four
ASCII codes for the role of the old FIGS:

- DC1 \x11 ^Q: change state to lowercase letters (the initial state)
- DC2 \x12 ^R: change state to uppercase letters
- DC3 \x13 ^S: change state to numbers
- DC4 \x14 ^T: treat the next character only as an uppercase letter

I know SI and SO would be more appropriate here, but I need three
states, not two.

ESC followed by any of the above four, or itself, simply passes that
character through to the output.

All three of uppercase, letters, and numbers are encoded as lowercase
letters.  Effectively, this reduces the 128-character ASCII character
set by 36 to 92 characters.

The algorithm for using DC4 (capitalize next letter) is potentially
problematic, in that it may use a lot of buffer space.

This approach *does* make my test file (Project Gutenberg’s King James
Bible, minus CR characters but retaining LFs) more compressible: it
compresses to 1369889 bytes instead of 1371072 bytes with this
preprocessing applied --- indicating that the preprocessing picked up
some structure gzip wasn’t able to find itself! But this is a very
small difference, like 0.08%.  The encoding bloated the original file
from 4351847 bytes to 4515061 bytes, a 3.8% increase.  A random
translation from a 128-character charset to a 92-character charset
would be expected to increase the file size by 7.3%, not 3.8%.

Doing a simple huffman compression on the same file produced 19939830
bits on the raw file and 20094861 bits on the encoded file, both
exclusive of the huffman table itself, an 0.8% increase in the size of
the file, rather than gzip’s 0.08% improvement.  This was a little

However, it achieved its purpose of formulating a practical huffman
code for manual encoding of English text with spacing, punctuation,
and formatting, with only 38 code points and reasonable efficiency of
about 4.6 bits per character. (Details in a later post.)


lowercase = 'abcdefghijklmnopqrstuvwxyz'
numbers = '0123456789'
(DC1, DC2, DC3, DC4, ESC) = ('\x11', '\x12', '\x13', '\x14', '\x1b')

def chars(infile):
    for line in infile:
        for char in line:
            yield char

def decode(infile):
    current_state = lowercase
    capitalize_next_char = False
    passthrough_next_char = False

    for char in chars(infile):
        if passthrough_next_char:
            yield char
            passthrough_next_char = False
        elif char in lowercase:
            if capitalize_next_char:
                yield uppercase[lowercase.index(char)]
                capitalize_next_char = False
                yield current_state[lowercase.index(char)]
        elif char == DC1:
            current_state = lowercase
        elif char == DC2:
            current_state = uppercase
        elif char == DC3:
            current_state = numbers
        elif char == DC4:
            capitalize_next_char = True
        elif char == ESC:
            passthrough_next_char = True
            yield char

def ok(a, b): assert a == b, (a, b)

ok(''.join(decode('this \x12is \x11a \x14test \x13bcd! \x1b\x12')),
   'this IS a Test 123! \x12')

def chunks(infile):
    "Break an infile into chunks such that any capital starts a new chunk."
    buffer = []
    for char in chars(infile):
        if char in uppercase:
            yield buffer
            buffer = [char]
    yield buffer

def encode(infile):
    current_state = lowercase
    for chunk in chunks(infile):
        if (current_state is not uppercase and
                chunk and
                chunk[0] in uppercase
                and any(letter in lowercase for letter in chunk)):
            yield DC4
            chunk[0] = chunk[0].lower()

        for char in chunk:
            if char in (DC1, DC2, DC3, DC4, ESC):
                yield ESC
            elif char in current_state:
            elif char in lowercase:
                yield DC1
                current_state = lowercase
            elif char in uppercase:
                yield DC2
                current_state = uppercase
            elif char in numbers:
                yield DC3
                current_state = numbers

            if char in current_state:
                yield lowercase[current_state.index(char)]
                yield char

ok(''.join(encode('this IS a Test 123! \x12')),
   'this \x12is \x11a \x14test \x13bcd! \x1b\x12')
_me = file(__file__).read()
ok(''.join(decode(encode(_me))), _me)

if __name__ == '__main__':
    import sys
    decoding = (len(sys.argv) > 1 and sys.argv[1] == '-d')
    if decoding: sys.argv.pop(1)
    function = decode if decoding else encode
    infile = file(sys.argv[1]) if len(sys.argv) > 1 else sys.stdin
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-hacks

Reply via email to