libBWT

[biject.bwts]

I took a quick look at it. THANK YOU YUTA IT WORKS GREAT. I don't think I am set up to use your stuff. I will try to follow the threads here but there was not very much source code for the BWTS part. I would like to test input versus output with some of my reference code. I suspect

Shelwien

could tell if they do the same thing since he tested BWTS with a file and I guess he has used your library before. But thanks again for putting it in. As far as I know yours is the first library to have it in.

Thanks
David A. Scott

[pat357]

I would like to test input versus output with some of my reference code.

There should also be 2 compiled exe's for BWTS : bwts.exe/unbwts.exe.
Maybe you can try these ?
I noticed however these exe's are often +50% slower than the "regular" bwt/unbwt...
Is this maybe inherent to bwts or is this because the way it's implemented ?
Thanks.

[biject.bwts]

There should also be 2 compiled exe's for BWTS : bwts.exe/unbwts.exe.
Maybe you can try these ?

I noticed however these exe's are often +50% slower than the "regular" bwt/unbwt...
Is this maybe inherent to bwts or is this because the way it's implemented ?
Thanks.

Yes last night was first time I saw the lib. It was after coming back form the Juarez war zone where a lot of my relatives live. Its sad there is little freedom there and what freedom we have here is draining away. And it was after relaxing with vast quanties of beer. I guess if I grow up in Russia it would have been vodka.

I did a quick test of BWTS.exe I found it today and it does not due the same think as mine. Well at least not the same when you just BWTS one file to another. But that may only be do to the fact he writes info for the blocking which is something I don't do. It should be easy enough to drop the blocking on output and then you have to know it on input. I assume he mostly used my reference code for the actual transformation. There are lost of places in my old code for speed up so the fact it currently takes twice as long is no big deal.

Actually looked at his source for BWTS, yes the blocking he adds to his test is outside the call that does the transform so will try to complie with that part dropped and use his lib. So far it looks like he did a great job.

I hoped after he compressed and uncompressed he checked to see if files matched. If they did he most likely has my code. I didn't realize at first that most of the source code is not in the zip file but instead I guess its in the lib file which I will play with,

[biject.bwts]

I got the given executable to run

However never got the source code to compile and run with the supplied library.
The malloc complained of a invalid change in assignment
so did a cast on the two lines to fix it. Later changed to 2 big arrays
no difference. every time it compiled and linked error free when you
run the code you get


Exiting due to signal SIGILL
Invalid Opcode at eip=0000d6bf
eax=00019041 ebx=00000044 ecx=0000000c edx=00000000
ebp=00019030 esp=013af3ec

when the C code line


err = BWTS(TT, UU, size);

is executed so its dying in code
linked from the library.

Any suggestions welcomed.
my pc is an AMD turion64

Thank You
David A. Scott

[biject.bwts]

It works!!

I was going crazy I kept trying to use the openbwt.a to resolve the problem
know I see there are 2 bwt.c one in the "samples" directry and one in the "src"
and the openbwt.a is not needed

The trick to get it to work was to use the bwts.c from the samples directory
and the bwt.c from the src directory.

Sorry I don't use other people libraries very much and when I go fast
I make mistakes faster. So thank you Yuta

Take Care
David Scott
P.S.
I really will take my time to look at this.

[biject.bwts]

OpenBWT-v1.4 has been released.

I am not sure if zxcb is still posting here. But I have been
in email back and forth correspondence with him. I don't
write very well and English is not his language so I hope
I understand him that version 1.4 is released. The main
difference is that the BWTS is now linear in time and space
before only the BWT was. He has sample code to do the
BWTS it does not tack on the word for buffer size. If the
program does not have enough memory it aborts. He
really did a fantastic job. If anyone has a problem I will
try to write him. But it really works fast all my tests are
using the MinGW setup for C.

From email to me:

"Now I understand the duval's algorithm. And, a linear-time
suffix sorting for lyndon-words was completed.

I sent you the test version of the BWTS. It runs in
linear-time using about 6n bytes of memory space. I will
add it to OpenBWT, if no bugs are found."

From later email to me:

"... Therefore, I put it in OpenBWT-v1.4 and uploaded to my SkyDrive.
GeoCities's site will be closing at October 26, 2009.

http://cid-d435dc59d0b86781.skydrive...enbwt-v1.4.zip

