foreign
[Music]
good afternoon so here this afternoon we
have Paul Weber and he's here to talk to
us about improving old compression
algorithms
Paul started writing code for a zx80 on
the typewriter and things improved a bit
since then they currently work for Red
Hat trying to automate so that other
people don't have to today Paul will
discuss this Research into improving the
lcw algorithm to get a demonstration on
encoding and decoding and compare his
compression ratios to other more modern
compression methods please welcome Paul
[Applause]
thank you very much and greetings from
nunawal country where I come from in
Canberra
so compression algorithms has been
something I've been really interested in
for a long time so I'm going to give you
a bit of a history of compression uh
some of the theory behind it some of the
algorithm work that I've been doing and
sort of look into the future so I want
to take you back to 1977. who wasn't
alive in
1977. okay there's a few so so I'm going
to have to recap some stuff
um
some some bad things happened uh some
good things happened uh the first hints
of an Internet
started appearing something particularly
important for a lot of people here that
were alive during this time was these
three computers appeared on the scene
the pet the Apple II and the TRS-80 and
those along with a number of other
personal computers really took Computing
from stuff that you did maybe at your
parents work or in a library into the
home that you could play with yourself
the other important thing that is for my
talk uh in that happened in 1977 was
that these two gentlemen Abraham Lincoln
on the left left who's sadly passed away
so this talk is kind of dedicated to him
and Jacob ziv on the right uh introduced
a compression algorithm called lz77
um strange title but there you go
um the way this works is that we look at
the output we're either outputting sort
of literal data or we have a way of
saying there's a repeat that's in the
output stream that is already in the
output and so we refer back to this we
have this sort of Tuple in the original
paper a bit the distance back to the
last match the length of that match and
then the next character that we're going
to Output
if we have no match then we just output
zeros and we output characters one at a
time until we've got enough to actually
form a match so this basically looks
back into a sliding window over the past
output to look for matches that the
encoder can efficiently uh
is transmit and the decoder then knows
to find in that window
like it's impossible to understate the
importance of this algorithm these are
the tools just some of them that have
been influenced by lz77 not just the
tools but the algorithms as well as ltma
obviously is one of them but there are
decompressors for different
architectures there's so when your
memory is very constrained there are
there are algorithms that are optimized
particularly for decompression speed
it it they have just been huge so
uh we're going to move along on to
another uh the next year 1978
um
a bunch of bad things happened a bunch
of good things happened
um
and these two gentlemen not satisfied
with releasing one algorithm released a
second called lz78
now this I know once you're on a theme
stick to it right
um so uh this works slightly differently
what it does is it learns sequences of
adjacent characters or symbols in the
input and put them into a dictionary and
then
the output is the longest dictionary
entry that matches that's in the
dictionary at the time
I have to take you slightly further
forward to give you a good example of
this I'm going I need to go forward to
1984
we were at war with East Asia again
there was a lot of sex crime I was 13 at
the moment so I didn't have any of that
but
um
Terry Welch who I don't have a photo of
uh released an improvement to lz78 and
it's commonly called lzw
the way this works which is conceptually
a lot easier than lz78 is that we start
with a symbol table that contains the
first the basically all variations of an
8-bit byte
uh there's also a flush table symbol and
there's a stop input symbol
um
and we basically add input
um
to sort of our buffer until that buffer
no longer is matches an entry in the
symbol table
at that point we know we've got a new
symbol
so we add the last symbol that matched
we remember the next character and we
start looking again
so I'm going to give you an example
of how this works we're going to be
encoding this admittedly very
repetitious string but it's good for my
purposes here and I'm going to ask you
to bear with me for one bit because I'm
not going to write out all 256 symbol
entries here I just want you to imagine
them I'm just going to number the
symbols that we've got here at the
moment we say we start with those the
four characters that appear in this
string as the first four entries in our
symbol table
so we read the first B we're looking
ahead to a there's no ba in the symbol
table so we add that and then we write
the symbol B
uh we'd go we've got the a we're looking
ahead to n there's no a n symbol uh we
add that and we write the a you can see
how we're building up this symbol table
here so we add n a that's good
and now we have our first match a n is
already in the symbol table so we can
look ahead to a there's no a and a
symbol but now we're outputting
essentially a two character symbol
versus just a one character symbol
there's no we're looking ahead through
the space so there's no a space symbol
so we add that there's no space b symbol
so we add that but now obviously we're
going to start to get these larger
symbols building up out of
symbols that we've added to the symbol
Table after we started compressing we've
got an N A here and that produces the
Nan because we're looking at forward to
the Outlook ahead is to the N symbol but
then we can write n a again and we know
that the
we're looking forward to in a space the
decompressor here basically starts with
the B symbol and it it knows that it's
going to write a b something symbol into
the table at some point when it gets the
a symbol it knows that the a there was
the first character of that symbol that
it needed to write and so the
decompressor and the compressor can work
in lockstep building up this same symbol
table so that's the shared knowledge and
we start getting
encoding that final banana
um
we and we're outputting symbols that are
now three characters in length
so and we finally basically finish up
our input and I've just said okay
there's no more work to be done
so how does that compare with our
original data
well we started with
four six byte words and three spaces so
we've got 27 characters 327 bytes
we have those symbols that we're needing
to Output
but in the original lzw algorithm we
have a 12 bit a 4096 entry symbol table
and so each of those is a 12 bit number
so we multiply by 1.5 to get 21 bytes
but we've still managed to get some
compression even in this relatively
short example
so let's have a look at what else are W
is giving us and what we could maybe
improve
we have this incremental adaptation
which is good because as the symbol as
the input changes you get new symbols
you start getting longer symbols being
made up
but there
we're only adding one more character
each time and I think it would be good
if we can find a way to expand that
to to increase the the size of the
symbols we're putting into the symbol
table sort of faster than that other
problem is that when we're writing data
out initially
um we only actually need eight bytes
sorry eight bits but we're writing 12.
um
and that's a that's a big overhead right
we're also Limited in this 4096 entry
symbol table uh when we reach the 4096
symbol we have to literally say forget
everything you ever know about the input
stream and start again from scratch
despite all this uh this the lzw
algorithm is actually used in the GIF
187a and the GIF 89A standards which is
where I need to mention
the patents
ordinarily there's a role of ominous
Thunder at that point but
um what happened here was Terry Welch
was working for Sperrys Barry got bought
by Unisys Unisys decided to start
enforcing the patents on people who
wrote algorithms to produce GIF images
uh the what was the internet then uh
kind of didn't like this companies
didn't like this uh companies fought
back a bit it was unpopular Unisys
decided not to and then I decided to do
it again and it was unpopular again
uh the patents expired in 2004 but by
that time uh in sort of early in the 90s
the graphics producing community in the
web Community as it was at the time
decided that the thing that we really
needed was a better standard gift was
also limited to 256 byte car so 256
color simple color tables so we needed
true color and better grayscale and
things like that so they invent the
graphics Community invented PNG which in
which used
lz77 and zedlib to do its compression
which was patent well patent free
so
that's kind of why I think that's the
other reason why I think uh Elder W
doesn't get as much scrutiny these days
for what we could do to improve it as
maybe uh lz77 has
so what can we do to improve lzw
well I reckon firstly we can find a more
efficient way to write
the initial data that is starting to add
to our symbol table
secondly
the the one of the big problems is you
can probably imagine if you're writing
just say text file you're only using 96
of the 256 characters
and that's a whole bunch of symbol table
that you have effectively wasted because
you're never using it
so we should start with as as little as
possible in the symbol table
um
we also want to try to use variable
length coding so one thing that an
improvement on Terry uh of the W that I
think Terry watch suggested was that if
we're output if we're less than symbol
512 we only out need to Output nine bit
symbols
we have already more than eight bit
eight bits of symbol in the simple table
but less than nine bits so we can always
represent those with nine bit numbers
when the compressor adds the 512 symbol
it goes up to 10 bits when the
decompressor recognizes that it is on
the FI the 512th symbol it knows the
next symbol is going to be 10 bits so
they're synchronized still so we can
shorten how much data work to go into
um send per symbol
I also want to look at ways that we can
learn
the patterns in the data faster and this
is essential essentially what all of the
improvements in
lz77 over the years have done they have
found ways of getting finding better
matches which also means we need a much
larger symbol table I mean
lzma is typically working with up to
four gigabytes of memory
4096 symbols is just not enough right
the last thing that I want to kind of do
in my thoughts about improving uh lzw is
still I wanted to stay true to that idea
that we are adding symbols to a
dictionary to a table
um from how we've built up the input
it would be nice if we could say okay
this symbol occurred here like you know
you're reading a Python program it uses
the word import so we're going to use
we're going to say directly write up the
import the word import is going to be a
symbol that you're going to need in the
future
and the problem is that that starts
looking awfully a lot a lot like lz77
where we said this amount of data was
repeated and I feel like
that's kind of a crossover here I'd like
to stay true to that lzw idea
Okay so
uh the LZ PW algorithm that I've been
working on
its main I think it's main Improvement
is that we alternate lists of literal
characters
um and then symbols we have a different
way of writing each of those and we will
basically say you will write as many
literal characters as you can until and
until there's a symbol that you you can
match and then you write symbols for as
many symbols as you can match until you
have to go back to literals
the symbols we're going to form similar
to the way that lzw forms them so that
when we read the literal string a b c d
we'll form these three symbols A B B C
and C D
the at the moment the way the code works
is that when we read the symbols a b and
c d we're also going to create the
symbol ABC now I that what I'm trying to
experiment with and I literally had a
brainwave as I was at the end of
um Seb Chan's keynote I don't know why
then but I realized how I can get it to
not only add ABC but in fact at ABCD as
a symbol and if we can do that then now
we're going to expand our the symbols in
our symbol table are going to start
expanding much quicker
um we're also going to store those
symbols obviously in a separate table
and we're going to start numbering from
zero we're going to literally start with
zero symbols in the table
and each of these lists literals or
symbols is going to be prefixed by
lengths and lengths so we're going to be
written in Fibonacci coding
what's Fibonacci coding I hear you cry
well
um
this is a little bit of a diversion but
number bases can be fun we all use base
10 coding where you read from right to
left you multiply by the bay the value
of that column in the base
add the the value multiplied by that to
produce the number and we've obviously
familiar with this with doing this with
binary coding where we just add the
values of each of those bases where the
base increases right from right to left
Fibonacci closing as you've probably
guessed now
um You the base values are the Fibonacci
numbers so that number there is 34 plus
1 plus 8 plus 3 plus 2.
and you've probably figured out here
hang on three plus two is five that's
also a Fibonacci number so we should
probably write that as
um eight plus five oh that's another
Fibonacci number that's 13.
so
here we can we can observe that if
there's a kind of canonical way to write
Fibonacci numbers you always you can
always write to them using the highest
Fibonacci number possible you'd never
need to write two ones side by side
and so the other clever thing about
Fibonacci coding is that we're actually
going to turn that around and write it
left to right increasing
and then add a one bit on the end and
when we see two one bits we know the
number has terminated
okay
so Fibonacci number Fibonacci coding is
self-terminating it also in some ways is
resistant to bit errors which is kind of
nice
it's easy to decode because we simply go
up the Fibonacci sequence it's a greedy
encoding algorithm which is as soon as
you know you can work out the
Fibonacci number that's
just below or equal to your current
number you subtract that you write a 1
and you write zeros until you get the
next Fibonacci number that is is uh
greater than that and
um so just less than that or something
like that yeah
because we're going down it's less than
um and you keep on doing that until you
run out of zeros and then chuckle one on
the front you reverse it around and
there's your encoding
there are schemes of Fibonacci coding
that can cope with writing negative
numbers and zeros and things like that
I'm just we only need to use the
simplest here because we're encoding
lengths and we never need to write a
zero length thing
okay so that's enough Theory
um the last thing I will say about the
Fibonacci coding is if you look at the
other variable length bitcoatings like
inlias gamma coding and Lys Delta coding
they are no more efficient than this but
they require a lot more logic to decode
um and you know we're really kind of at
that theoretical limit we could write we
could have Huffman tables but in order
to have a Huffman table you need to have
pre-encoded it or have some way of
transmitting it and that adds more bytes
this is kind of efficient right okay so
links are going to be stored in
Fibonacci coding
so let's have a look at what we do with
our example in coding this this again
so we're going to start out with the
literal ban we never start in simple
coding we always start in literal coding
because we have nothing in the simple
table
and we write we add we're looking
forward to the a so we can write the
three symbols b a a n and n a
and at the point where we're looking at
the A and we're looking forward to the N
we can say oh that's a symbol entry we
know there might be more than some more
symbols but we've got a n we're looking
forward to a something
um and here we need to know with it's uh
useful or it's sort of important in the
algorithm to know that a is a prefix of
a symbol somewhere we've seen it before
in our input if we saw a q there
um then we'd know no symbol starts with
Q so we it's impossible for us to have a
symbol with q that had is Q something in
it and therefore we can just go straight
back to literal coding but we might be
encoding something here that is a symbol
because it starts with a but then we
look forward to the space and say no
there's no a space symbol
at that point we need to Output the A
and the space so we've written two
literals
and we've we're looking forward to the
capital B so we've added those two more
symbols important to note here that we
have
more than four symbols in the table at
this point this will be important later
but now we can start writing symbols and
obviously this is kind of going to
follow that process that
um or the W uses to construct symbols we
keep on seeing symbols we add the next
character there
um
and we keep on building up this list of
symbols that we're going to Output until
finally we have written the whole input
Okay so
how does this do for
um
compat a size comparison compared to the
original input well we're going to need
to work in bits here as you've probably
guessed
and so we need to multiply it by eight
so we've got 250 216 bits in the input
so we're going to write a string of
length 3 which in Fibonacci coding is
zero zero one one and then we can write
the the initial 8 bit characters
then we write a a symbol run of length
one that is 1 1 and then the symbol
number we needed was
001 there were five b five symbols in
the table at that point
Which is less than eight so we needed at
least three bits to encode that number
um
so we've written a total of five bits
there
we then write two characters
um and that takes 19 bits and then this
sequence we've got less than 16
um
symbols in the symbol table when we're
writing this so we can use
4-bit
4-bit symbol numbers
prefixed by the length in six bits is 38
bits for a total of 90 by 90 bits
which I have I I think that's pretty
cool right
um
how does that compare if we were doing
that in lzw well we had 14 symbols and
they're 12 bits each and so they're 168
bits even if we go down to nine bits we
still only get 126 bits out of lzw so
this is actually Improvement I I feel
like I'm I'm on the right track here
somewhere
okay
so how does this do with more real world
data so I ran it I ran this on its own
source code and that got a ratio of
about 2.56 to 1
user shared words compressed down
slightly less less okay how does that
compare to something as old as gzip
okay well we've still got work to do
then
um it's not surprising because I think
there are a lot of improvements we that
we can get but I would just want a
couple cover a couple of things in the
code uh which is at my GitHub address
um before I sort of summarize on what
um
uh what what the current state of it is
and where the future is going
um so the code I'll firstly say is still
extremely experimental there's a lot of
ideas that are tried out that are that
I've got you know
um
uh flags on to say if if we're using
this this particular encoding try this
that sort of stuff I'm trying to keep as
many ideas in there because I want to
find out which work what works and what
what doesn't
um and this is still early code so I I'm
really still not sure which of these
ideas might prove to be useful as as
you'll see
the second is uh people who know me will
kind of recognize
um my sense of humor here but there's
the thing called the mabulate flag now
mabulate is a word I invented it's what
you do say uh if you've got a Rubik's
Cube and you know that uh the way to
solve it is to get all of the colors on
each face all together and the way to do
that is by rotating the faces but you
don't know
because we haven't learned yet the the
specific algorithms to move things
around but you think that if you keep on
sort of playing with it something might
end up in the right shape and you know
and colors might be able to move
together and you'll kind of gradually
learn your way around but you're not
quite sure what you're doing so that's
mabulating
so the mabulate flag works like this it
is basically that process that we did
we're where we're looking at whether
this symbol is a prefix whether we've
possibly got a another symbol because
we've got the prefix
If the symbol hasn't matched and the
last character is a prefix then we set
that flag and we that's to remember the
character that we're currently on
because it could be the start of the new
the new symbol
If the symbol hasn't matched and the
last character
or the last the symbol that we're
looking for is not a symbol
then we go we now need to go to literals
and it's the nebula flag is set at that
point it means that we previously looked
at a character which might have been a
prefix but turns out not to be and at
that point we need to Output that
character as well so it's a bit
complicated and as I said I I scratched
my head for a long time trying to find
the right word for this and I just
couldn't so I used mabulate because
that's me okay so the other thing you
need to know about the code is that
there's this array this thing called
variable called to write that if we're
in literal mode is a string of the
physical characters we're going to write
out if it if we're in symbol mode that
is a list of strings so don't enforce
type checking on that because it's going
to change
okay so where are we uh with LZ PW the
first thing I do need to share with you
is the failures
um the one really interesting thing I
discovered almost by accident uh was
that I had started on a totally wrong
premise I thought that it would be more
efficient to write the symbols in the
symbol table using Fibonacci codes and
if we wrote those in uh a if we used
like a move to front algorithm or we
favored the least
so the yeah the most recent symbol uh
the most recent symbol is the most
complex and it's the most the one most
recently found in the input so if we can
match that using fewer bits then we we
should actually
like this is how I was thinking which
that should give us better compression
than if we're just using a fixed width
number of bits based on the symbol table
size at that point in time
and I tried this out and I had spent
months working on that and then I was
going through tidying up the code trying
to make it vaguely presentable for this
conference
and I uh one of the things that uh was
set in there was the ability to use
variable length Fibonacci coding for
symbols or still use fixed length coding
and in one of my tests I ran it and left
the flag off
so it was using fixed length symbols and
it was shorter
I'm like okay well that's that idea out
the window why is that
and then I realized
that
if you think about the idea of Fibonacci
coding part of the reason of that final
one is that it has to tell the decoder
this is where you where you stop it
needs there needs to be an explicit
piece of information passed from the
encoder to the decoder to say this is
the length of that symbol
but if we already know the symbol table
size that's an implicit piece of data
that both the encoder and the decoder
know and therefore it doesn't need to be
transmitted and there therefore we can
actually use more of the the bit space
to transmit information as opposed to
avoiding writing two ones together
so that was a discovery
um but I'm glad I discovered it right
um the other idea that I've had in there
which the moment I pretty much removed
but it's there because it you know you
never know
um is I the idea of having a header in
front of literal blocks and in front of
symbol blocks that would both indicate
yes this is a little block or a symbol
block
and then might indicate some Flags about
that I'll cover some of the reasons why
I think this might be useful there is
never a situation where you need to
write two literal blocks one after the
other
because all you will always find it is
more efficient to Simply join them
together
it's possible that we might need to
write two symbol blocks one after the
other and that would most likely be when
we have we're just about to change
symbol sizes
and we want to write the all of the
symbols currently in the buffer out in
the shorter format and then move on to
the longer format
but I'm not sure yet if having an extra
bit in the header of the symbol list
is worth that overhead
it we're going to experiment right okay
so uh current features are basically
that it does do efficient literal coding
and it does do efficient variable coding
of symbols and I'm really proud of that
the future features one of the main ones
that I'm working on is the ability to
backtrack through how you're encoding
the symbols at this point
and the easiest way to demonstrate this
I've found it's a bit of a boring string
it's not as good as bananas but it is
this
so as we're reading through that to
write it we write the first five
characters the then have a b b c c d and
d dot dot a
then we can write a b c d and at that
point we add the ABC symbol
um
we add we have to add a literal comma
and then the symbol table has a b c d
and the ABC symbol
so we're about to read ABC
um
we get to ABC and we're looking at D we
we're mapulating that we're looking
ahead to C and there's no DC in the
symbol table so we would have to write a
literal D at that point
and then move on
but
what if we could instead write that as
the symbols a b c d
we've rearranged these the symbols that
we're encoding and then we can write a
second CD and where that it is always
more efficient like that uh
second D there was 10 bits of stepping
back into literals
that's a that's a 10-bit symbol that we
could put in there that's that's you
know where if we're a
1024 symbols in our table we're still
going to be more efficient just to write
that one character and we're probably
going to write more than one which means
we're probably saving 19 bits so
um we've got that that option of uh
thinking about how we encode those
symbols it then does mean that it we may
change what symbols uh the
decoder
sees in its symbol table and this is
something that's really important this
is where I'm going to have to really
play with this to try and try and
understand what the effects of that
rearrangement are the other thing that I
found when I was playing around with
this it worked fine with some of my test
examples and I gave it the code of
symbolizer to encode and it used all 32
gigs of my machine and I had to kill it
because it was running on flat out on a
CPU and the reason for that was that it
was looking through a list of about a
string probably in the order of
um
80 to 90 characters but it was doing
this like thousands of rearrangements of
that finding every possible way that you
could rewrite that so I have some ideas
on how to improve that the other way the
other ideas that I think we I want to
explore here are that
uh it would be good rather than having
some sort of signal to say throw away
your symbol table and start again from
scratch if we could throw away the
symbols we never needed again or the
symbols that just hadn't been used
recently we could tell the decoder to
forget those
even if we used fixed length coding
maybe we still need a move to front idea
so that uh the the uh the later symbols
the least recently used symbols can be
thrown out rather than say going up to a
higher symbol table a symbol length what
if we had literals that don't create
symbols we know we've got a header that
we never ever see again in the input and
we just say
the decoder should not encode symbols
from this because you're just placing
symbol space
what if we had uh literals that don't
create output but create symbols we
could say recognize some patterns uh the
you know in the first sort of
um
a 10 20 100 symbols find the most
efficient way to write those in a
compact string and then transmit that to
build the symbol table that we're then
going to use
to get
um just sort of almost immediately go
into symbol output
uh what if we are encoding not just one
stream but multiple streams like a tar
file or something like that
could be maybe
sometimes share this symbol table with
the next file or throw it away and the
three we're reading something completely
different
um
this last one was prompted from a friend
of mine who asked me would it be how
would it Go
reading Chinese characters and I
realized that actually at the moment
I've been talking about bytes throughout
my code but in fact my code is written
around Python's interpretation of utf-8
and that means that if the literals
still contain UTF cat 8 characters which
are perfectly readable in as an input
stream they're still just bytes at the
end of the day
but the symbol table is now not built up
of those bytes but of the characters
that have more meaning in the text
that too could be you know could give us
more and Co more compression if we're
reading something like wav files
which are notoriously hard to compress
because the uh if you look looking at
say a 16-bit PCM encoded each sample is
two bytes but there is no relationship
between essentially between the the
least the the lowest byte of sample one
and the highest byte of sample two
but as 16 bit words they are absolutely
related and if we could encode them as
symbols rather than simply treating it
as a stream of bytes I think that would
give us improvements as well so there's
a whole bunch of ideas that I'm
percolating away I'm still working on
the code but I'm hoping to have some
more results soon thank you
[Applause]
thank you
any questions
um
unfortunately we're actually out of time
right sorry and we're in room change so
we we can't really go over time like we
did do before lunch
um so wondering how would you be okay
with people come up and ask me any
questions you like I'd love to have
collaboration on this thank you thank
you thank you once again
[Applause]