BWTS help requested.

[Ernst]

I am experimenting with BWTS.cpp ( BWT Scott-ified).
I love iterative encoding/decoding and BWTS is clean with no overhead however I am simply merging Scott's code into my latest experiment and I'm needing some clarity on BLOCK_SIZE and "buffer' dimension. What does BLOCK_SIZE mean? Is it a maximum of what data it sorts? Can it be larger than 1000000 bytes? Can buffer[] be the size of the source file?

I did see some search results of for some newer efforts (BWTS) are using a larger block size and here I am getting a segmentation error on run after changing BLOCK_SIZE to 4000000 and pairing the "buffer[]" size to the file-size so I am not sure I am understanding the relationship of buffer[] and BLOCK_SIZE

I am trying to convert the BWTS.cpp to a function but perhaps there is something better now that is already a function???
That would be great! I lack advanced understanding of BWTS I admit

Any advice?

[Shelwien]

http://ideone.com/hkBo97
http://nishi.dreamhosters.com/u/bwts.cpp

[Ernst]

I am a humble experimenter so I ask what those links signify.
There is a lack of comment for such a humble experimenter as I.

[Shelwien]

Its a compact implementation of a bwts forward/inverse transform utility which can process whole files "larger than 1000000 bytes", eg. its tested with enwik8.

Also here's a x64 executable for it, use "bwts c input output" for bwts and "bwts d input output" for inverse transform.
It should be able to handle files up to 4G.

[Ernst]

Ah,...

You are reading me correctly.

Of course I wanted a plug and play solution but life is never that is it?
Thank you.

[Shelwien]

You can also look at http://compressionratings.com/i_bwtmix.html for a complete bwt/bwts-based compressor

[Ernst]

Code wise I am wanting a function call level BWTS()

[Shelwien]

That's why i posted that bwts.cpp - it has this function, just that its called obwt_bwts(), because its taken from openbwt library.

[Bulat Ziganshin]

let me search for you...
http://encode.su/threads/104-libBWT?...ull=1#post8627 and below
https://code.google.com/archive/p/mk-bwts/

[Piotr Tarsa]

I love iterative encoding/decoding and BWTS is clean with no overhead however I am simply merging Scott's code into my latest experiment and I'm needing some clarity on BLOCK_SIZE and "buffer' dimension. What does BLOCK_SIZE mean? Is it a maximum of what data it sorts? Can it be larger than 1000000 bytes? Can buffer[] be the size of the source file?

BWT (and variants) are block based algorithms, meaning that you split the file into independent blocks and transform them separately. For stationary sources the bigger the block size the better, but you need to take into account that too big block size will result in memory allocation failure.

Assuming that your file is 500 bytes long and your block size is 200 bytes then you get 3 blocks of following sizes: 200 bytes, 200 bytes, 100 bytes. Last block is smaller than the previous ones - it's normal in BWT as the set block size is in fact block size limit. It's best to have only the last block of variable size - this way you don't need to encode the block sizes, only the block size limit (in case it's not fixed).

[Ernst]

You guys are wonderful.
Indeed I see those functions clearly now. I am now working that code into my experiment.

I was tired and frazzled trying to get things to work so it was best I rested

Okay I have that code working.

One question of C++ is the new operator in the case of new byte[n]; where byte is type cast unsigned char the same as calloc() meaning it simply assigns a zeroed out block of memory?
I have not learned C++ yet so I massaged that C++ code to run under C

[Ernst]

BWT (and variants) are block based algorithms, meaning that you split the file into independent blocks and transform them separately. For stationary sources the bigger the block size the better, but you need to take into account that too big block size will result in memory allocation failure.

Assuming that your file is 500 bytes long and your block size is 200 bytes then you get 3 blocks of following sizes: 200 bytes, 200 bytes, 100 bytes. Last block is smaller than the previous ones - it's normal in BWT as the set block size is in fact block size limit. It's best to have only the last block of variable size - this way you don't need to encode the block sizes, only the block size limit (in case it's not fixed).

Cool.

I was wondering if a block size of the file would do more or better on the sort or it doesn't make much of a difference in reality?
I work mostly on binary transforms so it's best to ask.

[Shelwien]

1. In this case, new is equivalent of malloc, not calloc. See http://www.cplusplus.com/reference/new/operator%20new/
2. On x64 with swap enabled, there's no real limit to the block size.
3. Larger blocks mean better compression, but transformation is slower and uses more memory
(bwts.cpp implementation seems to use 6*blocksize for forward transform, and 7*blocksize for inverse one)

[Ernst]

1. In this case, new is equivalent of malloc, not calloc. See http://www.cplusplus.com/reference/new/operator%20new/
2. On x64 with swap enabled, there's no real limit to the block size.
3. Larger blocks mean better compression, but transformation is slower and uses more memory
(bwts.cpp implementation seems to use 6*blocksize for forward transform, and 7*blocksize for inverse one)

Thanks. In the case of new[] I would think calloc won't hurt. Malloc is the same as I expect in C by int Array[] then.
I was successful in using the Code you recommended. The experimental transform is running. It's a bijective process. So far so good.

[michael maniscalco]

I was wondering why David has not yet chimed in on this thread. He was never one to miss out on discussing his work. So I looked on a hunch and sadly it appears that he had passed away earlier this year. I just thought I would mention it since he was a long time contributor to the group and, as far as I can tell, his passing went unnoticed here.

http://news-ridgecrest.com/news/story.pl?id=0000005125

[Mike]

I was wondering why David has not yet chimed in on this thread. He was never one to miss out on discussing his work. So I looked on a hunch and sadly it appears that he had passed away earlier this year. I just thought I would mention it since he was a long time contributor to the group and, as far as I can tell, his passing went unnoticed here.

http://news-ridgecrest.com/news/story.pl?id=0000005125

Sad news.

[Ernst]

R.I.P. David Scott.