2019-08-psc-optimal-construction-of-suffix-arrays-and-lcp-arrays

We propose an algorithm to compute the suffix array in linear time and in-place.
We also propose an algorithm to compute both the suffix array and LCP array in linear time and space.

PSC2019: http://www.stringology.org/event/2019/
arXiv: https://arxiv.org/abs/1703.01009

1. Optimal Time and Space Construction of Suffix Arrays and LCP Arrays for Integer Alphabets PSC 2019 Keisuke Goto Fujitsu Laboratories Ltd. 0
2. Suffix Arrays and LCP Arrays nSuffix arrays sort all suffixes and store their starting positions nLCP arrays store the length of longest common prefix of the consecutive suffixes in the suffix array i LCP SA TSA[i] 1 0 7 $ 2 0 6 a$ 3 1 4 ana$ 4 3 2 anana$ 5 0 1 banana$ 6 0 5 na$ 7 2 3 nana$ suffix array and LCP array of T 1 2 3 4 5 6 7 b a n a n a $ T 1
3. Problems T SA SA LCP Input Output Problem 1 Problem 2 2 Assumption l T is read-only string of length N l Word RAM mode of word size log N l T consists of an integer alphabet [1…σ] l all σ characters appear in T Example T = banana$ from {$←1, a←2, b←3, n←4} Stronger assumption than previous research
4. Our Contributions Time Extra Words [Manber and Mayers,1990] O(N log N) O(N) [Kim+, 2003], [Ko and Aluru, 2003], [Karkkainen Sanders, 2003] O(N) O(N) [Franceschini and Muthukrishnan, 2007] O(N log N) O(1) [Nong, 2013] O(N) σ + O(1) Ours O(N) O(1) Problem 1: Construction of SA Space except for input and output space 3
5. Recent and Independent Works 4 n[Li et al., 2018] also proposed an optimal time and space algorithm for Problem 1 (Construction of SA) [Li et al., 2018] Ours Alphabet size σ ∈ O(N) σ ≦ N All characters appear in T? May not Must Framework Induced sorting Induced sorting Main complex external tools In-place Merging for two sorted arrays [Chen 2003] Succinct data structures for select queries [Jacobson, 1989] In-place Merging for two sorted arrays [Chen 2003]
6. Recent and Independent Works 5 Our work may contribute to develop practical time and space efficient implementations for Problem 1 [Li et al., 2018] Ours Alphabet size σ ∈ O(N) σ ≦ N All characters appear in T? May not Must Framework Induced sorting Induced sorting Main complex external tools In-place Merging for two sorted arrays [Chen 2003] Succinct data structures for select queries [Jacobson, 1989] In-place Merging for two sorted arrays [Chen 2003]
7. Our Contributions Time Extra Words [Manber and Mayers,1990] O(N log N) O(N) [Kim+, 2003], [Ko and Aluru, 2003], [Karkkainen Sanders, 2003] O(N) O(N) [Franceschini and Muthukrishnan, 2007] O(N log N) O(1) [Nong, 2013] O(N) σ + O(1) Ours O(N) O(1) Time Extra Words [Kasai+, 2001] O(N) N + O(1) [Manzini, 2004] O(N) σ + O(1) [Nong, 2013] + [Manzini, 2004] O(N) σ + O(1) Input: T and SA Output: LCP Input: T Output: SA and LCP Problem 2: Construction of SA + LCP Problem 1: Construction of SA Ours O(N) O(1) Space except for input and output space 6 Focus on Problem 1 in this talk
8. nProblems nInduced Sorting Framework nOptimal Time and Space Algorithm nSummary 7
9. Induced Sorting Frameworks nSort suffixes from sorted suffixes of smaller size Suffixes L-suffixes S-suffixes LMS-suffixes sort sort • Make T’ such that SA of T’ equals SA of LMS-suffixes • Compute SA of T’ recursively of T’ We focus on this core part 8 [Ko and Aluru, 2003] [Nong et al., 2011]
10. Type of Suffixes nSuffix Ti (T[i..N]) is an L(arger)-suffix if Ti > Ti+1 nSuffix Ti (T[i..N]) is an S(maller)-suffix if Ti < Ti+1 1 2 3 4 5 6 7 b a a b b a $ L S S L L L S T a $ $ > aabba$ < abba$ type Left-most S-suffix (LMS-suffix) 9
11. Type of Suffixes nSuffix Ti (T[i..N]) is an L(arger)-suffix if Ti > Ti+1 nSuffix Ti (T[i..N]) is an S(maller)-suffix if Ti < Ti+1 TSA[i] $ a$ aabba$ abba$ ba$ baabba$ bba$ SAof T In each interval, L-suffixes must appear before S-suffixes $-interval a-interval b-interval L-suffix must appear after the succeeding suffix S-suffix must appear before the succeeding suffix 10
12. Sorting L-suffixes from sorted LMS-suffixes A TSA[i] $ $ a$ aabba$ aabba$ abba$ ba$ baabba$ bba$ 1 2 3 4 5 6 7 b a a b b a $ L S S L L L S T type LE a b Use three arrays pA: will be SA pLE: indicate the leftmost empty position of each interval ptype: store the type of each suffix Preliminary, we store sorted LMS-suffixes in the tail of each interval σ extra words N / log N extra words 11
13. Sorting L-suffixes from sorted LMS-suffixes A TSA[i] $ $ a$ aabba$ aabba$ abba$ ba$ baabba$ bba$ 1 2 3 4 5 6 7 b a a b b a $ L S S L L L S T type LE a b With a left-to-right scan on A pRead a suffix A[i]=Tj , lexicographically pJudge Tj-1 is L-suffix or not pIf so, we store Tj-1 at the leftmost empty position LE[tj-1 ] of tj-1 -interval tj-1 : Starting character of Tj-1 12
14. Sorting L-suffixes from sorted LMS-suffixes A TSA[i] $ $ a$ a$ aabba$ aabba$ abba$ ba$ baabba$ bba$ 1 2 3 4 5 6 7 b a a b b a $ L S S L L L S T type LE a b With a left-to-right scan on A pRead a suffix A[i]=Tj , lexicographically pJudge Tj-1 is L-suffix or not pIf so, we store Tj-1 at the leftmost empty position LE[tj-1 ] of tj-1 -interval tj-1 : Starting character of Tj-1 13
15. Sorting L-suffixes from sorted LMS-suffixes A TSA[i] $ $ a$ a$ aabba$ aabba$ abba$ ba$ baabba$ bba$ 1 2 3 4 5 6 7 b a a b b a $ L S S L L L S T type LE a b With a left-to-right scan on A pRead a suffix A[i]=Tj , lexicographically pJudge Tj-1 is L-suffix or not pIf so, we store Tj-1 at the leftmost empty position LE[tj-1 ] of tj-1 -interval tj-1 : Starting character of Tj-1 14
16. Sorting L-suffixes from sorted LMS-suffixes A TSA[i] $ $ a$ a$ aabba$ aabba$ abba$ ba$ ba$ baabba$ baabba$ bba$ bba$ 1 2 3 4 5 6 7 b a a b b a $ L S S L L L S T type LE a b With a left-to-right scan on A pRead a suffix A[i]=Tj , lexicographically pJudge Tj-1 is L-suffix or not pIf so, we store Tj-1 at the leftmost empty position LE[tj-1 ] of tj-1 -interval tj-1 : Starting character of Tj-1 15
17. Correctness A TSA[i] $ $ a$ a$ aabba$ aabba$ abba$ ba$ ba$ baabba$ baabba$ bba$ bba$ 1 2 3 4 5 6 7 b a a b b a $ L S S L L L S T type LE a b nWe don’t miss any L-suffixes nWe keep an invariant that suffixes in A are always sorted during the step Induced sorting framework runs in O(N) time and uses σ + N / log N extra words 16
18. nProblems nInduced Sorting Framework nOptimal Time and Space Algorithm nSummary 17
19. Observations nInduced sorting framework pGood: run in O(N) time pBad: use σ + N / log N extra words for LE and type I’d like to remove LE and type, but constructing SA without them seems TOO difficult I was thinking … 18
20. Observations One day, I came up with a good idea! Use only LE, BUT we store it in A, so we require no extra space LE type LE A Is it so easy? Of course not 19
21. Observations NOOO! some LE-values, which will be needed, are overwritten by induced suffixes LE type LE A suffixes 20
22. Observations LE type LE A Our algorithm store LE in A and overwrite LE-values only when they will be no longer used. It runs in O(N) time and uses O(1) extra words space! suffixes 21
23. Overview of Our Algorithm nWe use three internal sub-arrays in A nPreliminary, Y store LE-values and some LMS-suffixes nZ stores the other LMS-suffixes X Z A LE-values Y of length σ S-suffix 22
24. Overview of Our Algorithm nOur goal is to store sorted L-suffixes separatory in X and Y nFinally, we merge them A X Y Z X Z A LE-values A Sorted L-suffixes Y of length σ L-suffix S-suffix 23
25. Detail Layout of Suffixes X Z j i l j j i i k l m m j i k j k l m i-interval ・・・ ・・・ SA A X stores each interval by shifting one to left Y stores the largest L- suffix in each interval Y stores the smallest S-suffix in each interval if there is no L-suffix 24 Y i j k l m
26. Initial State X Z j i l m j i k A i j k l m 25 Y LE-values, which will be needed, are not overwritten
27. Step 1: Lexicographically Read L- and LMS-suffixes Tj pLeft-to-right scan on X, Y, and Z, respectively pCompare their starting characters and choose the smallest one in priority over X, Y, and Z X Z A 26
28. Step2: Judge Tj-1 is L-suffix or not 27 Key Property [Nong et al., 2011] For Tj-1 and Tj , if tj-1 = tj , the type of Tj-1 equals one of Tj 1 2 3 4 5 6 7 b a a b b a $ L S S L L L S T type
29. Step2: Judge Tj-1 is L-suffix or not nTj-1 is L-suffix only if pTj is read from X and tj-1 ≧ tj pOr, Tj is read from Z and tj-1 > tj pOr, Tj is read from Y and tj-1 > tj We know the type of Tj , so We know the type of Tj their starting characters must be different since Tj is the largest L- suffix or the smallest LMS-suffix 28
30. Step3: Store Tj-1 If It is L-suffix nWe try to store Tj-1 in X[LE[tj-1 ]] pIf X[LE[tj-1 ]] is EMPTY, then we store Tj-1 in X[LE[tj-1 ]] potherwise, X[LE[tj-1 ]] has a suffix then we compare their starting characters, and store the smallest one in Y and store the other in X[LE[tj-1 ]] LE-value for the smallest one is no longer used since it is the largest one in its interval 29
31. Correctness nOur algorithm simulates induced sorting framework without errors 30 A X Y Z X Z A Y of length σ Our algorithm runs in O(N) time and uses O(1) extra words space
32. Summary nProposed an algorithm for constructing SA in optimal time and space nProposed an algorithm for constructing both SA and LCP in optimal time and space (see our paper) Future work? nUsing some techniques or observations in this work, develop practical implementations 31