BWTS is useful for compressing small pieces of data.
However, the advantage of BWTS decreases as the input size grows."

I tested his code it works for the tests I tried.
One thing I noticed looking at his code. I think the UNBWTS is faster
than the UNBWT. So its possible that even if BWTS is slower than BWT
you may make up the difference if you uncompress the data more often
than you compress it. That's my gut feeling.

Take Care

[Bulat Ziganshin]

thanks, it looks very interesting:

D:\testing\3>t sst_test.exe enwik8
Input: enwik8, 100000000 bytes
BWT ... Done. (41.60 sec)
BWT -> SST -> RLE0 + Simple Structured Coding Model
  SST       Encoding Time   Decoding Time   Compressed Size
  MTF                1.05            0.64          22944781 (22.94%)
  M1FF               0.99            0.61          22620816 (22.62%)
  M1FF2              1.00            0.60          22480483 (22.48%)
  SIF                1.42            5.24          21648436 (21.65%)
  DC                 1.04            0.80          23118798 (23.12%)
  SDC                1.31            0.94          21774150 (21.77%)
  SRC                1.52            0.76          21434745 (21.43%)
  TP                 0.49            0.32          22901245 (22.90%)
  TS0                0.86            0.97          22311750 (22.31%)
  Bx(3)              1.30            1.36          22275919 (22.28%)
  Bx(4)              1.30            1.38          22354727 (22.35%)
  Bx(5)              1.69            1.73          22454707 (22.45%)
  Bx(6)              1.74            1.79          22559436 (22.56%)
  SBR                0.92            0.95          22129901 (22.13%)
  FC                 2.44            2.41          22354372 (22.35%)
  WFC                5.39            5.23          21944813 (21.94%)
  AWFC               5.63            5.31          21743432 (21.74%)
  IFC                8.79            8.61          22290628 (22.29%)
BWTS ... Done. (88.53 sec)
BWTS -> SST -> RLE0 + Simple Structured Coding Model
  SST       Encoding Time   Decoding Time   Compressed Size
  MTF                1.02            0.66          22944776 (22.94%)
  M1FF               0.96            0.59          22620859 (22.62%)
  M1FF2              1.00            0.60          22480509 (22.48%)
^C

using 500mb memory, afaik

[zxcb]

OpenBWT-v1.5 has been released. This new version includes a new BWTS and BWT-WT.

Changes in v1.5:

• Added BWT-WT. (Burrows-Wheeler Transformation algorithm based on Wavelet Tree)
• Rewrote BWTS with a new algorithm.

[Piotr Tarsa]

Is BWTWT an online algorithm? Ie. is it possible to put as much data in block as we can before exceeding memory limit? For example I want to set memory limit to 800 MiB and the program will use 450 Mib block, then 1200 MiB block, then 1000 MiB block, all of them processed using exactly 800 MiB of memory.

Can BWTWT be made to output identical files as BWTS or BWT?

[zxcb]

Is BWTWT an online algorithm? Ie. is it possible to put as much data in block as we can before exceeding memory limit? For example I want to set memory limit to 800 MiB and the program will use 450 Mib block, then 1200 MiB block, then 1000 MiB block, all of them processed using exactly 800 MiB of memory.

No, BWT-WT is two-pass & right-to-left algorithm.
But if you use the BWT of the reversed input string, it is possible.

samplecodes of about 50MiB memory limit:

[biject.bwts]

I noticed v1.4 not in set. I like it so in here it is?

[Yuri Grille.]

zxcb you work is incredible !! , keep working hard in this program

Yuri

[Piotr Tarsa]

No, BWT-WT is two-pass & right-to-left algorithm.
But if you use the BWT of the reversed input string, it is possible.

Why not do reversing when UNBWT-ing?

[Shelwien]

