Re: [HACKERS] LZ compressing data type - Mailing list pgsql-hackers

> > If it is, you are liable for a $5,000 fee to use it throughout your
> > site, or a per-licence fee if you are distributing (thay are worked out
> > on a per case basis but typical licences are $5 per unit sold from what
> > I am told).
>
>     It't  an  SLZ  algorithm, not LZW. There are FLZ and LZ77 out
>     too (and I don't know how many other subtypes). At least,  LZ
>     is  a  family  of  compression algorithms where LZW is just a
>     member of them.
>
> [...]
>
>     But thanks for the info.

    From the very beginning of US patent No. 4,558,302 (the thing
    behind Unisys's LZW):

        The compressor searches the input stream to determine the
        longest  match  to  a  stored  string. Each stored string
        comprises a prefix  string  and  an  extension  character
        where  the  extension  character is the last character in
        the string and the prefix string comprises  all  but  the
        extension  character.  Each  string  has  a  code  signal
        associated therewith and a string is stored in the string
        table  by,  at  least implicitly, storing the code signal
        for the string, the code signal for the string prefix and
        the extension character.

    The  format  my  code stores is different to this definition.
    It only stores offset/length pairs or literal bytes, signaled
    by  a  bit  in  a  control unit. So there is no prefix string
    and/or extension character at all.

    If someone might state that storing TAG's and  LITERAL  chars
    is  still equivalent to PREFIX and EXTension character, I say
    that my  code  possibly  output's  sequences  of  immediately
    following  TAG's, that aren't neccessarily PREFIX'es. One TAG
    could code a sequence of characters, not  previously  occured
    in  any other TAG, without any intermediate LITERAL character
    occured.

    And my  code  forgets  AUTOMATICALLY  about  too  far  behind
    occurences of matching strings for speed AND compression rate
    improvement.

    Thus I think my implementation is not related to this patent.

    When  reading  patent  #4,558,302  I  really  remembered  the
    question, if anyone could ever have  a  patent  on  rectangle
    front  lights for cars.  The definition is so general, that I
    cannot  think  that  gzip,  bzip  or   any   other   existing
    compression  tool doesn't use it's METHOD.  If such a GENERAL
    patent is possible at all, car  manufacturers  all  over  the
    world  would  have  to  pay millions of dollars license fee's
    just to sell cars with rectangular lights.

    I don't see any relationship between my code and what  Unisys
    has a patent for. If they see, I might be blind - or they see
    a horizon from inside a black hole. If  they  need  to,  I'll
    enlighten them.


Jan

--

#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me.                                  #
#========================================= wieck@debis.com (Jan Wieck) #