PREV INDEX NEXT

Author: Stan Eisenstat
Subject: Re: [Cs323] length of codes in LZW FOLLOW-UP
Date: Monday, 12 Oct 2020, 07:11:59


    > Message Posted By: Unknown
    >
    >      ``Because the LZW codes do not have the same prefix
    >      property (i.e., no code is a prefix of another)."
    >
    > I am confused as to what this means. I thought the codes were the numbers
    > that "index" the strings in the LZW table.

Huffman codes can use a variable number of bits per code
because no code (i.e., sequence of bits) is a prefix of
another.

If the codes used by LZW are indices into an array of
strings as in the example used in class, then they do
not have this property.  Thus you need to send enough
bits to distinguish them.  For example, you cannot send
11 for 3 since 11 is a prefix of 111, the binary for 7.
=====

    > For example in the sheet we went over in class, the code for 'a' is 1, for
    > 'b' is 2, for 'c' is 3, for 'ab' is 4, etc...
    >
    > Therefore if we were to send over 1 when there are 5 prefixes in the
    > table, we would send 1 as 001 with three bits instead of two bits as 01.
    > This is because we must use the number of bits to accommodate sending ANY
    > code.

As you note, you must send the leading 0s.
=====

    > If this is correct, how is the prefix property related here?

See above.

--Stan-
PREV INDEX NEXT