Prologue

倍增法 求字符串的 后缀数组 本质上其实并不难,但是基于 多个数组与基排序 的实现却非常令人迷惑 —— 众多的数组以及更多的循环让初学者一片混乱,包括我。

本文会由浅入深逐步讲解后缀数组、倍增法以及逐步的优化,并在最后附上完整的代码与基准测试结果。

代码均由 golang 实现,但是不用担心,不会有语法问题困扰你。

什么是后缀数组?

后缀数组( Suffix Array )是一个有序数组,其元数为某一个字符串的所有后缀。

比如:

给定字符串 banana 。显然它所有的后缀为: {"banana", "anana", "nana", "ana", "na", "a"} 。不过,这种表示方式冗长且浪费空间,我们可以直接将其简化为 {0, 1, 2, 3, 4, 5} ,其中每个元素都代表该后缀首字母在原本字符串中的索引号。我们设该数组为 Origin

若要根据 Origin 求出 banana 的后缀数组,我们只需要对 Origin 排序即可:

1
2
3
4
5
6
7
8
Origin                            SuffixArray

0 banana 5 a
1 anana Sort the Suffixes 3 ana
2 nana ----------------> 1 anana
3 ana alphabetically 0 banana
4 na 4 na
5 a 2 nana

所以, banana 的后缀数组为 {5, 3, 1, 0, 4, 2} 。(在本文中为升序)

正如我们所见的,后缀数组本身并不复杂,或则说定义很简单,其高深晦涩的地方在于 通过何种高效的排序方式得出后缀数组

可能有人会脱口而出:“快速排序!"

快速排序很棒,使用起来也很方便,各个语言都在系统库中有其实现,但是快速排序并不适合这里:快速排序需要对元素进行 O(NlgN) 次比较,由于元素为字符串,每次元素比较的复杂度为 O(N) ,所以总体复杂度为 O(N^2*lgN)

倍增法

当给定字符串非常非常长时,一般的快速排序显然还不够快,所以我们需要使用倍增法进行适当的改进。

Rank 数组

我们先引进一个 rank 数组,它是一个数组, rank[i] 保存的是后缀经过从小到大排序后,后缀 i 在结果数组中的名次,此时多个后缀可能拥有同一个名次。在最终,后缀排序得出 SuffixArray 时, rank[i] 是指后缀 i 在后缀数组中的名次,且后缀的名次都不重复。

在这里,我们必须搞清 rankSuffixArray 的区别:

SuffixArray[i] 是“排第i的是谁?”, rank[i] 是“后缀i排第几?”。

可知,在 SuffixArray 被排序成后缀数组时, rank[SuffixArray[i]] = i 以及 SuffixArray[rank[i]] = i

思路

对长度为 n 的字符串的所有后缀使用倍增法排序的主要思路是:

用倍增的方式对每个后缀i的长度为 2^k 的前缀部分进行排序,求出排名,即 rank 。其中, k0 开始,每次加 1 ,直到 2^k 大于 n 后,此时每个后缀i的长度为 2k 的前缀部分便相当于后缀i本身。并且这些后缀i都一定已经比较出大小, 即 rank 中没有相同的值,那么此时的 rank 就是最后的结果。

每一次排序都利用上次长度为 2^(k-1) 的前缀部分的 rank 值,那么长度为 2^k 的前缀部分就可以用两个长度为 2^(k-1) 的前缀部分的排名作为关键字表示,对其进行排序,便得出了后缀i的长度为 2^k 的前缀部分的 rank 值。以字符串 aabaaaab 为例,整个过程如下图所示。其中 x, y 表示长度为 2^k 的前缀部分的两个关键字。

基于比较排序的实现

我们已经了解了后缀数组倍增法的基础理论,现在,让我们来实现它。

回想一下倍增法,若要求得后缀i长度为 2^k 的前缀部分的 rank ,我们需要持有哪些数据?

  • 后缀i,
  • 它长度为 2^(k-1) 的前缀部分的 rank
  • 以及位于它后面第 2^k-1 个后缀(即后缀 i+2k-1)的长度为 2^(k-1) 的前缀部分的 rank

为此,定义一个名为 suffix 的结构体:

1
2
3
4
5
6
type suffix struct {
i int
rank [2]int
}

