solve's blog

Suffix Sorting in nlog(n)
By solve, 12 years ago, In English

Hi All,Could somebody explain me what is idea behind suffix sorting in context of suffix array.

i know usual sorting algorithm,but what actually is idea behind mayer and mayber algorithm?

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

DC3 is faster!!!

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you know about number sort? Theory, it's O(n).

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think this file would be useful :

http://www.stanford.edu/class/cs97si/suffix-array.pdf

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks MMJ :)

    This pdf says "The algorithm is mainly based on maintaining the order of the string’s suffixes sorted by their 2k long prefixes".

    could you explain me how actually this idea works?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 3   Vote: I like it -8 Vote: I do not like it

      I have recently learned this algorithm, so excuse me for my poor explanation.(and my poor English :D)

      consider we have a string S and we want to sort all suffix of S in O(nlgn * lgn).

      first of all we add some extra character to the end of S that they're maximum character in our alphabet.

      then for every j (1 <= 2^j < 2^k) such that 2^k is first power of 2 that's larger than size of S and every i (0<= i < size of S), we will sort all substring of S that starts from i and they're length is equal 2^j in O(nlgn).

      consider (i, j) a substring of S that starts from i and it's length is equal 2^j

      in each step(for every j) we spot a number from 0 to n-1 for every substring (i, j), that it's position in all substrings (i, j). we call this number D[i][j]

      we can calculate D[i][j+1] in this way :

      1 . for every i : D[i][j + 1] = (D[i][j] * n) + D[i + 2^j][j]

      2 . sort all D[i][j + 1], and then change value's to numbers from 0 to n-1 (as explained above).

      the total complexity is equal O(nlgn * lgn).

      I know there's a O(nlgn) algorithm but I have no idea for that one :D

      → Reply