MY question is about storage complexity of a suffix array. According to textbooks it is O(n) with an exact cost that approximates 4n. However a suffix array of a string of length n is an n-size integer array, along an index that maps each substring to the appropriate position of the array. This index has size $1+2+..+n= O(n^2)$. So why the storage cost it is said to be $O(n)$ at the textbooks?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ This is explained very well in the Wikipedia article, en.wikipedia.org/wiki/Suffix_array. $\endgroup$– Yuval FilmusFeb 24, 2016 at 22:11
-
$\begingroup$ I still can't see how you search for a substring as long as you do not store the substring itself but only its position $\endgroup$– curiousFeb 24, 2016 at 22:14
-
$\begingroup$ That's a different question. There is an algorithm for doing that, described in your textbook. $\endgroup$– Yuval FilmusFeb 24, 2016 at 22:15
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
You don't store the actual suffixes in the array. You only store indices, $n$ of them. Each index takes $O(1)$ space in the RAM model (which is what the textbook is using to count space), so in total the space consumption is $O(n)$. The number of bits used is $\Theta(n\log n)$.
answered Feb 24, 2016 at 22:14
-
$\begingroup$ The question is for the total cost. So i agree there is a need of O(n) for the storage cost of the SA. But there is a need to store the corresponding suffixes isn't it? Not in that array, but the SA itself without the substrings is useless. $\endgroup$– curiousFeb 24, 2016 at 22:17
-
$\begingroup$ No, you never store the suffixes explicitly. That's the point of this data structure – everything is stored implicitly. You use the data structure in conjunction with the original string. $\endgroup$ Feb 24, 2016 at 22:19
-
$\begingroup$ I can't really get it.Let's say we have a suffix array, ordered by the suffixes, which contains each suffix position. I want to look for some pattern p.How do i perform binary search based on p, if the algorithm does not keep track of each suffix and its position. Or it only keeps track of the starting point of the suffix as an index to its position on the original string and then it traverses the original one to find the end point of the possible match? That way you need the original string right? $\endgroup$– curiousFeb 24, 2016 at 23:18
-
$\begingroup$ Your textbook contains all the answers. Unfortunately I'm not an expert so I cannot help you any further. $\endgroup$ Feb 24, 2016 at 23:22
$\begingroup$
$\endgroup$
2
You store only the position of suffixes in the index, not the suffixes themselves.
So the storage complexity is O(n) for the index. You then have to keep the original string along with the suffixes array. The original string storage complexity is O(n) also by definition.
The whole storage complexity remains O(n).
-
$\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post - you can always comment on your own posts, and once you have sufficient reputation you will be able to comment on any post. - From Review $\endgroup$– codyFeb 26, 2016 at 20:59
-
$\begingroup$ @cody I edited my answer in order to comply, thanks. $\endgroup$– ManuelFeb 26, 2016 at 23:04