type suffixes []suffix

一个 suffix 类型数据就表示一个后缀,为 后缀suffix.i 。它的 rank 成员的第一个元素储存自身(即后缀i)的长度为 2^(k-1) 的前缀部分的 rank 值,而第二个元素存储它后面第 2^k-1 个后缀(即后缀 i+2k-1)的长度为 2^(k-1) 的前缀部分的 rank 值。

当一个元素类型为 suffix 的数组——我们设它为 suffixes ,经过倍增法逐步排序后,就是最终的后缀数组。为此,我们需要为它定义一些方法便于我们使用系统库的 sort.Sort 排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func (ss suffixes) Len() int {
return len(ss)
}

// rank[0] 是第一个关键字, rank[1] 第二关键字。
func (ss suffixes) Less(i, j int) bool {
a, b := &ss[i], &ss[j]
if a.rank[0] == b.rank[0] {
return a.rank[1] < b.rank[1]
}

return a.rank[0] < b.rank[0]
}

// 交换元素i和元素j
func (ss suffixes) Swap(i, j int) {
ss[i], s[j] = s[j], s[i]
}

// Equal 函数用来比较两个后缀的rank是否相等, MAXLENGTH 为后缀数组最大长度
func Equal(ss *[MAXLENGTH]suffix, i, j int) bool {
a, b := &ss[i], &ss[j]
if a.rank[0] == b.rank[0] && a.rank[1] == b.rank[1] {
return true
}

return false
}

Len()Less()Swap() 方法的定义,实现了 sort.Interface 接口,因此我们可以在一个各元素的 rank 成员都有效的 suffixes 上直接调用 sort.Sort(suffixes) 的方式完成一遍排序。

首先,我们需要初始化这个 suffixes 类型的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// sufarr 是一个 suffixes 变量,它的索引表示排名
// 而数组元素为后缀及其 rank 信息
var sufarr [MAXLENGTH]suffix

// sufnrr 是一个记录各后缀的排名的数组,索引表示后缀i,数组元素sufnrr[i]为后缀i的在sufarr中的排名。(nrr 表示 Non Repeating Rank)
var sufnrr [MAXLENGTH]int

strLen := len(str)

// 初始化 sufarr 数组
for i := 0; i < strLen; i++ {
sufarr[i].i = i
sufarr[i].rank[0] = int(str[i])
sufnrr[i] = i
}

我们求字符串 str 的后缀数组,则先通过它的长度创建一个 sufarrsufnrr

sufarr 在经过多次排序后,最终会成为 str 的后缀数组。

sufnrr 的定义与 rank 类似,它与 rank 数组的区别在于, sufnrr 的元素在任何一趟排序中都是不重复的,及它是不重复的排名值。初始化时,由于还未进行排序, sufnrr 的元素值与它的索引值相等。

PS: sufarr[i].rank[0] 的值应该为后缀i长度为 2^(k-1) 的前缀部分的 rank ,而这里直接使用 str 第i个字节的数值大小,因为 rank 其实只需要相对大小即可。

接下来,让我们看看进行一趟排序的实现过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
l = 2^k - 1

// 求出位于后缀i后面第 2^k-1 个后缀(即后缀 i+2^k-1)的长度为 2^(k-1) 的前缀部分的 rank
// 并将其赋值给 sufarr[i].rank[1], 如果不存在后缀 i+2^k-1, 则 sufarr[i].rank[1] = -1
for i = 0; i < strLen; i++ {
adjSuf := sufarr[i].i + l
if adjSuf < strLen {
sufarr[i].rank[1] = sufarr[sufnrr[adjSuf]].rank[0]
} else {
sufarr[i].rank[1] = -1
}
}

// 根据sufarr中每个元素的 rank[0] 与 rank[1] 进行排序
sort.Sort(suffixes(sufarr[:strLen]))

r = 0
// 给每个元素设置新的不重复排名值和 rank 值
for i = 1; i < strLen; i++ {
sufnrr[sufarr[i-1].i] = i - 1
if Equal(&sufarr, i, i-1) {
sufarr[i-1].rank[0] = r
} else {
sufarr[i-1].rank[0] = r
r++
}
}
// 给最后一个元素设置新的不重复排名值和 rank 值
sufnrr[sufarr[i-1].i] = i - 1
sufarr[i-1].rank[0] = r

