(data structure)
Definition: For each position in a string, the inverse suffix array has its index in the string's suffix array.
Formal Definition: Given a suffix array, sa, and the corresponding inverse suffix array, isa, isa[i] = j iff sa[j] = i.
Generalization (I am a kind of ...)
array.
See also suffix array.
Note: Consider the string "good". In one-based indexing, the suffix array is [4, 1, 3, 2]. The inverse suffix array is [2, 4, 3, 1].
Many algorithms to build suffix arrays use an inverse suffix array. A suffix array can be built from the inverse suffix array in linear time. An inverse suffix array can be turned into a suffix array in place in linear time, too.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 7 December 2007.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "inverse suffix array", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 7 December 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/inverseSuffixArray.html
