Native Julia suffix array implementation; Derived from sais
12 Stars
Updated Last
2 Years Ago
Started In
August 2014


Build Status

A Julia package for computing Suffix Arrays. The underlying suffix array sorting implementation is a pure Julia port of sais, by Yuta Mori.

You can use the package by running:

julia> using SuffixArrays

julia> s = "banana"

julia> sa = suffixsort(s)
6-element Array{UInt8,1}:

julia> [s[i:end] for i in sa]
6-element Array{String,1}:

julia> issorted(ans)

The suffixsort function can compute a suffix array for vectors of UInt8 or UInt16 values, or for strings with code units that are one of these two types. When generating a suffix array for a string, the suffix indices are in terms of code units, not characters, which means that some indices will be into the middle of characters that span multiple code units. For UTF-8 and UTF-16 this doesn't affect using the suffix array as search index since a valid substring cannot start in the middle of a character anyway. In other words, invalid substrings occuring in the suffix array will simply not match.

By default, suffixsort(v) produces an array of 1-based indices, but it can be called as suffixsort(v, 0) in order to produce an array of 0-based indices, which may be desirable to interface with 0-based libraries (or to save a tiny bit of space).

Required Packages

No packages found.

Used By Packages