LZW compression for twittering knitters

[kassia]

Consider a two-color knitting pattern, all knit stitches, and define an nxm block, repeating after m stitches each row, and repeating the block every n rows. Let 'd' represent the foreground color and 'c' represent the background color, and 'a' the "end of row" (or "repeat to end of round and then next row" or "control-return,line-feed") and 'b' the "end of block" (or "repeat all rows to end of length" or "end-of-file") and consider the famous "Kurdish Kilim" pattern recorded by Zilboorg (8x8):
ooxooxxx
ooxxoxxo
xooxxxoo
xxoxxooo
oxxxooxo
oxxoooxx
xxooxoox
xoooxxox
,
which we represent as the following string: ccdccdddaccddcddcadccdddccaddcddcccacdddccdcacddcccddaddccdccdadcccddcdb
.

Now, this is a pretty simple pattern, needing 71 characters total, which is within twitter's 140-character limit. Can we use compression to make it shorter, and thereby be able to twitter more complicated patterns? We'd want the compression to be lossless, otherwise the pattern won't work. LZW to the rescue! Essentially, it compresses by sending codes that mean "that thing you did there before, do it again", which means the encoder and decoder don't have to agree on the complete dictionary in advance - the encoder creates it as it goes, and so does the decoder, remembering what sequences they have already seen.
Let's use the alphabet of lower case letters, in order.

Our dictionary for this example ends up having 35 entries:

'a' 'b' 'c' 'd' 'cc' 'cd' 'dc' 'ccd' 'dd' 'dda' 'ac' 'ccdd' 'dcd' 'ddc' 'ca' 'ad' 'dcc' 'cdd' 'ddcc' 'cad' 'ddcd' 'ddccc' 'cac' 'cddd' 'dccd' 'dca' 'acd' 'ddcccd' 'ddad' 'ddccd' 'dccda' 'adc' 'ccc' 'cddc' 'cdb'

but we only use 19 of them, for an output string of

ccdediahgicagfnonsorqgkvjsyperfb

only 32 characters long! Very helpful for almost any repetitive pattern, that is, for any pattern that's comfortable and easy to knit!
(It's interesting to note that the essential 8-element pattern kernel 'ccdccddd' and its inverse and their rotations don't appear as dictionary words; they would if we were defining in advance an optimal compression for this particular pattern.)

I'm sure most twitter interface software will incorporate this very soon. In the meantime, use python.

I'll keep thinking about whether there's a more twitter-appropriate compression for this application that would also be more trivially encoded and decoded visually, so that the sending knitter could type it up (and the receiving knitter could knit from the code directly) without needing a computer. [maybe they're twittering from their phones {and they haven't picked up LZWcftk from the App Store yet}]

#LZWcftk

Comments

[alethia-juturna.livejournal.com]

That is really cool.. ;-)