根据字符串比较规则:当字符串a是字符串b的前缀时,字符串a小于字符串b。所以我们在后缀 i+2k-1 不存在时,给 sufarr[i].rank[1] 赋值为 -1,使它在排序时第一关键字相等情况下位于其他后缀之前。

sort.Sort(suffixes(sufarr[:strLen])) 由三步组成:

  1. sufarr[:strLen] 切片表达式返回一个由 sufarr 中第一个元素到第 strLen-1 个元素元素组成的切片,
  2. 然后将所得切片转化为 suffixes 类型数据,因为只有 suffixes 类型实现了 sort.Interface
  3. 最后,调用 sort.Sort 函数,实现对 sufarr[:strLen] 的排序

至于在给元素的 rank 重新赋值时,为什么在第i次循环给 sufarr[i-1] 赋值,这个问题我就不解释了,留给读者自己思考。

k0 开始,每次加 1 ,直到 2^k 大于 n 。最终, sufarr[i].i 组成的数组将是后缀数组。

1
2
3
4
suffixArray := make([]int, strLen)
for i := 0; i < strLen; i++ {
suffixArray[i] = sufarr[i].i
}

复杂度分析

它时间复杂度有两部分组成,由 k=02^k > n 一共经历了 lgN 趟排序(其中N为原字符串的长度),时间复杂度为 O(lgN) ,没趟排序的复杂度取决于 sort.Sort() ,为 O(NlgN) , 所以该实现的时间复杂度总共为 O(N*(lgN)^2) 。可见这是一种优于直接快速排序的方法。

全部代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
type suffix struct {
i int
rank [2]int
}

type suffixes []suffix

func (ss suffixes) Len() int {
return len(ss)
}

func (ss suffixes) Less(i, j int) bool {
a, b := &ss[i], &ss[j]
if a.rank[0] == b.rank[0] {
return a.rank[1] < b.rank[1]
}

return a.rank[0] < b.rank[0]
}

func (ss suffixes) Swap(i, j int) {
ss[i], ss[j] = ss[j], ss[i]
}

var sufarr [MAXLENGTH]suffix

func Equal(ss *[MAXLENGTH]suffix, i, j int) bool {
a, b := &ss[i], &ss[j]
if a.rank[0] == b.rank[0] && a.rank[1] == b.rank[1] {
return true
}

return false
}

var sufnrr [MAXLENGTH]int

func BuildByCmpSort(str string) []int {
strLen := len(str)

for i := 0; i < strLen; i++ {
sufarr[i].i = i
sufarr[i].rank[0] = int(str[i])
sufnrr[i] = i
}

for i, k, l := 0, 1, 0; k < strLen; k <<= 1 {
l = k - 1

for i = 0; i < strLen; i++ {
adjSuf := sufarr[i].i + l
if adjSuf < strLen {
sufarr[i].rank[1] = sufarr[sufnrr[adjSuf]].rank[0]
} else {
sufarr[i].rank[1] = -1
}
}

sort.Sort(suffixes(sufarr[:strLen]))

r = 0
for i = 1; i < strLen; i++ {
sufnrr[sufarr[i-1].i] = i - 1
if Equal(&sufarr, i, i-1) {
sufarr[i-1].rank[0] = r
} else {
sufarr[i-1].rank[0] = r
r++
}
}
sufnrr[sufarr[i-1].i] = i - 1
sufarr[i-1].rank[0] = r
}

suffixArray := make([]int, strLen)
for i := 0; i < strLen; i++ {
suffixArray[i] = sufarr[i].i
}

return suffixArray
}

基于基数排序的实现

从“基于比较的实现“中,可以得知,通过倍增法求后缀数组的时间复杂度主要由两部分组成:

  • 外部的 lgN 次循环提供的 O(lgN)
  • 每次循环内部根据两个 rank 值进行的一趟排序,它复杂度为 O(NlgN)

我们无法改变外部的循环次数,但是可以优化内部一趟排序。现在问题来了:什么排序的时间复杂度优于 O(NlgN) ?

计数排序、基数排序以及桶排序。

