Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #42497

Re: compressing charatcers

Show all headers | View raw

On 2014-04-02, Keith Thompson <kst-u@mib.org> wrote:
> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
>> On Wednesday, April 2, 2014 4:35:59 PM UTC+1, Keith Thompson wrote:
>>> To solve that, you need a way to indicate whether a decimal string is a
>>> count or just a sequence of digits copied from the input.  This added
>>> information means that at least some input strings will result in
>>> *longer* output strings; this is unavoidable for any non-lossy
>>> compression algorithm.  (Unless you require a more limited character set
>>> for the input than for the output.)
>>> 
>> That's an inherent problem. But you can always store a single bit which 
>> indicates that the following is plaintext, so your maximum inflation is just
>> one bit. 
>
> You can't always store a single bit if your file system only supports
> whole numbers of bytes.

Most file systems support only a whole number of *blocks*.

But never mind that.

Even if the file system actually stores bytes rather than blocks,
it means that the bit streams which represent compressed files require
between 0 and 7 bits of padding. This means that 7 out of 8 times,
a compressed file has slack space which can absorb an extra bit.

So 7/8 files will stay the same length when extended by a bit,
and 1/8 will add an extra byte.

Over many files, this averages out to one bit per file, assuming
there is a uniform distribution of the eight possible padding lengths.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

compressing charatcers jay <arnuld.mizong@gmail.com> - 2014-04-02 05:23 -0700
  Re: compressing charatcers Richard Damon <Richard@Damon-Family.org> - 2014-04-02 08:58 -0400
    Re: compressing charatcers glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-04-02 19:40 +0000
      Re: compressing charatcers "Osmium" <r124c4u102@comcast.net> - 2014-04-02 15:02 -0500
      Re: compressing charatcers Keith Thompson <kst-u@mib.org> - 2014-04-02 14:52 -0700
  Re: compressing charatcers David Brown <david.brown@hesbynett.no> - 2014-04-02 16:06 +0200
  Re: compressing charatcers Keith Thompson <kst-u@mib.org> - 2014-04-02 08:35 -0700
    Re: compressing charatcers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-02 11:59 -0700
      Re: compressing charatcers Keith Thompson <kst-u@mib.org> - 2014-04-02 14:50 -0700
        Re: compressing charatcers Kaz Kylheku <kaz@kylheku.com> - 2014-04-02 22:23 +0000
  Re: compressing charatcers "BartC" <bc@freeuk.com> - 2014-04-02 18:54 +0100
    Re: compressing charatcers Keith Thompson <kst-u@mib.org> - 2014-04-02 11:45 -0700
      Re: compressing charatcers "BartC" <bc@freeuk.com> - 2014-04-02 20:12 +0100
        Re: compressing charatcers David Brown <david.brown@hesbynett.no> - 2014-04-03 10:12 +0200
  Re: compressing charatcers Barry Schwarz <schwarzb@dqel.com> - 2014-04-02 12:47 -0700
    Re: compressing charatcers jay <arnuld.mizong@gmail.com> - 2014-04-02 23:45 -0700
      Re: compressing charatcers Barry Schwarz <schwarzb@dqel.com> - 2014-04-03 00:18 -0700
        Re: compressing charatcers Ian Collins <ian-news@hotmail.com> - 2014-04-03 20:25 +1300
      Re: compressing charatcers Barry Schwarz <schwarzb@dqel.com> - 2014-04-03 00:43 -0700
        Re: compressing charatcers jay <arnuld.mizong@gmail.com> - 2014-04-03 22:56 -0700
          Re: compressing charatcers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-04 01:08 -0700
          Re: compressing charatcers Barry Schwarz <schwarzb@dqel.com> - 2014-04-04 12:53 -0700
      Re: compressing charatcers James Kuyper <jameskuyper@verizon.net> - 2014-04-03 10:19 -0400
        Re: compressing charatcers glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-04-03 15:52 +0000
          Re: compressing charatcers Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2014-04-03 10:10 -0600
      Re: compressing charatcers "BartC" <bc@freeuk.com> - 2014-04-04 11:19 +0100
        Re: compressing charatcers Ike Naar <ike@iceland.freeshell.org> - 2014-04-04 15:36 +0000
          Re: compressing charatcers "BartC" <bc@freeuk.com> - 2014-04-04 17:49 +0100
            Re: compressing charatcers James Kuyper <jameskuyper@verizon.net> - 2014-04-04 13:05 -0400
              Re: compressing charatcers Martin Shobe <martin.shobe@yahoo.com> - 2014-04-04 13:01 -0500
            Re: compressing charatcers Stephen Sprunk <stephen@sprunk.org> - 2014-04-04 12:56 -0500
              Re: compressing charatcers Stephen Sprunk <stephen@sprunk.org> - 2014-04-04 15:05 -0500
            Re: compressing charatcers Keith Thompson <kst-u@mib.org> - 2014-04-04 11:30 -0700
            Re: compressing charatcers Werner Wenzel <werner.wenzel@netcologne.de> - 2014-04-04 20:37 +0200

csiph-web