Re: Using compression before encryption in device-mapper

[Guillaume Lacôte]

> > Oops ! I thought it was possible to guarantee with the Huffman encoding
> > (which is more basic than Lempev-Zif) that the compressed data use no
> > more than 1 bit for every byte (i.e. 12,5% more space).
>
> Makes sense, although I'd like to see the proof first.  Shouldn't be
> too hard to do.
>
I was referring to the paper by Jeffrey Scott Vitter "Design and Analysis of 
Dynamic Huffman Codes" (accessible through http://acm.org). It defines a 
refinement of the well-known dynamic Huffman algorithm by Faller, Gallager 
and Knuth such that the encoded length will use at most _one_ more bit per 
encoded letter than the optimal two-pass Huffman algorithm (it is also shown 
that the FGK algorithm an use twice the optimal length + on more bit per 
letter).

My conclusion comes from the fact that for every text, the optimal two-pass 
huffman encoding can _not_ be longer than the native encoding (apart from the 
dictionnary encoding). 

Actually I plan to implement the easier FGK algorithm first - if the whole 
matter makes sense.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/