桶排序显然不适合这里,我们也无法使用‘简单’的计数排序实现对两个关键字的排序,所以我们这里应该使用基数排序,但其中对每一个关键字依旧使用计数排序。

首先,我们申明需要的基础数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var rank         *[MAXLENGTH]int
var rankAdjnrr *[MAXLENGTH]int

func init() {
rank = &[MAXLENGTH]int{}
rankAdjnrr = &[MAXLENGTH]int{}
}

// isEqual 函数用来比较两个后缀的rank值与rankAdj值是否相等
func isEqual(i, j, l int) bool {
strLen := len(rank)
var (
iAdjRank int
iAdjRank int
)

if i+l >= strLen {
iAdjRank = -1
} else {
iAdjRank = rank[i+l]
}
if j+l >= strLen {
jAdjRank = -1
} else {
jAdjRank = rank[j+l]
}

return rank[i] == rank[j] && iAdjRank == jAdjRank
}

为了便于基数排序,我们不再使用 suffix 结构体,而是直接申明两 []int 类型的变量 rankrankAdj 。其中,变量 rank[i] 为后缀i长度为 2^(k-1) 的前缀部分的 rank 值,变量 rankAdj[i] 为后缀i+2k-1的长度为 2^(k-1) 的前缀部分的 rank 值。

然后依然是初始化:

1
2
3
4
5
6
7
strLen := len(str)
sufarr := make([]int, strLen)

for i := range str {
sufarr[i] = i
rank[i] = int(str[i])
}

经倍增法排序后的 sufarr 就是我们所求的后缀数组。

最初同样直接使用 str 第i个字节的数值大小表示后缀i的长度为 1 的前缀部分的 rank 值。

而每一趟排序的大致结构也与之前类似:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
l = k - 1

// 根据rank数组求出rankAdj数组
for i = 0; i < strLen; i++ {
if i+l >= strLen {
// 当不存在后缀i+2^k-1时, rankAdj[i] = -1
rankAdj[i] = -1
} else {
rankAdj[i] = rank[i+l]
}
}

// 根据 rank 与 rankAdj 对sufarr进行排序
RadixSort(sufarr)

// 根据sufarr的排序结果,求出新的rank数组
newRank := rankAdj
r := 1
newRank[sufarr[0]] = 0
for i := 1; i < strLen; i++ {
curSuf, prevSuf := sufarr[i], sufarr[i-1]
if isEqual(curSuf, prevSuf, l) {
newRank[curSuf] = r - 1
} else {
newRank[curSuf] = r
r++
}
}
rank, rankAdj = newRank, rank

这里我们使用了一个巧妙地方法求新的 rank 数组。由于在基数排序过后, rankAdj 在这趟排序中已经没有用处了,所以我们直接使用 rankAdj 作为新的 rank 数组,在求出新的 rank 数组后,在将它们的引用交换。

好,现在是最关键的内部的基数排序的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
var tempSufarr [MAXLENGTH]int
var radixSortArr [MAXLENGTH]int

func RadixSort(sufarr []int) {
strLen := len(sufarr)
radixLen := int(math.Max(float64(strLen), 256)) + 1

// 第一次,以rankAdj为关键字进行计数排序
var i int
for i = 0; i < radixLen; i++ {
radixSortArr[i] = 0
}
for i = 0; i < strLen; i++ {
radixSortArr[rankAdj[i]+1]++
}
t := radixSortArr[0]
for i = 1; i < radixLen; i++ {
radixSortArr[i] += t
t = radixSortArr[i]
}
for i = strLen - 1; i > -1; i-- {
radixSortArr[rankAdj[i]+1]--
tempSufarr[radixSortArr[rankAdj[i]+1]] = i
}

// 第二次,以rank为关键字进行计数排序
for i = 0; i < radixLen; i++ {
radixSortArr[i] = 0
}
for i = 0; i < strLen; i++ {
radixSortArr[rank[i]]++
}
t := radixSortArr[0]
for i = 1; i < radixLen; i++ {
radixSortArr[i] += t
t = radixSortArr[i]
}
for i = strLen - 1; i > -1; i-- {
t = tempSufarr[i]
radixSortArr[rank[t]]--
sufarr[radixSortArr[rank[t]]] = t
}
}