<Shelwien>
uh, i have intelc and it supports openmp
and i think that my gcc/mingw supports it too
<sami>
openbwt
as said i'd be interested how much it gets from multithreading
<Shelwien>
well, i guess i can try compiling it
...
i'm compiling the BWT sample from openbwt 1.5 with various intelc options
uh, now intelc complains about some loops...
ok, adding i=i fixed it %)
<sami>
if you get it compiled i don't necessarily need it.
(checking the usage from the source)
"bwt 100 enwik8 enwik.bwt" would do
<Shelwien>
yeah, that's what i do anyway
ok, results: http://nishi.dreamhosters.com/u/openbwt15test.txt
1. intelc vs mingw 4.4.2 produces similar results
(27.797s vs 27.687s), maybe IC even a bit slower, though
that's not certain
2. setting more advanced target cpus and enabling PGO
made IntelC results worse, but improved gcc results
3. enabling openmp did improve speed a little bit
(27.141s vs 27.344s) but overall it looks useless
4. last gcc openmp build produced different output, with
a couple of bytes moved, so there's likely a gcc or
openbwt bug

[Shelwien]

<Shelwien> 
  uh, i have intelc and it supports openmp
  and i think that my gcc/mingw supports it too
<sami> 
  openbwt
  as said i'd be interested how much it gets from multithreading
<Shelwien> 
  well, i guess i can try compiling it
  ...
  i'm compiling the BWT sample from openbwt 1.5 with various intelc options
  uh, now intelc complains about some loops...
  ok, adding i=i fixed it %)
<sami> 
  if you get it compiled i don't necessarily need it.
  (checking the usage from the source) 
  "bwt 100 enwik8 enwik.bwt" would do
<Shelwien> 
  yeah, that's what i do anyway :)
  ok, results: http://nishi.dreamhosters.com/u/openbwt15test.txt
  1. intelc vs mingw 4.4.2 produces similar results
(27.797s vs 27.687s), maybe IC even a bit slower, though
that's not certain
  2. setting more advanced target cpus and enabling PGO
made IntelC results worse, but improved gcc results
  3. enabling openmp did improve speed a little bit
(27.141s vs 27.344s) but overall it looks useless
  4. last gcc openmp build produced different output, with
a couple of bytes moved, so there's likely a gcc or
openbwt bug

[willvarfar]

Summary: 2 threads finish sorting nearly twice as fast as 1 thread.

I know slightly more about parallel programming than about compression (which is just enough to be naively confident), so looked quickly at how threads help sorting. You normally parallelize a sort by partitioning the data (or the buckets), and then each core tackling a single partition of the data, and then merging the results when they are done.

Well, you normally write a dedicated parallel sort routine that does it all in one, of course! But I just wanted to get an idea of what gains might be possible, so I took the shortest possible route.

I quickly slipped parallel sorting into my BWT test code (which uses std::stable_sort like bbb). It is obvious that std::stable_sort is not a very competitive sorter for latin texts, and it might be considerably less trivial or even less beneficial to slip parallelism into the libbwt and other BWT sorts.

The results (on a Core2Duo) for using std::stable_sort on enwik8 (100MB):

1 thread, 2m13.725s
2 threads, 1m22.479s
3 threads, 1m30.290s

(my source-code is buggy in exactly how it partitions the data; don't use it as is for real BWT; I think it's performance is indicative though, so the bugs - in this instance - are unimportant)

the source-code:

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>

#ifndef NDEBUG
    // sorts in std::algorithm asserting *really* *really* slows them down
    #define WILL_NDEBUG
    #define NDEBUG
#endif
#include <algorithm>
#ifdef WILL_NDEBUG
    #undef WILL_NDEBUG
    #undef NDEBUG
#endif

#define STABLE_SORT // else uses std::sort

struct stl_memcmp {
    stl_memcmp(const unsigned char* e) : end(e) {}
    inline bool operator()(const unsigned char *a, const unsigned char *b) const {
        // find first differing byte
        const int lena = (end-a), lenb = (end-b);
        if(int diff = ::memcmp(a,b,std::min(lena,lenb)))
            return (diff < 0);
        // one is longer than the other?
        return (a < b);
    }
private:
    const unsigned char* const end;
};

struct thread_sort_t {
    const unsigned char* S;
    const unsigned char** P;
    size_t N;
};

void* thread_sort(void* vparams) {
    const thread_sort_t params = *(thread_sort_t*)vparams;
#ifdef STABLE_SORT
    std::stable_sort(params.P,params.P+params.N,stl_memcmp(params.S+params.N));
#else
    std::sort(params.P,params.P+params.N,stl_memcmp(params.S+params.N));
#endif
    return NULL;
}

