Compression - Re: A truely BIJECTIVE BWT is here!

You are viewing an archived Text-only version of the thread. To view this thread in it's original format and/or if you want to reply to this thread please [click here]

Author

Re: A truely BIJECTIVE BWT is here!

Mark Nelson

2007-12-15, 6:56 pm

On Dec 15, 2:46 am, Klaus Stengel <Klaus.Sten...@asamnet.de> wrote:

Thanks very much for taking the time to provide this explanation,
Klaus.

My gut feeling is that modifying the transform in this fashion is
going to reduce the compressibility of the transformed string. The
whole point of BWT is exploiting correlation in the last column values
- for every occurrence of 'foo' in the text, we know there will be a
consecutive run of characters in the last column that immediately
precede 'foo', Compressibility arises because all the characters that
precede 'foo' are collected.

Using David's modified rotation, it seems that we are giving up some
of this adjacency clustering, which ought to have a bad effect on
compression. Testing needed.

|
| Mark Nelson - http://marknelson.us
|

Sponsored Links