由于我们需要以 rank 值为第一关键字, rankAdj 值为第二关键字对 sufarr 进行排序,所以根据基数排序,先以 rankAdj 为关键字进行计数排序,在以 rank 为关键字进行计数排序。

第一次计数排序得到的结果 tempSufarr 是后缀根据 rankAdj 计数排序所得的,它是一个 nrr (Non Repeating Ranking) 的数组,它将作为下一次计数排序的重要素材。

至于第二次排序最后一次循环中为什么是使用 radixSortArr[rank[tempSufarr[i]]] 而不是 radixSortArr[rank[i]] ,我会在写一篇blog通过讨论“计数排序的稳定性”来解释,在那之前读者可以先自行思考。

两次计数排序组成的基数排序将正确地对 sufarr 进行排序。

复杂度分析

每次循环内部使用了基数排序后,时间复杂度降为 O(N) ,而总体时间复杂度为 O(NlgN)

全部代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
var rank, rankAdj [MAXLENGTH]int

func init() {
rank = &[MAXLENGTH]int
rankAdj = &[MAXLENGTH]int
}

func isEqual(i, j, l int) bool {
strLen := len(rank)
var (
iAdjRank int
iAdjRank int
)

if i+l >= strLen {
iAdjRank = -1
} else {
iAdjRank = rank[i+l]
}
if j+l >= strLen {
jAdjRank = -1
} else {
jAdjRank = rank[j+l]
}

return rank[i] == rank[j] && iAdjRank == jAdjRank
}

var tempSufarr [MAXLENGTH]int
var radixSortArr [MAXLENGTH]int

func RadixSort(sufarr []int) {
strLen := len(sufarr)
radixLen := int(math.Max(float64(strLen), 256)) + 1

var i int
for i = 0; i < radixLen; i++ {
radixSortArr[i] = 0
}
for i = 0; i < strLen; i++ {
radixSortArr[rankAdj[i]+1]++
}
t := radixSortArr[0]
for i = 1; i < radixLen; i++ {
radixSortArr[i] += t
t = radixSortArr[i]
}
for i = strLen - 1; i > -1; i-- {
radixSortArr[rankAdj[i]+1]--
tempSufarr[radixSortArr[rankAdj[i]+1]] = i
}

for i = 0; i < radixLen; i++ {
radixSortArr[i] = 0
}
for i = 0; i < strLen; i++ {
radixSortArr[rank[i]]++
}
t := radixSortArr[0]
for i = 1; i < radixLen; i++ {
radixSortArr[i] += t
t = radixSortArr[i]
}
for i = strLen - 1; i > -1; i-- {
t = tempSufarr[i]
radixSortArr[rank[t]]--
sufarr[radixSortArr[rank[t]]] = t
}
}

func BuildByRadixSort(str string) []int {
strLen := len(str)
sufarr := make([]int, strLen)

for i := range str {
sufarr[i] = i
rank[i] = int(str[i])
}

for i, l, k := 0, 0, 1; k < strLen; k <<= 1 {
l = k - 1

for i = 0; i < strLen; i++ {
if i+l >= strLen {
rankAdj[i] = -1
} else {
rankAdj[i] = rank[i+l]
}
}

RadixSort(sufarr)

newRank := rankAdj
r := 1
newRank[sufarr[0]] = 0
for i := 1; i < strLen; i++ {
curSuf, prevSuf := sufarr[i], sufarr[i-1]
if isEqual(curSuf, prevSuf, l) {
newRank[curSuf] = r - 1
} else {
newRank[curSuf] = r
r++
}
}
rank, rankAdj = newRank, rank
}

return sufarr
}

基于基数排序的实现(优化基数排序)

我们已经实现 O(NlgN) 复杂度的排序法,这看起来已经很酷了~~~~

然而,我们还可以做得更好!

在上一个实现中,我们通过两次计数排序完成一次基数排序,这看起来没什么问题,除了过多的 for 循环语句,但是如果我们仔细思考第一次计数排序——即以rankAdj为关键字的计数排序,会发现其实我们可以通过更快的方法根据 rank 数组求出 tempSufarr

已知 tempSufarr 数组是一个 nrr 数组,它的索引是第二关键字的名次,而元素是后缀, tempSufarr[j] = i 表示后缀i的第二关键字(即后缀i+2k-1)在所有第二关键字中排名为 j 。