unsigned char* bwt_sort(const unsigned char* S,size_t N,int& I,char num_threads) {
    // make a list to sort
    const unsigned char** P = new const unsigned char*[N];
    for(size_t i=0; i<N; i++)
        P[i] = S + i;
    // dispatch worker threads
    const size_t part = (N/num_threads);
    thread_sort_t* params = new thread_sort_t[num_threads];
    pthread_t* threads = new pthread_t[num_threads];
    for(int i=0, start=0; i<num_threads; i++, start+=part) {
        params[i].S = S;
        params[i].P = P+start;
        params[i].N = (i==(num_threads-1))? N-start: part;
        pthread_create(threads+i,NULL,thread_sort,params+i);
    }
    // wait for the workers to finish sorting
    for(int i=0; i<num_threads; i++)
        pthread_join(threads[i],NULL);
    delete[] threads;
    delete[] params;
    // merge parts; this could be done in one pass but I'm lazy
    for(int i=1, start=part; i<num_threads; i++, start+=part) {
        const size_t stop = (i==(num_threads-1))? N: (start+part);
        std::inplace_merge(P,P+start,P+stop,stl_memcmp(S+N));
    }
    // create output
    I = -1;
    unsigned char* L = new unsigned char[N];
    for(size_t i=0; i<N; i++) {
        if(S == P[i]) {
            L[i] = P[i][N-1];
            I = i;
        } else {
            L[i] = P[i][-1];
        }
    }
    assert(0 <= I);
    delete[] P;
    return L;
}

int main(int argc,char** args) {
    if(4!=argc) {
        fprintf(stderr,"Usage: %s num_threads src dest\n",args[0]);
        return -1;
    }
    const int num_threads = atoi(args[1]);
    if(1>num_threads || 127<num_threads) {
        fprintf(stderr,"number of threads is crazy\n");
        return -1;
    }
    FILE* file = fopen(args[2],"r");
    if(!file) {
        fprintf(stderr,"could not open src \"%s\"\n",args[2]);
        return -1;
    }
    fseek(file,0,SEEK_END);
    const size_t N = ftell(file);
    fseek(file,0,SEEK_SET);
    unsigned char* S = new unsigned char[N+1];
    fread(S,1,N+1,file);
    S[N] = 0;
    fclose(file);
    int I;
    unsigned char* L = bwt_sort(S,N,I,num_threads);
    delete[] S;
    if(strcmp(".",args[3])) {
        file = fopen(args[3],"w");
        if(!file) {
            fprintf(stderr,"Could not open dest \"%s\"\n",args[3]);
            return -1;
        }
        fwrite(&N,sizeof(N),1,file);
        fwrite(&I,sizeof(I),1,file);
        fwrite(L,1,N,file);
        fclose(file);
    }
    delete[] L;
    return 0;
}

[zxcb]

4. last gcc openmp build produced different output, with
a couple of bytes moved, so there's likely a gcc or
openbwt bug

I've fixed it. Thanks Shelwien

URL:
http://cid-d435dc59d0b86781.skydrive...bwt-v1.5.1.zip

[zxcb]

OpenBWT-2.0.0 has been released.

Changes in 2.0.0:

• Added some new inverse BWT algorithms.
• Removed BWT-WT.
• Changed all function names to obwt_*().
• Updated sais with new version.
• Rewrote bwt.c and unbwt.c.

comparison of unbwt times (in seconds) for enwik9 on C2D 2.66 GHz

blksz (MiB)  basisPSI  basisLF    bw94
          1     43.42    40.71   44.38
          2     66.81    66.46   68.04
          4     84.49    84.87   84.67
          8     98.97    99.03  100.02
         16    108.58   108.86  109.25
         32    116.30   118.87  114.53
         64    128.94   131.16  126.85
        128    144.87   145.29  141.16
        256    166.36   167.80  167.55

blksz (MiB)   saPSI    saLF  mergedTPSI  mergedTL
          1   36.81   35.78       30.61     31.16
          2   56.56   55.59       50.84     52.25
          4   75.93   75.25       66.73     67.77
          8   94.61   93.56       78.17     79.52
         16  107.11  106.34       84.86     86.34
         32  116.24  115.44           -         -
         64  125.23  124.50           -         -
        128  134.38  133.59           -         -
        256  145.82  144.96           -         -

