1 // Copyright 2011 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // This algorithm is based on "Faster Suffix Sorting"
6 // by N. Jesper Larsson and Kunihiko Sadakane
7 // paper: http://www.larsson.dogma.net/ssrev-tr.pdf
8 // code: http://www.larsson.dogma.net/qsufsort.c
10 // This algorithm computes the suffix array sa by computing its inverse.
11 // Consecutive groups of suffixes in sa are labeled as sorted groups or
12 // unsorted groups. For a given pass of the sorter, all suffixes are ordered
13 // up to their first h characters, and sa is h-ordered. Suffixes in their
14 // final positions and unambiguouly sorted in h-order are in a sorted group.
15 // Consecutive groups of suffixes with identical first h characters are an
16 // unsorted group. In each pass of the algorithm, unsorted groups are sorted
17 // according to the group number of their following suffix.
19 // In the implementation, if sa[i] is negative, it indicates that i is
20 // the first element of a sorted group of length -sa[i], and can be skipped.
21 // An unsorted group sa[i:k] is given the group number of the index of its
22 // last element, k-1. The group numbers are stored in the inverse slice (inv),
23 // and when all groups are sorted, this slice is the inverse suffix array.
29 func qsufsort(data []byte) []int {
30 // initial sorting by first byte of suffix
31 sa := sortedByFirstByte(data)
35 // initialize the group lookup table
36 // this becomes the inverse of the suffix array when all groups are sorted
37 inv := initGroups(sa, data)
39 // the index starts 1-ordered
40 sufSortable := &suffixSortable{sa, inv, 1}
42 for sa[0] > -len(sa) { // until all suffixes are one big sorted group
43 // The suffixes are h-ordered, make them 2*h-ordered
44 pi := 0 // pi is first position of first group
45 sl := 0 // sl is negated length of sorted groups
47 if s := sa[pi]; s < 0 { // if pi starts sorted group
48 pi -= s // skip over sorted group
49 sl += s // add negated length to sl
50 } else { // if pi starts unsorted group
52 sa[pi+sl] = sl // combine sorted groups before pi
55 pk := inv[s] + 1 // pk-1 is last position of unsorted group
56 sufSortable.sa = sa[pi:pk]
57 sort.Sort(sufSortable)
58 sufSortable.updateGroups(pi)
62 if sl != 0 { // if the array ends with a sorted group
63 sa[pi+sl] = sl // combine sorted groups at end of sa
66 sufSortable.h *= 2 // double sorted depth
69 for i := range sa { // reconstruct suffix array from inverse
76 func sortedByFirstByte(data []byte) []int {
79 for _, b := range data {
82 // make count[b] equal index of first occurence of b in sorted array
84 for b := range count {
85 count[b], sum = sum, count[b]+sum
87 // iterate through bytes, placing index into the correct spot in sa
88 sa := make([]int, len(data))
89 for i, b := range data {
97 func initGroups(sa []int, data []byte) []int {
98 // label contiguous same-letter groups with the same group number
99 inv := make([]int, len(data))
100 prevGroup := len(sa) - 1
101 groupByte := data[sa[prevGroup]]
102 for i := len(sa) - 1; i >= 0; i-- {
103 if b := data[sa[i]]; b < groupByte {
104 if prevGroup == i+1 {
110 inv[sa[i]] = prevGroup
115 // Separate out the final suffix to the start of its group.
116 // This is necessary to ensure the suffix "a" is before "aba"
117 // when using a potentially unstable sort.
118 lastByte := data[len(data)-1]
122 if data[sa[i]] == lastByte && s == -1 {
125 if sa[i] == len(sa)-1 {
126 sa[i], sa[s] = sa[s], sa[i]
128 sa[s] = -1 // mark it as an isolated sorted group
137 type suffixSortable struct {
143 func (x *suffixSortable) Len() int { return len(x.sa) }
144 func (x *suffixSortable) Less(i, j int) bool { return x.inv[x.sa[i]+x.h] < x.inv[x.sa[j]+x.h] }
145 func (x *suffixSortable) Swap(i, j int) { x.sa[i], x.sa[j] = x.sa[j], x.sa[i] }
148 func (x *suffixSortable) updateGroups(offset int) {
149 bounds := make([]int, 0, 4)
150 group := x.inv[x.sa[0]+x.h]
151 for i := 1; i < len(x.sa); i++ {
152 if g := x.inv[x.sa[i]+x.h]; g > group {
153 bounds = append(bounds, i)
157 bounds = append(bounds, len(x.sa))
159 // update the group numberings after all new groups are determined
161 for _, b := range bounds {
162 for i := prev; i < b; i++ {
163 x.inv[x.sa[i]] = offset + b - 1