Results 1 to 4 of 4

Thread: Test SA-IC creation suffix array algorithm

  1. #1
    Member
    Join Date
    Jun 2019
    Location
    Poland
    Posts
    24
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Test SA-IC creation suffix array algorithm

    https://gitlab.com/compress-data/sa-is

    can be seen inversely proportional efficency when cicles exists.Naive takes long tiome when long cycles, but algorithm SA-IS especially.

    Next, I want do similar test of Karkkainen-Sanders, but I think it is slower than SA-IS

  2. #2
    Member
    Join Date
    Dec 2012
    Location
    japan
    Posts
    163
    Thanks
    31
    Thanked 64 Times in 40 Posts
    Do you know openbwt?

  3. #3
    Member
    Join Date
    Jun 2019
    Location
    Poland
    Posts
    24
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Sa-Is is not quite linear. I tested for 150 kB block and was above 4x better than naive, but for large block like 10 MB was only 1.1 x better. Method Karkkainen-Sanders was above 2x worse on large blocks. Worse cooperation with processor cache?

  4. #4
    Member
    Join Date
    Mar 2013
    Location
    Worldwide
    Posts
    565
    Thanks
    67
    Thanked 199 Times in 147 Posts
    The best and widely used SA construction library for CPUs is libdivsufsort. 2 times faster than SAIS (incl. in openbwt) from the same author.
    You might also have a look at: msufsort parallel suffix array construction algorithm & msufsort 4 update

Similar Threads

  1. Better quality image resize for corpus creation
    By khavish in forum Data Compression
    Replies: 0
    Last Post: 28th October 2017, 21:53
  2. An Elegant Algorithm for the Construction of Suffix Arrays
    By willvarfar in forum Data Compression
    Replies: 18
    Last Post: 11th July 2013, 16:01
  3. Compression of array of chars
    By garriks in forum Data Compression
    Replies: 2
    Last Post: 19th May 2012, 01:30
  4. Suffix Trees, Suffix Arrays, or What?
    By incblitz in forum Data Compression
    Replies: 47
    Last Post: 12th July 2011, 21:54
  5. Creation of RAR-files...?
    By Vacon in forum Forum Archive
    Replies: 3
    Last Post: 11th October 2007, 02:19

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
  •