Page 1 of 2 12 LastLast
Results 1 to 30 of 52

Thread: libBWT

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

    libBWT

    Hello,

    libBWT is a very simple library for Burrows-Wheeler Transformation. This BWT works very fast in the file of various types!

    Changes in 1.1.0:
    * Added BWT.def, BWT.exp and BWT.lib for some compilers.
    * Added a space-efficient inverse BWT and the sample code. (It requires only 3.63n bytes of memory space, including input text)


    Code:
    Timing results (Core 2 Duo 2.66GHz, 1Gb memory)
                   qsort     ST2  libBWT
    A10.jpg        0.252   0.002   0.040
    acrord32.exe   5.172   0.032   0.264
    english.dic    1.770   0.024   0.292
    FlashMX.pdf    1.800   0.062   0.380
    fp.log        23.916   0.190   2.682
    mso97.dll      1.568   0.040   0.290
    ohs.doc       59.452   0.034   0.320
    rafale.bmp     1.982   0.030   0.268
    vcfiu.hlp      3.422   0.030   0.276
    world95.txt    1.578   0.022   0.248

    This package contains the include file, libraries and sample codes.
    http://www.geocities.com/zxcb33/libBWT-1.1.0.zip
    Attached Files Attached Files

  2. The Following User Says Thank You to zxcb For This Useful Post:

    encode (27th February 2015)

  3. #2
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Thanks a lot!

  4. #3
    Member
    Join Date
    Oct 2007
    Location
    Germany, Hamburg
    Posts
    408
    Thanks
    0
    Thanked 5 Times in 5 Posts
    I tested the statically linked bwt program with enwik8 and got almost the same size (above 100mb)

  5. #4
    Member
    Join Date
    May 2008
    Location
    Earth
    Posts
    115
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Lightbulb

    Quote Originally Posted by Simon Berger View Post
    I tested the statically linked bwt program with enwik8 and got almost the same size (above 100mb)
    BWT itself doesn't compress the data.

  6. #5
    Member
    Join Date
    Oct 2007
    Location
    Germany, Hamburg
    Posts
    408
    Thanks
    0
    Thanked 5 Times in 5 Posts

    Ah ok so all other programs using this technique uses another algorithm

  7. #6
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Quote Originally Posted by Simon Berger View Post

    Ah ok so all other programs using this technique uses another algorithm
    If you'll test BCM or other BWT-based compressor, you may see something like:
    sorting...
    encoding...

    i.e. Firstly, we do block sorting, and only after, we do actual compression of transformed data...

  8. #7
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Thumbs up

    Thanks zxcb!

  9. #8
    Programmer
    Join Date
    Jul 2008
    Location
    Finland
    Posts
    102
    Thanks
    0
    Thanked 1 Time in 1 Post
    Hi zxcb,

    Is this your original algorithm and/or implementation? If not, which library is it using?

  10. #9
    Programmer
    Join Date
    Jun 2008
    Location
    Japan
    Posts
    14
    Thanks
    0
    Thanked 2 Times in 2 Posts
    Quote Originally Posted by Sami View Post
    Hi zxcb,

    Is this your original algorithm and/or implementation? If not, which library is it using?

    Hello Sami,

    libBWT uses my original suffix-sorting algorithm.

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

    OpenBWT - v1.0

    Hi,

    I wrote an open source version of BWT, called OpenBWT. It runs in O(n) worst-case time and 2n worst-case extra space.

    This package is released under the MIT license.
    Attached Files Attached Files

  12. The Following User Says Thank You to zxcb For This Useful Post:

    encode (11th May 2019)

  13. #11
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Thank you!

  14. #12
    Programmer michael maniscalco's Avatar
    Join Date
    Apr 2007
    Location
    Boston, Massachusetts, USA
    Posts
    109
    Thanks
    7
    Thanked 80 Times in 25 Posts
    Quote Originally Posted by zxcb View Post
    Hi,

    I wrote an open source version of BWT, called OpenBWT. It runs in O(n) worst-case time and 2n worst-case extra space.

    This package is released under the MIT license.

    Unless I missed it, you really should acknowledge in these files that this is largely (if not entirely) Yuta Mori's code. Unless, that is, zxcb = Yuta.

    [update]

    Sorry, it appears that even Yuta might have taken the code from the original paper. Are you the original author of the paper?

    - Michael Maniscalco
    Last edited by michael maniscalco; 15th July 2008 at 18:32.

  15. #13
    Programmer
    Join Date
    Jun 2008
    Location
    Japan
    Posts
    14
    Thanks
    0
    Thanked 2 Times in 2 Posts
    Hi Michael,

    Quote Originally Posted by michael maniscalco View Post
    Unless I missed it, you really should acknowledge in these files that this is largely (if not entirely) Yuta Mori's code. Unless, that is, zxcb = Yuta.

    [update]

    Sorry, it appears that even Yuta might have taken the code from ぶり the original paper. Are you the original author of the paper?

    - Michael Maniscalco
    I'm Yuta.

  16. #14
    Member
    Join Date
    Jan 2007
    Location
    Moscow
    Posts
    239
    Thanks
    0
    Thanked 3 Times in 1 Post
    HEHE... LOL!

  17. #15
    Member
    Join Date
    May 2008
    Location
    Antwerp , country:Belgium , W.Europe
    Posts
    487
    Thanks
    1
    Thanked 3 Times in 3 Posts
    and original author from the paper = Yuta ?

  18. #16
    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 zxcb View Post
    Hi,
    I wrote an open source version of BWT, called OpenBWT. It runs in O(n) worst-case time and 2n worst-case extra space. .
    I did a quick test : it seems that this BWT algorithm is slower then yours from LIBBWT110.
    I haven't looked in the code, but what are the differences between this one and LIBBWT v1.10 ?

  19. #17
    Programmer
    Join Date
    Jun 2008
    Location
    Japan
    Posts
    14
    Thanks
    0
    Thanked 2 Times in 2 Posts
    Quote Originally Posted by pat357 View Post
    I did a quick test : it seems that this BWT algorithm is slower then yours from LIBBWT110.
    I haven't looked in the code, but what are the differences between this one and LIBBWT v1.10 ?
    OpenBWT uses a different algorithm for suffix-sorting. libBWT's worst-case time is O(n log n).

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

    OpenBWT-v1.1

    OpenBWT-v1.1 has been released.

    Changes in v1.1:
    • Added the following second stage transforms.
      • Move To Front
      • Move One From Front
      • Move One From Front 2
      • Sorted Inversion Frequencies
      • Distance Coding
      • Sorted Distance Coding
      • Sorted Rank Coding


    http://www.geocities.com/zxcb33/openbwt-v1.1.zip
    Attached Files Attached Files

  21. #19
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Thanks a lot!

  22. #20
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Thumbs up

    Thanks zxcb!

  23. #21
    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 zxcb View Post
    OpenBWT-v1.1 has been released.

    Changes in v1.1:
    • Added the following second stage transforms.
      • Move To Front
      • Move One From Front
      • Move One From Front 2
      • Sorted Inversion Frequencies
      • Distance Coding
      • Sorted Distance Coding
      • Sorted Rank Coding
    Very nice! Thanks a lot !
    What a piity there are no compiled bin's included
    If someone is compiling this, I'd be very interested !

    @encode :
    Maybe there some ideas included here to improve BCM ?
    Anyway, I would be very happy with a compiled version (Win).

  24. #22
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    Compiled the samples.
    Attached Files Attached Files

  25. #23
    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 Shelwien View Post
    Compiled the samples.
    Thanks a lot !!

  26. #24
    Programmer
    Join Date
    Jul 2008
    Location
    Finland
    Posts
    102
    Thanks
    0
    Thanked 1 Time in 1 Post
    Has anybody got any results for dc vs sorted dc? If so please post.

    I planned sorted dc tests long time ago. I never did finish the implementation. I intended simply to write the distances for each symbol in separate pass (perhaps sorted by freq or something else), is this the same idea as here?

    I suspected it would not be good since it's more difficult to model things and it must be inefficient since with the first (or several depending what is our order) symbol, there is nothing but integers to encode blindly (the same is with IF, although there don't need to encode the last symbol).

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

    OpenBWT-v1.2

    OpenBWT-v1.2 has been released.

    Changes in v1.2:
    • Added the following second stage transforms.
      • Transpose
      • Best x of 2x - 1
      • TimeStamp(0)
      • Sort-By-Rank(0.5)
      • Frequency Count
      • Weighted Frequency Count
      • Advanced Weighted Frequency Count
      • Incremental Frequency Count
    • Improved SIF encoding/decoding speed.

    http://www.geocities.com/zxcb33/openbwt-v1.2.zip
    Attached Files Attached Files

  28. #26
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Thumbs up

    Thanks zxcb!

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

    alternate BWT

    I was wondering any thoughts of having your lib support the bijective version of BWT.

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

    OpenBWT-v1.3

    OpenBWT-v1.3 has been released.

    Changes in v1.3:

    • Added Burrows-Wheeler Transform Scottifed. (BWTS)


    http://www.geocities.com/zxcb33/openbwt-v1.3.zip
    Attached Files Attached Files

  31. #29
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Thumbs up

    Thanks zxcb!

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

    Thumbs up The Added Burrows-Wheeler Transform Scottifed. (BWTS)

    Quote Originally Posted by zxcb View Post
    OpenBWT-v1.3 has been released.

    Changes in v1.3:

    • Added Burrows-Wheeler Transform Scottifed. (BWTS)


    http://www.geocities.com/zxcb33/openbwt-v1.3.zip
    Great I am slow it took me years to get the output to what I wanted. I know the code that I left is slow but I just wanted it done. My mind is much faster I have on paper several versions for improvements but the core is the one I wrote about. I will try in the next few weeks to take a good look at what you did I hope it works with DJPP GNU C
    Take Care
    David A. Scott

Page 1 of 2 12 LastLast

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
  •