libgo/go/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 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.
  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, inv, 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
  76 func sortedByFirstByte(data []byte) []int {
  77         // total byte counts
  78         var count [256]int
  79         for _, b := range data {
  80                 count[b]++
  81         }
  82         // make count[b] equal index of first occurence of b in sorted array
  83         sum := 0
  84         for b := range count {
  85                 count[b], sum = sum, count[b]+sum
  86         }
  87         // iterate through bytes, placing index into the correct spot in sa
  88         sa := make([]int, len(data))
  89         for i, b := range data {
  90                 sa[count[b]] = i
  91                 count[b]++
  92         }
  93         return sa
  94 }
  95
  96
  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 {
 105                                 sa[i+1] = -1
 106                         }
 107                         groupByte = b
 108                         prevGroup = i
 109                 }
 110                 inv[sa[i]] = prevGroup
 111                 if prevGroup == 0 {
 112                         sa[0] = -1
 113                 }
 114         }
 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]
 119         s := -1
 120         for i := range sa {
 121                 if sa[i] >= 0 {
 122                         if data[sa[i]] == lastByte && s == -1 {
 123                                 s = i
 124                         }
 125                         if sa[i] == len(sa)-1 {
 126                                 sa[i], sa[s] = sa[s], sa[i]
 127                                 inv[sa[s]] = s
 128                                 sa[s] = -1 // mark it as an isolated sorted group
 129                                 break
 130                         }
 131                 }
 132         }
 133         return inv
 134 }
 135
 136
 137 type suffixSortable struct {
 138         sa  []int
 139         inv []int
 140         h   int
 141 }
 142
 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] }
 146
 147
 148 func (x *suffixSortable) updateGroups(offset int) {
 149         prev := len(x.sa) - 1
 150         group := x.inv[x.sa[prev]+x.h]
 151         for i := prev; i >= 0; i-- {
 152                 if g := x.inv[x.sa[i]+x.h]; g < group {
 153                         if prev == i+1 { // previous group had size 1 and is thus sorted
 154                                 x.sa[i+1] = -1
 155                         }
 156                         group = g
 157                         prev = i
 158                 }
 159                 x.inv[x.sa[i]] = prev + offset
 160                 if prev == 0 { // first group has size 1 and is thus sorted
 161                         x.sa[0] = -1
 162                 }
 163         }
 164 }