blksz (MiB)  indexPSIv1  indexPSIv2  indexLFv1  indexLFv2
          1       45.52       36.35      45.34      37.03
          2       64.24       53.75      64.76      54.79
          4       79.45       69.58      80.62      70.88
          8       90.58       81.03      91.70      82.62
         16       97.25       88.03      98.58      89.90
         32      102.82       93.89     104.34      95.48
         64      109.66      100.99     111.57     102.04
        128      117.40      108.77     118.85     109.69
        256      127.17      118.33     128.56     119.55

blksz (MiB)  unlimTPSI  unlimTLF  biPSIv1  biPSIv2
          1      30.89     31.09    61.23    45.38
          2      51.60     51.88    70.58    56.81
          4      67.55     68.13    78.40    64.73
          8      79.27     79.81    85.00    71.53
         16      86.26     87.09    88.52    75.36
         32     100.33     92.68    91.38    78.21
         64      99.58     99.62    94.85    81.74
        128     107.27    107.33    99.01    85.83
        256     117.05    117.19   105.71    90.76

blksz (MiB)      LL     LRI  LRI8v1  LRI8v2
          1   42.31  125.90   78.69   52.75
          2   58.01  148.38   97.43   65.60
          4   85.03  196.73  124.74   91.56
          8  102.11  254.62  149.72  113.15
         16  119.12  315.98  168.99  131.94
         32  136.30  387.99  185.46  147.44
         64  154.88  475.58  207.36  168.14
        128  174.54  562.38  239.65  196.92
        256  197.87  671.05  292.62  248.41

[biject.bwts]

Yuta you have done a very excellent job on BWT and BWTS I notice you
have added more routines for UNBWT. I was wondering why your new
version of the UNBWTS requires 5n extra memory making it 6n at best.

I have a slightly modified though likely slower version that is a mod
of your previous UNBWTS that makes it a 5n for large arrays in case
someone doing a large UNBWTS. I was wondering if you could include
a strict 5n version in your library as an alternative. Of course you
could change it to allocate the A array in the routine as that seems
to be the change you are now doing.

Thank You
David Scott

int
UnBWTS(const unsigned char *T, unsigned char *U, int *A, int n) {
int C[256];
int i, j, p, t;

/* allow T and U the same so 5n unbwts with lots of memory */
if((T == NULL) || (U == NULL) || (A == NULL) || (n < 0)) { return -1; }
if(n <= 1) { if(n == 1) { U[0] = T[0]; } return 0; }

for(i = 0; i < 256; ++i) { C[i] = 0; }
for(i = 0; i < n; ++i) { C[T[i]] += 1; }
for(i = 0, j = 1; i < 256; ++i) { t = C[i]; C[i] = j; j += t; }
for(i = 0; i < n; ++i) { A[i] = C[T[i]]++; }
/*
for(i = 0, j = n - 1; 0 <= j; ++i) {
if(0 <= A[i]) {
p = i;
do {
U[j--] = T[p];
t = A[p];
A[p] = -1;
p = t;
} while(0 <= A[p]);
}
}
*/

for(i = 0, j = n - 1; 0 <= j; ++i) {
if(0 < A[i]) {
p = i;
do {
t = A[p];
A[p] = -j--;
p = --t;
} while(0 < A[p]);
}
}

for(i = 0;i<n;++i){
if( 1 != A[i]){
j = - A[i];
t = T[j];
do{
p = T[-A[j]];
U[-A[j]]= t;
t = -A[j];
A[j] = 1;
j = t;
t = p;
} while( 1 != A[j]);
}
}

return 0;
}

[biject.bwts]

Yuta just sent me new code for UNBWTS it has several UNBWTS the last three are 5n here is a simple test I did on my machine.
good job Yuta




S:gcc -O3 -Wall unbwts_test.c

S:a e:enwik8
bwts : 115.1370 sec
obwt's : 19.2400 sec
indexLF : 17.1720 sec
unlimLF : 17.8800 sec
scott : 53.5160 sec

You can see for the simple case my mode to make it 5n runs slower
than his 5n versions indexLF unlimLF

[just a worm]

Is there a documentation on how the algorithms of Yuta Mori's (encode.su user name: zxcb) openBWT's detransformation of the Wheeler's transform work? So far I only got the source code.

Many thanks.

[biject.bwts]

The so called detransformation of the Wheeler's transform is self expalanatory by looking at the code. I don't think a write up would help.