A "bijective" BWT transform variant that is inversible without prefix has been presented in a paper that claims 1% compression improvement in comparison to BWT.
The gain in compression ratio is about 1%. Note this gain is much greater than what can be attributed to the saving due due [sic] bijectivity, that is, the elimination of the end-of-string character,...
Gil & Scott - A Bijective String Sorting Transform


This claim is false. It is an apparent source of much confusion. The transform has similar context sorting properties as BWT. The difference is similar to applying a random rotation to the original input before adding end-of-string marker and BWT.

We study the compression gain by comparing the results from 2 versions of BWTmix compressor. One using BWT (1) and one using BWTS (1s). The results below show BWTmix 1 sizes without the prefix (which is 4 bytes per file) for comparing the compression ratio without the savings from end-of-string marker elimination.

BWTmix 1s   208 201
BWTmix 1 208 204
BWTmix 1s   71 696
BWTmix 1 71 696
BWTmix 1s   51 717
BWTmix 1 51 712
BWTmix 1s   1 123 608
BWTmix 1 1 123 610

For more results see the reference files test.

2017-2023 ©