home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / compress / 4161 < prev    next >
Encoding:
Text File  |  1992-12-15  |  1.4 KB  |  40 lines
  1. Newsgroups: comp.compression
  2. Path: sparky!uunet!news.uiowa.edu!news
  3. From: williams@herky.cs.uiowa.edu (Kent Williams)
  4. Subject: Re: Fixed point of the lzw compression alg.
  5. Sender: news@news.uiowa.edu (News)
  6. Message-ID: <1992Dec15.165902.3227@news.uiowa.edu>
  7. Date: Tue, 15 Dec 1992 16:59:02 GMT
  8. References: <1gj129INNdv2@function.mps.ohio-state.edu>
  9. Nntp-Posting-Host: herky.cs.uiowa.edu
  10. Organization: University of Iowa, Iowa City, IA, USA
  11. Lines: 27
  12.  
  13. From article <1gj129INNdv2@function.mps.ohio-state.edu>, by ren@function.mps.ohio-state.edu (Liming Ren):
  14. > 
  15. > I like the lzw alg. a lot. I have a question after I studied the alg:
  16. > 
  17. > Is there a fixed point for lzw? By fixed point, I mean the file is unchanged
  18. > after we apply the compression alg. If there is one , what is the size of 
  19. > the shortest one?
  20. > 
  21. > Just a random thought. I hope it makes sense!
  22. > 
  23. > 
  24. > Liming Ren
  25.  
  26. Taking the Unix Compress.  You start out with your
  27. intial string table containing
  28.  
  29.     <NO PREDECESSOR>N
  30.  
  31. for N in 0..256.  The code for <NO PREDECESSOR>N is N, but the code
  32. will be output at nine bits of precision.  So any short string of symbols
  33. would have the extra bit inserted for each symbol.  I can't think of any
  34. string, off the top of my head, for which the input would equal the output.
  35. --
  36. Kent Williams -- williams@cs.uiowa.edu Work(335-4496) Home(338-6053)
  37. There used to be an inflammatory quote here.
  38.  
  39.  
  40.