[Flac-dev] Blocking and compression.

[Josh Coalson]

--- Wayde Milas <wmilas at rarcoa.com> wrote:
> The reason for this post is I would like to know if I start coding
> again
> and releasing patches agaisnt flac in various areas, if they will be
> accepted. I'm not sure if these additions fit the "focus" of what
> flac
> is meant to be, so I thought I'd discuss them first. Keep in mind
> that I
> just subscribed to this list, so if these have already been gone
> over,
> just slap me with a tuna :)

hi Wayde.  sure, if they fit the goals, patches will make it in
in some form or another.

> Blocking: If the data set is local (not streaming) and we have the
> opportunity to make a coupla passes on the data, its possible to
> determine non fixed block sizes that fit orders of prediction
> closely.
> I'm sure this is no surprise to all of you. Actually coming up with a
> algo to do this is not as easy as it sounds. However, a few more %
> can
> be squeezed this way jsut but fitting lp's I believe. Then again,
> maybe
> not. Its depends if there are sharp shifts in the data set. If there
> are, finding these "edges" could benefit because you wont have a
> block
> where its encoding well, then goes all to hell because the predictor
> is
> missing by large numbers, and takes a while to readjust. The downside
> is
> not very large... scanning a data set and building a table of block
> offsets would not add that much overhead to the encoding process as
> its
> a lightweight operation (assuming i/o operations are moderately
> fast).

Miroslav did some experiments with searching for optimum blocksize.
from what I remember it made at best a couple percent difference.
there was a thread about it here a while back.

> Arithmatic encoding. Rice's granularity for encoding is 1 bit.
> (obviously) However there are techniques out there to encode
> fractions
> of bits. Well, you can only encode down to the granularity of 1 bit,
> but
> by doing a bit of magic, you get the net effect of being able to
> represent fractions of bits. Over a large data set, this can save
> hundreds of thousands of bits. I think this is where some of the
> closed
> source encoders make thier large gains. The down side is that
> arithmatic
> encoding takes more horsepower. Looking at some of the other
> encoders,
> any of them that take alot of time to encode are almsot certainly
> employing this technique. It might not be suitable for streaming, but
> would be a very nice option for archival purposes.

you can get very close ot arithmetic coding with range coding,
which is much faster and believed to be patent free.  monkey's
audio uses range coding as part of its entropy coder.  I did
some experiments and couldn't get much of a compression
improvement, but the area is far from exhausted.

Josh


__________________________________
Do you Yahoo!?
Yahoo! Hotjobs: Enter the "Signing Bonus" Sweepstakes
http://hotjobs.sweepstakes.yahoo.com/signingbonus