Source file src/pkg/index/suffixarray/qsufsort.go
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. 4 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 9 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 unambiguously 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. 18 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. 24 25 package suffixarray 26 27 import "sort" 28 29 func qsufsort(data []byte) []int { 30 // initial sorting by first byte of suffix 31 sa := sortedByFirstByte(data) 32 if len(sa) < 2 { 33 return sa 34 } 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) 38 39 // the index starts 1-ordered 40 sufSortable := &suffixSortable{sa: sa, inv: inv, h: 1} 41 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 46 for pi < len(sa) { 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 51 if sl != 0 { 52 sa[pi+sl] = sl // combine sorted groups before pi 53 sl = 0 54 } 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) 59 pi = pk // next group 60 } 61 } 62 if sl != 0 { // if the array ends with a sorted group 63 sa[pi+sl] = sl // combine sorted groups at end of sa 64 } 65 66 sufSortable.h *= 2 // double sorted depth 67 } 68 69 for i := range sa { // reconstruct suffix array from inverse 70 sa[inv[i]] = i 71 } 72 return sa 73 } 74 75 func sortedByFirstByte(data []byte) []int { 76 // total byte counts 77 var count [256]int 78 for _, b := range data { 79 count[b]++ 80 } 81 // make count[b] equal index of first occurrence of b in sorted array 82 sum := 0 83 for b := range count { 84 count[b], sum = sum, count[b]+sum 85 } 86 // iterate through bytes, placing index into the correct spot in sa 87 sa := make([]int, len(data)) 88 for i, b := range data { 89 sa[count[b]] = i 90 count[b]++ 91 } 92 return sa 93 } 94 95 func initGroups(sa []int, data []byte) []int { 96 // label contiguous same-letter groups with the same group number 97 inv := make([]int, len(data)) 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 { 102 if prevGroup == i+1 { 103 sa[i+1] = -1 104 } 105 groupByte = b 106 prevGroup = i 107 } 108 inv[sa[i]] = prevGroup 109 if prevGroup == 0 { 110 sa[0] = -1 111 } 112 } 113 // Separate out the final suffix to the start of its group. 114 // This is necessary to ensure the suffix "a" is before "aba" 115 // when using a potentially unstable sort. 116 lastByte := data[len(data)-1] 117 s := -1 118 for i := range sa { 119 if sa[i] >= 0 { 120 if data[sa[i]] == lastByte && s == -1 { 121 s = i 122 } 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 127 break 128 } 129 } 130 } 131 return inv 132 } 133 134 type suffixSortable struct { 135 sa []int 136 inv []int 137 h int 138 buf []int // common scratch space 139 } 140 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] } 144 145 func (x *suffixSortable) updateGroups(offset int) { 146 bounds := x.buf[0:0] 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 { 150 bounds = append(bounds, i) 151 group = g 152 } 153 } 154 bounds = append(bounds, len(x.sa)) 155 x.buf = bounds 156 157 // update the group numberings after all new groups are determined 158 prev := 0 159 for _, b := range bounds { 160 for i := prev; i < b; i++ { 161 x.inv[x.sa[i]] = offset + b - 1 162 } 163 if b-prev == 1 { 164 x.sa[prev] = -1 165 } 166 prev = b 167 } 168 }