现在有如下情况:

1
2
3
4
5
region:          |     A    |      B       |    C   |
rank: [4 6 8 1 2 3 5 7]
[ 4 6 8 1 2 3 5 7] -1 -1 -1

rankAdj: [1 2 3 5 7 -1 -1 -1]

很容易看出此时 k = 2 。区域A中的值是无效值,而区域C由于 i+2^k-1 超出 rank 数组,所以值全为 -1 。

-1 已经是 rankAdj 中最小的值了,由于在第一关键字和第二关键字相同时,元素间相对次序不会发送变化,所以我们可以直接将区域C中的索引搬到下一次 tempSufarr 的开始部分: {3, 5, 7}

然后,我们需要在区域B中有序地找出 rankAjd 值大于等于 0 的后缀。其实,在我们通过 sufarr 求出 rank 时,下方的不等式已经是必然成立了:

1
rank[sufarr[0]] < rank[sufarr[1]] < rank[sufarr[2]] < ... < rank[sufarr[6]]

只要顺着 sufarr 数组找,得到的后缀的 rankAdj 值就是有序的,而如果 sufarr[j] >= 2^k-1 ,则 sufarr[j] 存在于下列不等式中:

1
rankAdj[sufarr[0]] < rankAdj[sufarr[1]] < rankAdj[sufarr[2]] < ... < rankAdj[sufarr[6]]

该不等式一共有5个元素,刚好是区域B的大小。由于是在 rankAdj 中的排名,该式的 sufarr[j] 是后缀i+2k-1。

以下代码就是我们前面讨论的求 tempSufarr 的过程,只不过把 tempSufarr 换成了 rankAdjnrr

1
2
3
4
5
6
7
8
9
10
11
p := 0
for i = strLen - l; i < strLen; i++ {
rankAdjnrr[p] = i
p++
}
for i = 0; i < strLen; i++ {
if sufarr[i] >= l {
rankAdjnrr[p] = sufarr[i] - l
p++
}
}

我们可以用这段代码替换掉上一个实现中求 rankAdj 数组和根据第二关键字计数排序的过程。

全部代码

这段也是网上出现最多,最难看懂的一段代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
var rank         *[MAXLENGTH]int
var rankAdjnrr *[MAXLENGTH]int
var radixSortArr [MAXLENGTH]int

func init() {
rank = &[MAXLENGTH]int{}
rankAdjnrr = &[MAXLENGTH]int{}
}

func isEqual(i, j, l int) bool {
strLen := len(rank)
var (
iAdjRank int
jAdjRank int
)

if i+l >= strLen {
iAdjRank = -1
} else {
iAdjRank = rank[i+l]
}
if j+l >= strLen {
jAdjRank = -1
} else {
jAdjRank = rank[j+l]
}

return rank[i] == rank[j] && iAdjRank == jAdjRank
}

func BuildByRadixSort2(str string) []int {
strLen := len(str)
radixLen := int(math.Max(float64(strLen), 256))

sufarr := make([]int, strLen)

for i := range str {
sufarr[i] = i
rank[i] = int(str[i])
}

var radixTemp int
for i, l, k := 0, 0, 1; k < strLen; k <<= 1 {
l = k - 1

// 这一段替换掉了 求randAdj 和 第一次计数排序
p := 0
for i = strLen - l; i < strLen; i++ {
rankAdjnrr[p] = i
p++
}
for i = 0; i < strLen; i++ {
if sufarr[i] >= l {
rankAdjnrr[p] = sufarr[i] - l
p++
}
}

// Radix Sort
for i = 0; i < radixLen; i++ {
radixSortArr[i] = 0
}
for i = 0; i < strLen; i++ {
radixSortArr[rank[i]]++
}
radixTemp = radixSortArr[0]
for i = 1; i < radixLen; i++ {
radixSortArr[i] += radixTemp
radixTemp = radixSortArr[i]
}
for i = strLen - 1; i > -1; i-- {
radixTemp = rankAdjnrr[i]
radixSortArr[rank[radixTemp]]--
sufarr[radixSortArr[rank[radixTemp]]] = radixTemp
}

newRank := rankAdjnrr
r := 1
newRank[sufarr[0]] = 0
for i = 1; i < strLen; i++ {
curSuf, prevSuf := sufarr[i], sufarr[i-1]
if isEqual(curSuf, prevSuf, l) {
newRank[curSuf] = r - 1
} else {
newRank[curSuf] = r
r++
}
}
rank, rankAdjnrr = newRank, rank
}

return sufarr
}

