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

Groups > comp.compression > #1522 > unrolled thread

Using various kinds of frequencies

Back to article view | Back to comp.compression

Contents

  Using various kinds of frequencies Mok-Kong Shen <mok-kong.shen@t-online.de> - 2012-09-22 11:17 +0200
    Re: Using various kinds of frequencies Thomas Richter <thor@math.tu-berlin.de> - 2012-09-24 11:01 +0200
      Re: Using various kinds of frequencies Mok-Kong Shen <mok-kong.shen@t-online.de> - 2012-09-24 23:13 +0200
        Re: Using various kinds of frequencies Willem <willem@turtle.stack.nl> - 2012-09-24 21:25 +0000
        Re: Using various kinds of frequencies glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-09-24 22:20 +0000
        Re: Using various kinds of frequencies "George Johnson" <matrix29@charter.net> - 2012-09-24 20:57 -0400
        Re: Using various kinds of frequencies Thomas Richter <thor@math.tu-berlin.de> - 2012-09-25 10:50 +0200

#1522 — Using various kinds of frequencies

If one in the space of, say, 8 bits, optimally allocate a part to the
most freqeunt words, a part to the most frequent digraphs and finally
a part to the single characters, couldn't that eventually be better
than a common Huffman coding based on frequencies of single characters
alone? If that has already be tried out, could someone give reference
informations? Thanks.

M. K. Shen

[toc] | [next] | [standalone]

#1525

Am 22.09.2012 11:17, schrieb Mok-Kong Shen:
>
> If one in the space of, say, 8 bits, optimally allocate a part to the
> most freqeunt words, a part to the most frequent digraphs and finally
> a part to the single characters, couldn't that eventually be better
> than a common Huffman coding based on frequencies of single characters
> alone? If that has already be tried out, could someone give reference
> informations? Thanks.

Sorry, I don't quite follow the question. Is your question related to 
the optimal definition of the alphabet, and are you wondering why an 
alphabet may include digraphs (such as 'th', 'qu' or 'wh') in addition 
to single characters ('a' to 'z')?

The answer is that a Huffman code is a zero-order code - it only knows 
the frequencies but not the relations between characters. IOW, given 
zero-order statistics of the English alphabet, the vowel 'U' might not 
be very frequent and may be given a moderately long code, whereas it is 
very likely that a 'U' follows a 'Q'. In fact, almost all 'Q's are 
followed by 'U's. If one is contraint to zero-order coding, it thus 
makes sense to define a new symbol 'QU' with moderately low probability, 
and another symbol 'Q' which exceptionally low probability since the 
former ('QU') is considerably more likely than 'Q' alone without a 'U'.

Given that, a better alternative is of course a higher-order code, i.e. 
a code that assigns probabilities conditioned to the predicessor, i.e. 
make probabilities depend on the character seen before. Such codecs are 
possible and are frequently used, but the number of probabilities to be 
kept grows longer and longer the larger the context (the number of 
characters to be analyzed and to be conditioned on) grows. They thus 
soon become impractical. Thus, typically a compromize is made to 
truncate the context at some point. Thus, for example, for 'U' a context 
of at least one character (to care about the 'QU' case) makes sense, 
whereas for other characters such contexts are less fruitful.

It all depends on the application and the data you want to model.

Greetings,
	Thomas

[toc] | [prev] | [next] | [standalone]

#1526

Am 24.09.2012 11:01, schrieb Thomas Richter:
> Am 22.09.2012 11:17, schrieb Mok-Kong Shen:
>>
>> If one in the space of, say, 8 bits, optimally allocate a part to the
>> most freqeunt words, a part to the most frequent digraphs and finally
>> a part to the single characters, couldn't that eventually be better
>> than a common Huffman coding based on frequencies of single characters
>> alone? If that has already be tried out, could someone give reference
>> informations? Thanks.
>
> Sorry, I don't quite follow the question. Is your question related to
> the optimal definition of the alphabet, and are you wondering why an
> alphabet may include digraphs (such as 'th', 'qu' or 'wh') in addition
> to single characters ('a' to 'z')?
>
> The answer is that a Huffman code is a zero-order code - it only knows
> the frequencies but not the relations between characters. IOW, given
> zero-order statistics of the English alphabet, the vowel 'U' might not
> be very frequent and may be given a moderately long code, whereas it is
> very likely that a 'U' follows a 'Q'. In fact, almost all 'Q's are
> followed by 'U's. If one is contraint to zero-order coding, it thus
> makes sense to define a new symbol 'QU' with moderately low probability,
> and another symbol 'Q' which exceptionally low probability since the
> former ('QU') is considerably more likely than 'Q' alone without a 'U'.
>
> Given that, a better alternative is of course a higher-order code, i.e.
> a code that assigns probabilities conditioned to the predicessor, i.e.
> make probabilities depend on the character seen before. Such codecs are
> possible and are frequently used, but the number of probabilities to be
> kept grows longer and longer the larger the context (the number of
> characters to be analyzed and to be conditioned on) grows. They thus
> soon become impractical. Thus, typically a compromize is made to
> truncate the context at some point. Thus, for example, for 'U' a context
> of at least one character (to care about the 'QU' case) makes sense,
> whereas for other characters such contexts are less fruitful.
>
> It all depends on the application and the data you want to model.

I mean the following: An 8-bit byte has a coding space of 256. One could
allocate a part of it to code some high frequency words, another part
to code some high frequency digraphs and the rest to code the
alphabetical characters. I assume also that these frequencies are
known (averages of natural language texts). I like to know whether
that would result in some compression that is not too bad as compared
to, say, Huffman applied to single characters as usual.

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#1527

