Results 1 to 5 of 5

Thread: Computing the BWTS faster

  1. #1
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 71 Times in 55 Posts

    Computing the BWTS faster

    I've been sitting on this for a little while, and talked about it with David Scott, and I figure now is as good a time as any to share.

    This computes the BWTS using a new approach. Unlike the original implementation and the one in openbwt, it suffix sorts the input as a whole and then corrects the order to produce the BWTS. It's not clear to me whether it's fundamentally a better approach than merging, or if it's just simpler and benefits from the optimization that's gone into divsufsort. But it seems to get the BWTS quite a bit faster, and gets the same result as openbwt on all the data I've thrown at it.

    Please let me know if you find a bug.
    Attached Files Attached Files

  2. The Following 4 Users Say Thank You to nburns For This Useful Post:

    biject.bwts (29th June 2013),Matt Mahoney (9th July 2013),Nania Francesco (9th July 2013),willvarfar (9th July 2013)

  3. #2
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 71 Times in 55 Posts

    Google code project

    This now has a Google Code project: http://code.google.com/p/mk-bwts/

  4. The Following User Says Thank You to nburns For This Useful Post:

    Bulat Ziganshin (8th July 2013)

  5. #3
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    I ran a quick test on the simple benchmark similar to http://encode.ru/threads/1744-An-Ele...ll=1#post33777
    All files produced output of identical size. I did not test the inverse BWTS to see if it was identical.

    Of the 1 MB files, the slowest were l6002 and m6002, which are ascending lists of 16 bit integers in LSB first or MSB first format. These were 0.43 seconds. All others were under 0.27 sec. The file w8002 (2 copies of a 50 MB random string) took 52 sec. and 600 MB memory.

  6. The Following User Says Thank You to Matt Mahoney For This Useful Post:

    nburns (9th July 2013)

  7. #4
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 71 Times in 55 Posts
    The steps that dominate the performance are, in descending order: the suffix sort, computing the inverse suffix array, permuting the text by the new order, and computing the new order. Computing the new order takes about 1-6% of the total time. I have an update that improves the performance of computing the order on some inputs, which I'll put on google code once it's fully tested. However, unless there's a dataset that triggers massively pathological behavior, the difference will be small.

    The data that's allocated are the suffix array (4N), the inverse suffix array (4N), and the output array (N). The input is memory mapped for speed. I was originally computing and writing the output on the fly, but it turned out to be faster to generate it out of order and buffer it before writing. The SA gets freed before the output buffer is allocated, so the max allocated at a single time is 8N bytes.

    Any significant improvement in speed/memory will have to come from doing something about the inverse suffix array, which will not be easy to get rid of.

  8. #5
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 71 Times in 55 Posts
    I updated the google code repository with the sorting improvements. I tested it on ~20k files.

Similar Threads

  1. GPGPU computing
    By Bulat Ziganshin in forum The Off-Topic Lounge
    Replies: 0
    Last Post: 19th February 2012, 17:10
  2. Replies: 1
    Last Post: 21st June 2011, 11:48
  3. GCC 4.6 faster than previous GCC, faster than LLVM
    By willvarfar in forum The Off-Topic Lounge
    Replies: 2
    Last Post: 15th November 2010, 16:09
  4. BWTS explanation?
    By TopQuark in forum Data Compression
    Replies: 5
    Last Post: 8th April 2009, 22:26
  5. Faster PAQ7/8
    By LovePimple in forum Forum Archive
    Replies: 6
    Last Post: 8th February 2007, 14:04

Posting Permissions

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