Page 2 of 2 FirstFirst 12
Results 31 to 52 of 52

Thread: libBWT

  1. #31
    Member biject.bwts's Avatar
    Join Date
    Jun 2008
    Location
    texas
    Posts
    449
    Thanks
    23
    Thanked 14 Times in 10 Posts
    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
    Last edited by biject.bwts; 13th June 2013 at 00:18. Reason: to state it works as real BWTS

  2. #32
    Member
    Join Date
    May 2008
    Location
    Antwerp , country:Belgium , W.Europe
    Posts
    487
    Thanks
    1
    Thanked 3 Times in 3 Posts
    Quote Originally Posted by biject.bwts View Post
    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.

  3. #33
    Member biject.bwts's Avatar
    Join Date
    Jun 2008
    Location
    texas
    Posts
    449
    Thanks
    23
    Thanked 14 Times in 10 Posts
    Quote Originally Posted by pat357 View Post
    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,

  4. #34
    Member biject.bwts's Avatar
    Join Date
    Jun 2008
    Location
    texas
    Posts
    449
    Thanks
    23
    Thanked 14 Times in 10 Posts

    libbwt

    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
    Last edited by biject.bwts; 13th June 2013 at 00:20. Reason: OLD STUFF YUTA'S CODE WORKS

  5. #35
    Member biject.bwts's Avatar
    Join Date
    Jun 2008
    Location
    texas
    Posts
    449
    Thanks
    23
    Thanked 14 Times in 10 Posts

    libBWT works

    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.

  6. #36
    Member biject.bwts's Avatar
    Join Date
    Jun 2008
    Location
    texas
    Posts
    449
    Thanks
    23
    Thanked 14 Times in 10 Posts

    Thumbs up OpenBWT-v1.4 has been released

    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

  7. #37
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,531
    Thanks
    755
    Thanked 674 Times in 365 Posts
    thanks, it looks very interesting:
    Code:
    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

  8. #38
    Programmer
    Join Date
    Jun 2008
    Location
    Japan
    Posts
    14
    Thanks
    0
    Thanked 2 Times in 2 Posts

    OpenBWT-v1.5

    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.
    Attached Files Attached Files

  9. #39
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,478
    Thanks
    26
    Thanked 122 Times in 96 Posts
    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?

  10. #40
    Programmer
    Join Date
    Jun 2008
    Location
    Japan
    Posts
    14
    Thanks
    0
    Thanked 2 Times in 2 Posts
    Quote Originally Posted by Piotr Tarsa View Post
    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:
    Attached Files Attached Files

  11. #41
    Member biject.bwts's Avatar
    Join Date
    Jun 2008
    Location
    texas
    Posts
    449
    Thanks
    23
    Thanked 14 Times in 10 Posts

    openbwt-v1.4

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

  12. #42
    Member Yuri Grille.'s Avatar
    Join Date
    Mar 2009
    Location
    ****
    Posts
    35
    Thanks
    0
    Thanked 1 Time in 1 Post

    zxcb you work is incredible !!

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

    Yuri

  13. #43
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,478
    Thanks
    26
    Thanked 122 Times in 96 Posts
    Quote Originally Posted by zxcb View Post
    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?

  14. #44
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,687
    Thanks
    264
    Thanked 1,180 Times in 651 Posts
    <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

  15. #45
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,687
    Thanks
    264
    Thanked 1,180 Times in 651 Posts
    Code:
    <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

  16. #46
    Member
    Join Date
    Feb 2010
    Location
    Nordic
    Posts
    200
    Thanks
    41
    Thanked 36 Times in 12 Posts

    parallel sorting can't be done naively

    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):

    Code:
    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:

    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;
    }

  17. #47
    Programmer
    Join Date
    Jun 2008
    Location
    Japan
    Posts
    14
    Thanks
    0
    Thanked 2 Times in 2 Posts
    Quote Originally Posted by Shelwien View Post
    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

  18. #48
    Programmer
    Join Date
    Jun 2008
    Location
    Japan
    Posts
    14
    Thanks
    0
    Thanked 2 Times in 2 Posts

    OpenBWT-2.0.0

    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.


    Code:
    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
    Attached Files Attached Files

  19. #49
    Member biject.bwts's Avatar
    Join Date
    Jun 2008
    Location
    texas
    Posts
    449
    Thanks
    23
    Thanked 14 Times in 10 Posts

    Question

    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;
    }

  20. #50
    Member biject.bwts's Avatar
    Join Date
    Jun 2008
    Location
    texas
    Posts
    449
    Thanks
    23
    Thanked 14 Times in 10 Posts
    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
    Attached Files Attached Files

  21. #51
    Member just a worm's Avatar
    Join Date
    Aug 2013
    Location
    planet "earth"
    Posts
    96
    Thanks
    29
    Thanked 6 Times in 5 Posts
    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.

  22. #52
    Member biject.bwts's Avatar
    Join Date
    Jun 2008
    Location
    texas
    Posts
    449
    Thanks
    23
    Thanked 14 Times in 10 Posts
    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.

Page 2 of 2 FirstFirst 12

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •