0
$\begingroup$

I am using language as a placeholder although I think it can be used in music too. I am unclear if the frequencies are given based on the text or the entire language. The latter would prove to be difficult because if we are to say that 'e' is the most common letter in English, wouldn't this shift over time with some new words being created and some being dropped due to fashion etc?

Say we are trying to encode the first book of Harry Potter, is the encoding basing the frequency of letters of the book only or of the English language at the time? Extending it to music, would the entire domain be all possible sounds the human ear can hear or only of the track being listened to.

$\endgroup$
2
  • $\begingroup$ It is more efficient to use frequencies of the text you are encoding rather than an entire language. $\endgroup$ – Nathaniel Feb 20 at 0:48
  • $\begingroup$ Could you make an answer so that I can upvote it? $\endgroup$ – heretoinfinity Feb 20 at 0:53
2
$\begingroup$

The statistics used to derive the Huffman codes from can come from any source that you want. For a practical example, the popular DEFLATE format allows both "dynamic Huffman codes" (in this usage it is not a form of adaptive Huffman coding, it means the codebook is specified in the data stream) and "fixed Huffman codes" (a codebook that is specified in the DEFLATE specification).

A codebook based on the statistics of the actual data being compressed generally results in a smaller compressed size. The trade-off is that a codebook that is not pre-defined must be supplied along with the data (the decoder still needs it), adding to the overall size. Canonical Huffman codes can mitigate the impact (requiring only the code lengths to be transmitted, the codes themselves can be inferred in a simple way), but transmitting the codebook is going to cost some extra data, and may not be worth the size overhead for short texts (especially when the statistics of the given text happen to approximately line up with the statistics on which the pre-defined codebook was based).

Other practical considerations may favour using slightly inaccurate statistics, for example statistics based on some prefix of the data to be able to start encoding without having to wait until the input is fully known. The more accurate you want the statistics to be, the longer the latency is between the "first input" and the "first output" of the encoder. Even if the input is entirely known at the start, depending on the application, gathering fully accurate statistics may not be worth the time investment.

$\endgroup$
1
$\begingroup$

If you wanted to compress 20 bytes of text, knowing the language would be useful. If you want to compress the first book of Harry Potter, no matter what language you pick, you would most likely not use Huffman encoding in the first place because it is just based on letter frequencies, but something like LZW encoding, which also handles correlations between letters (in other words, it handles the fact that some sequences of letters are more likely for others).

You would likely base the compression on the text, not on the language. For example, "Harry" will happen many times in this particular book, and it will be compressed a lot better than with compression based on the language. On the other hand, I doubt you'll find "Harry" in "War and Peace" at all.

$\endgroup$
3
  • $\begingroup$ Does LZW work with audio? I suppose given music chords sound correlations make sense. $\endgroup$ – heretoinfinity Feb 20 at 1:09
  • $\begingroup$ Could you clarify your first sentence "... knowing the language would be useful"? How useful as you go on to show convincingly that correlations are better with a given text and that Huffman encoding wouldn't be efficient. $\endgroup$ – heretoinfinity Feb 20 at 1:10
  • $\begingroup$ Most people use lossy compression for audio. For lossless compression you will first find some way to reduce the redundancy. The person doing the decompression needs the frequencies, so if you don’t use a known frequency table, that table must be part of the compressed text. It’s likely so large that you gain nothing at all. But if your compression and decompression algorithms contain frequencies for many languages built in, then you could just say “this text is Catalan, and here are the compressed bytes.” For 20 bytes, you can’t do much better. For many 100,000 bytes, LZW will be better. $\endgroup$ – gnasher729 Feb 20 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.