home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compress / 4778 < prev    next >
Encoding:
Text File  |  1993-01-23  |  1.5 KB  |  33 lines
  1. Newsgroups: comp.compression
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!rpi!sigma
  3. From: sigma@degas.ipl.rpi.edu (Kevin Martin)
  4. Subject: Re: zipsplit with pkzip204c Was: Re: Unix release? (Was etc.
  5. Message-ID: <9cl333-@rpi.edu>
  6. Nntp-Posting-Host: degas.ipl.rpi.edu
  7. References: <1993Jan14.051725.19618@ucsu.Colorado.EDU> <Jan19.211317.17236@halcon.dpi.udec.cl> <1jk4c1INN9fu@gap.caltech.edu>
  8. Date: Sat, 23 Jan 1993 04:13:06 GMT
  9. Lines: 22
  10.  
  11. madler@cco.caltech.edu (Mark Adler) writes:
  12. >Or perhaps you think that the other zipsplit optimizes the chunks
  13. >better.  I don't know what algorithm the other zipsplit uses, but
  14. >our's uses a simple "greedy" algorithm that achieves the optimum in
  15. >nearly all cases with typical distributions of entry sizes.  The
  16. >chunk optimization is an NP-complete problem, so there are lots of
  17. >approximate approaches to the solution.
  18.  
  19. This is what's called the Knapsack Problem.  It's NP-complete, but since
  20. your knapsack is usually relatively small compared to the total size of the
  21. files, an early-out algorithm which avoids combinations which will
  22. obviously not fit actually has to check very few combinations.  Even with
  23. four hundred files, I've never had to check more than 30000 combinations
  24. (well, my program does - not myself by hand) to get a perfect fit.
  25.  
  26. "Perfect" in the sense that no clusters are wasted, which also simplifies
  27. things.
  28.  
  29. -- 
  30. Kevin Martin
  31. sigma@ipl.rpi.edu
  32. "I told you I'd shoot, but you didn't believe me! WHY didn't you BELIEVE me?!"
  33.