Benchmark

我们先写一个最初被我否决的方案——直接快速排序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
type rawsuff struct {
sufarr []int
str string
}

// Len ...
func (rs *rawsuff) Len() int {
return len(rs.sufarr)
}

// Less ...
func (rs *rawsuff) Less(i, j int) bool {
return string(rs.str[rs.sufarr[i]:]) < string(rs.str[rs.sufarr[j]:])
}

// Swap ...
func (rs *rawsuff) Swap(i, j int) {
rs.sufarr[i], rs.sufarr[j] = rs.sufarr[j], rs.sufarr[i]
}

func RawSort(str string) []int {
strLen := len(str)
sufarr := make([]int, strLen)

for i := range sufarr {
sufarr[i] = i
}

sort.Sort(&rawsuff{
sufarr: sufarr,
str: str,
})

return sufarr
}
  • 随机字符串长度为 10
1
2
3
4
BenchmarkRawSort-4      	 2000000	       676 ns/op	     128 B/op	       2 allocs/op
BenchmarkCmpSort-4 1000000 1072 ns/op 208 B/op 5 allocs/op
BenchmarkRadixSort1-4 300000 4305 ns/op 80 B/op 1 allocs/op
BenchmarkRadixSort2-4 500000 2350 ns/op 80 B/op 1 allocs/op

RadixSort2 是经过基数排序优化的。

  • 随机字符串长度为 100
1
2
3
4
BenchmarkRawSort-4      	  100000	     11431 ns/op	     944 B/op	       2 allocs/op
BenchmarkCmpSort-4 50000 32060 ns/op 1120 B/op 8 allocs/op
BenchmarkRadixSort1-4 100000 18833 ns/op 896 B/op 1 allocs/op
BenchmarkRadixSort2-4 100000 12346 ns/op 896 B/op 1 allocs/op
  • 随机字符串长度为 1000
1
2
3
4
BenchmarkRawSort-4      	    5000	    284441 ns/op	    8240 B/op	       2 allocs/op
BenchmarkCmpSort-4 2000 800005 ns/op 8512 B/op 11 allocs/op
BenchmarkRadixSort1-4 10000 214813 ns/op 8192 B/op 1 allocs/op
BenchmarkRadixSort2-4 10000 156841 ns/op 8192 B/op 1 allocs/op
  • 随机字符串长度为 10000
1
2
3
4
BenchmarkRawSort-4      	     300	   3767895 ns/op	   81968 B/op	       2 allocs/op
BenchmarkCmpSort-4 100 14019824 ns/op 82368 B/op 15 allocs/op
BenchmarkRadixSort1-4 300 3989277 ns/op 81920 B/op 1 allocs/op
BenchmarkRadixSort2-4 500 2726894 ns/op 81920 B/op 1 allocs/op
  • 随机字符串长度为 100000
1
2
3
4
BenchmarkRawSort-4      	      20	  58836259 ns/op	  802864 B/op	       2 allocs/op
BenchmarkCmpSort-4 5 299357701 ns/op 803360 B/op 18 allocs/op
BenchmarkRadixSort1-4 10 122560552 ns/op 802816 B/op 1 allocs/op
BenchmarkRadixSort2-4 20 65983308 ns/op 802820 B/op 1 allocs/op

当字符串长度为 100000 我的实现并不能比 sort.Sort 好。

  • 随机字符串长度为 1000000
1
2
3
4
BenchmarkRawSort-4      	       2	 641055861 ns/op	 8003632 B/op	       2 allocs/op
BenchmarkCmpSort-4 1 3692050970 ns/op 8004224 B/op 21 allocs/op
BenchmarkRadixSort1-4 1 7731306777 ns/op 8003584 B/op 1 allocs/op
BenchmarkRadixSort2-4 1 5428793138 ns/op 8003584 B/op 1 allocs/op