Results 1 to 3 of 3

Thread: efficient bitwise BWT ?

  1. #1
    Member
    Join Date
    Feb 2020
    Location
    Earth
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question efficient bitwise BWT ?

    The talks about bitwise BWT on this forum started in 2010.
    The output of bitwise BWT looks interesting because you would
    only need to encode lengths of runs, ok?
    In bitwise case it's possible to transform input as big as 512 MiB using the conventional
    5*N bytes of memory, where N is the size of input in bytes,
    is it possible to complete the regular bytewise BWT and then transform quickly to the output of bitwise BWT?

  2. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,716
    Thanks
    271
    Thanked 1,185 Times in 656 Posts
    > The output of bitwise BWT looks interesting because you would
    > only need to encode lengths of runs, ok?

    Actually no. I mean, its possible, but result of simple bitwise RLE won't be better than
    bytewise BWT + MTF + RLE.

    > In bitwise case it's possible to transform input as big as 512 MiB using the conventional
    > 5*N bytes of memory, where N is the size of input in bytes,

    No, if its true BWT, you'd need a pointer per symbol (ie bit).
    So 40*N memory until 512Mb (since after than bit pointers won't fit in 32 bits).
    Well, 33*N if we'd work with packed bits, but that'd be slower.

    > is it possible to complete the regular bytewise BWT and
    > then transform quickly to the output of bitwise BWT?

    Its possible to compute bytewise BWT of 8 bit-shifts of the block,
    then merge these.

    I actually have a project where bitwise BWT is used:
    https://encode.su/threads/2742-Compr...ll=1#post52493
    You can also find standalone utilities for bitwise BWT (and BWTS) there.

  3. #3
    Programmer michael maniscalco's Avatar
    Join Date
    Apr 2007
    Location
    Boston, Massachusetts, USA
    Posts
    139
    Thanks
    20
    Thanked 94 Times in 31 Posts
    Bitwise bwt, in theory, would be incedible fast. Only the increased memory is an issue. As for RLE, binary m99 is much better compression. See https://encode.su/threads/3103-exper...th-prediction:

Similar Threads

  1. Efficient deflate implementations
    By Bulat Ziganshin in forum Data Compression
    Replies: 10
    Last Post: 28th March 2019, 00:25
  2. Replies: 0
    Last Post: 17th October 2018, 01:42
  3. Replies: 41
    Last Post: 24th July 2017, 20:05
  4. Demixer - new tree-based bitwise CM codec is in development
    By Piotr Tarsa in forum Data Compression
    Replies: 34
    Last Post: 17th March 2013, 21:33
  5. New data structure for bitwise CM
    By Shelwien in forum Data Compression
    Replies: 5
    Last Post: 27th November 2010, 17:35

Posting Permissions

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