Messages in this thread | | | Date | Wed, 14 Apr 2004 13:25:06 +0200 | From | Jörn Engel <> | Subject | Re: Using compression before encryption in device-mapper |
| |
On Wed, 14 April 2004 12:02:07 +0200, Guillaume Lacôte wrote: > > > > 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).
Makes sense. You should try to use the crypto/ infrastructure in the kernel, add the compression algorithm there and use it through the normal interface. Apart from that, good lock! :)
Jörn
-- Simplicity is prerequisite for reliability. -- Edsger W. Dijkstra - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |