Re: An interview question.

From: Thomas Matthews (Thomas_MatthewsSpitsOnSpamBots_at_sbcglobal.net)
Date: 07/28/04 

Date: Wed, 28 Jul 2004 14:30:54 GMT

Matt wrote:

> I was asked to compress a text file in a way that evey word be written
> with the number of times that such a word is repeated. Something like
> this:
>
> If this is the original file:
>
> ---------------------------------------
> AAAA BBB CCCC AAAA CCCC AAAA........
>
>
> the result will be:
> ---------------------------------------
> 3 AAAA
> 1 BBB
> 2 CCCC
>
>
>
> I appreciate any hints.
>
>
>
> Matt

One of the popular compression algorithm is based on this
technique. I think it might be Huffman, or start with an 'L'.
Perhaps somebody else will chime in. :-)

Essentially, the algorithm creates a table of patterns, then
if the pattern is repeated, writes out the index of the
pattern. 

-- 
Thomas Matthews
C++ newsgroup welcome message:
          http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq:   http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
          http://www.comeaucomputing.com/learn/faq/
Other sites:
     http://www.josuttis.com  -- C++ STL Library book

Relevant Pages

  • Re: Monster Siteswap List
    ... but based in siteswap notation. ... Matt does an excellent job of feeling out the group and finding a good ... Then his kindly takes it a step further, by using each pattern to build ...
    (rec.juggling)
  • Re: Public School was a waste of my time (Re: When even a Republican can see it....)
    ... your conjecture about Matt, which you are now treating as a fact, is ... The argument pattern is not one that I ... particularly care to play with. ... are responding to Matt--confidently accused him of being a liar, ...
    (rec.arts.sf.fandom)
  • Re: Monster Siteswap List
    ... but based in siteswap notation. ... Matt does an excellent job of feeling out the group and finding a good ... Then his kindly takes it a step further, by using each pattern to build ...
    (rec.juggling)
  • Re: Public School was a waste of my time (Re: When even a Republican can see it....)
    ... your conjecture about Matt, which you are now treating as a fact, is ... The argument pattern is not one that I ... particularly care to play with. ... are responding to Matt--confidently accused him of being a liar, ...
    (rec.arts.sf.fandom)
  • Re: Finding formatting items in a string
    ... I even found a FAQ on this... ... And a further completed regex, including the fact that you can use within the custom pattern if you want to... ... Just escape them again. ...
    (microsoft.public.dotnet.languages.csharp)
Loading