Mok-Kong Shen wrote:
) I mean the following: An 8-bit byte has a coding space of 256. One could
) allocate a part of it to code some high frequency words, another part
) to code some high frequency digraphs and the rest to code the
) alphabetical characters. I assume also that these frequencies are
) known (averages of natural language texts). I like to know whether
) that would result in some compression that is not too bad as compared
) to, say, Huffman applied to single characters as usual.

Probably.  It's like Lempel-Ziv compression, but with a fixed dictionary.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#1528

Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:

(snip)
>>> If one in the space of, say, 8 bits, optimally allocate a part to the
>>> most freqeunt words, a part to the most frequent digraphs and finally
>>> a part to the single characters, couldn't that eventually be better
>>> than a common Huffman coding based on frequencies of single characters
>>> alone? If that has already be tried out, could someone give reference
>>> informations? Thanks.

(snip)
> I mean the following: An 8-bit byte has a coding space of 256. One could
> allocate a part of it to code some high frequency words, another part
> to code some high frequency digraphs and the rest to code the
> alphabetical characters. I assume also that these frequencies are
> known (averages of natural language texts). I like to know whether
> that would result in some compression that is not too bad as compared
> to, say, Huffman applied to single characters as usual.

If you only know byte (character) frequencies, but not digraph
or higher, then single character Huffman is the best you can do.

If you know more, then you can use that information.

You could just Huffman code byte pairs, which would automatically
code digraphs (some directly, some as the first or last character
of another pair), and code single characters about as well as
single character Huffman.

-- glen

[toc] | [prev] | [next] | [standalone]

#1529

"Mok-Kong Shen" <mok-kong.shen@t-online.de> wrote in message 
news:k3qiej$noo$1@news.albasani.net...
> Am 24.09.2012 11:01, schrieb Thomas Richter:
>> Am 22.09.2012 11:17, schrieb Mok-Kong Shen:
>>>
>>> If one in the space of, say, 8 bits, optimally allocate a part to the
>>> most freqeunt words, a part to the most frequent digraphs and finally
>>> a part to the single characters, couldn't that eventually be better
>>> than a common Huffman coding based on frequencies of single characters
>>> alone? If that has already be tried out, could someone give reference
>>> informations? Thanks.
>>
>> Sorry, I don't quite follow the question. Is your question related to
>> the optimal definition of the alphabet, and are you wondering why an
>> alphabet may include digraphs (such as 'th', 'qu' or 'wh') in addition
>> to single characters ('a' to 'z')?
>>
>> The answer is that a Huffman code is a zero-order code - it only knows
>> the frequencies but not the relations between characters. IOW, given
>> zero-order statistics of the English alphabet, the vowel 'U' might not
>> be very frequent and may be given a moderately long code, whereas it is
>> very likely that a 'U' follows a 'Q'. In fact, almost all 'Q's are
>> followed by 'U's. If one is contraint to zero-order coding, it thus
>> makes sense to define a new symbol 'QU' with moderately low probability,
>> and another symbol 'Q' which exceptionally low probability since the
>> former ('QU') is considerably more likely than 'Q' alone without a 'U'.
>>
>> Given that, a better alternative is of course a higher-order code, i.e.
>> a code that assigns probabilities conditioned to the predicessor, i.e.
>> make probabilities depend on the character seen before. Such codecs are
>> possible and are frequently used, but the number of probabilities to be
>> kept grows longer and longer the larger the context (the number of
>> characters to be analyzed and to be conditioned on) grows. They thus
>> soon become impractical. Thus, typically a compromize is made to
>> truncate the context at some point. Thus, for example, for 'U' a context
>> of at least one character (to care about the 'QU' case) makes sense,
>> whereas for other characters such contexts are less fruitful.
>>
>> It all depends on the application and the data you want to model.
>
> I mean the following: An 8-bit byte has a coding space of 256. One could
> allocate a part of it to code some high frequency words, another part
> to code some high frequency digraphs and the rest to code the
> alphabetical characters. I assume also that these frequencies are
> known (averages of natural language texts). I like to know whether
> that would result in some compression that is not too bad as compared
> to, say, Huffman applied to single characters as usual.
>
> M. K. Shen

    And logically, keeping a tag-along codebase library of high probability 
frequency pairs & triplets (found by compiling stored Huffman files as to 
the highest frequency statistical averages per 5000 files examined) per file 
extensions (or recognizable file types) would not hurt too much either.

    It could help to utilize these these statistical shortcuts rather than 
continually rediscovering them each and every file.
 

[toc] | [prev] | [next] | [standalone]

#1530

Am 24.09.2012 23:13, schrieb Mok-Kong Shen:

> I mean the following: An 8-bit byte has a coding space of 256. One could
> allocate a part of it to code some high frequency words, another part
> to code some high frequency digraphs and the rest to code the
> alphabetical characters. I assume also that these frequencies are
> known (averages of natural language texts). I like to know whether
> that would result in some compression that is not too bad as compared
> to, say, Huffman applied to single characters as usual.

Well, it would certainly provide some compression, but it would 
certainly be worse than Huffman. Basically, Huffman allocates bits in 
its output space whereas you would have to allocate entire bytes. IOWs, 
what you generate here is *also* some kind of Huffman code, but one 
whose bit sizes are constrained. Drop the constraint, and the efficiency 
will go up - really simple.

Of course I mean a higher-order encoding, not a zero-order Huffman. How 
well this method compares to zero-order Huffman I do not know.

Greetings,
	Thomas

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web