Lines Matching refs:sa
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
13 // up to their first h characters, and sa is h-ordered. Suffixes in their
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
31 sa := sortedByFirstByte(data)
32 if len(sa) < 2 {
33 return sa
37 inv := initGroups(sa, data)
40 sufSortable := &suffixSortable{sa: sa, inv: inv, h: 1}
42 for sa[0] > -len(sa) { // until all suffixes are one big sorted group
46 for pi < len(sa) {
47 if s := sa[pi]; s < 0 { // if pi starts sorted group
52 sa[pi+sl] = sl // combine sorted groups before pi
56 sufSortable.sa = sa[pi:pk]
63 sa[pi+sl] = sl // combine sorted groups at end of sa
69 for i := range sa { // reconstruct suffix array from inverse
70 sa[inv[i]] = i
72 return sa
86 // iterate through bytes, placing index into the correct spot in sa
87 sa := make([]int, len(data))
89 sa[count[b]] = i
92 return sa
95 func initGroups(sa []int, data []byte) []int {
98 prevGroup := len(sa) - 1
99 groupByte := data[sa[prevGroup]]
100 for i := len(sa) - 1; i >= 0; i-- {
101 if b := data[sa[i]]; b < groupByte {
103 sa[i+1] = -1
108 inv[sa[i]] = prevGroup
110 sa[0] = -1
118 for i := range sa {
119 if sa[i] >= 0 {
120 if data[sa[i]] == lastByte && s == -1 {
123 if sa[i] == len(sa)-1 {
124 sa[i], sa[s] = sa[s], sa[i]
125 inv[sa[s]] = s
126 sa[s] = -1 // mark it as an isolated sorted group
135 sa []int
141 func (x *suffixSortable) Len() int { return len(x.sa) }
142 func (x *suffixSortable) Less(i, j int) bool { return x.inv[x.sa[i]+x.h] < x.inv[x.sa[j]+x.h] }
143 func (x *suffixSortable) Swap(i, j int) { x.sa[i], x.sa[j] = x.sa[j], x.sa[i] }
147 group := x.inv[x.sa[0]+x.h]
148 for i := 1; i < len(x.sa); i++ {
149 if g := x.inv[x.sa[i]+x.h]; g > group {
154 bounds = append(bounds, len(x.sa))
161 x.inv[x.sa[i]] = offset + b - 1
164 x.sa[prev] = -1
