efficient bitwise BWT ?

[Boris K]

The talks about bitwise BWT on this forum started in 2010.
The output of bitwise BWT looks interesting because you would
only need to encode lengths of runs, ok?
In bitwise case it's possible to transform input as big as 512 MiB using the conventional
5*N bytes of memory, where N is the size of input in bytes,
is it possible to complete the regular bytewise BWT and then transform quickly to the output of bitwise BWT?

[Shelwien]

> The output of bitwise BWT looks interesting because you would
> only need to encode lengths of runs, ok?

Actually no. I mean, its possible, but result of simple bitwise RLE won't be better than
bytewise BWT + MTF + RLE.

> In bitwise case it's possible to transform input as big as 512 MiB using the conventional
> 5*N bytes of memory, where N is the size of input in bytes,

No, if its true BWT, you'd need a pointer per symbol (ie bit).
So 40*N memory until 512Mb (since after than bit pointers won't fit in 32 bits).
Well, 33*N if we'd work with packed bits, but that'd be slower.

> is it possible to complete the regular bytewise BWT and
> then transform quickly to the output of bitwise BWT?

Its possible to compute bytewise BWT of 8 bit-shifts of the block,
then merge these.

I actually have a project where bitwise BWT is used:
https://encode.su/threads/2742-Compr...ll=1#post52493
You can also find standalone utilities for bitwise BWT (and BWTS) there.

[michael maniscalco]

Bitwise bwt, in theory, would be incedible fast. Only the increased memory is an issue. As for RLE, binary m99 is much better compression. See https://encode.su/threads/3103-exper...th-prediction: