Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: compressing charatcers |
| Date | 2014-04-02 08:35 -0700 |
| Organization | None to speak of |
| Message-ID | <lntxabg2w0.fsf@nuthaus.mib.org> (permalink) |
| References | <3a14c8e6-f756-4f62-8490-2dd281b6ef36@googlegroups.com> |
jay <arnuld.mizong@gmail.com> writes:
> PROBLEM: You are given a string FOOFIGHTERS. You have to come up with
> an algorithm that will compress this string. You also have to make
> sure that you are not using extra memory. For example: FOOFIGHTERS
> will be compressed as FO2FIGHTERS. You should not use another array or
> bitfield to keep a frequency count for the individual letters.
Not commenting (yet) on your C, but ...
It's difficult to be sure just what the algorithm is based on a single
example. You should define the algorithm unambiguously in English.
"FO2FIGHTERS" is just as long as "FOOFIGHTERS". This particular
algorithm doesn't actually compress the input at all unless it contains
a run of at least 3 of the same character.
You'll also need to decide what to do with a run of 10 or more
characters. "XXXXXXXXXX" will *probably* compress to "X10", but it
should be stated explicitly.
Assuming that the algorithm is:
Replace each run of 2 or more of the same character by a single
instance of that character followed by the count in decimal
it has the interesting characteristic that every input string is mapped
to an output string that's the same length or shorter.
It has the even more interesting characterstic that there's no unique
reverse mapping; the compression loses information. Both "FOOFIGHTERS"
and "FO2FIGHTERS" map to the same output string.
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.)
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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