lkml.org 
[lkml]   [2004]   [Apr]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: 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/

\
 
 \ /
  Last update: 2005-03-22 14:02    [W:0.062 / U:0.492 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site