-
Notifications
You must be signed in to change notification settings - Fork 0
/
bwst.go
160 lines (147 loc) · 3.7 KB
/
bwst.go
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
package bwst
import (
"sort"
"sync"
)
// Compute the Burrows-Wheeler-Scott transform of s. This is done
// out-of-place.
func BWST(s []byte) []byte {
words := factorize(s)
// Sorting all rotations of all Lyndon words and then choosing the last
// character of each is the same as choosing the character to the left of
// each character in its Lyndon word in sorted order. Therefore, we find
// all locations of each character, sort them all by their rotations, and
// proceed therein.
locs := locate(s, words)
b := make([]byte, 0, len(s))
var wg sync.WaitGroup
for _, charLocs := range locs {
wg.Add(1)
go func(charLocs []loc) { defer wg.Done(); sortrots(s, words, charLocs) }(charLocs)
}
wg.Wait()
for _, charLocs := range locs {
for _, l := range charLocs {
word := s[words[l.word]:words[l.word+1]]
i := l.idx - 1
if i < 0 {
i = len(word) - 1
}
b = append(b, word[i])
}
}
return b
}
// Better than actually storing all rotations of all words. Probably.
type loc struct {
word, idx int
}
func locate(s []byte, words []int) (locs [256][]loc) {
w := 0
for i, c := range s {
if i >= words[w+1] {
w++
}
locs[int(c)] = append(locs[int(c)], loc{w, i - words[w]})
}
return locs
}
// Compute the Lyndon factorization of s. Includes both endpoints.
func factorize(s []byte) (bounds []int) {
// Do an initial pass to count the number of words. Hopefully this avoids
// enough copying to be faster.
ch := make(chan int)
go findLyndon(s, ch)
n := 1
for _ = range ch {
n++
}
ch = make(chan int)
go findLyndon(s, ch)
bounds = make([]int, 1, n+1)
for i := range ch {
bounds = append(bounds, i)
}
return bounds
}
// Duval's algorithm. This is done concurrently under factorize() to enable
// word counting without doing extra work.
func findLyndon(s []byte, ch chan<- int) {
// Thanks to Jonathan on golang-nuts for simplifying the inner loop.
k := -1
for k < len(s)-1 {
i, j := k+1, k+2
for j < len(s) && s[i] <= s[j] {
if s[i] < s[j] {
// Whenever a character is less than the first character of a
// Lyndon word, it is not in that word.
i = k
}
// When the character at i is equal to the character at the start
// of the word, whether it is a part of that word or the start of
// the next is determined by the remainder of the string: if the
// substring s[k..n] < s[i..n], then s[i] is in the word starting
// at k.
i++
j++
}
for k < i {
k += j - i
ch <- k + 1
}
}
close(ch)
}
// Each instance of a character is considered to be at the beginning of a
// rotation of its word, so the locations can be sorted. Because each char is
// in order already, we only need to sort the occurrences of each char
// separately to sort the entire thing.
func sortrots(s []byte, words []int, locs []loc) {
l := locsorter{locs, s, words}
sort.Sort(l)
}
type locsorter struct {
locs []loc
s []byte
words []int
}
func (l locsorter) Len() int { return len(l.locs) }
func (l locsorter) Swap(i, j int) { l.locs[i], l.locs[j] = l.locs[j], l.locs[i] }
// Cyclic order - AXYA < AXY here because AXYAAXYA < AXYAXY
func (l locsorter) Less(i, j int) bool {
loc1, loc2 := l.locs[i], l.locs[j]
// get the actual sequences
w1 := l.s[l.words[loc1.word]:l.words[loc1.word+1]]
w2 := l.s[l.words[loc2.word]:l.words[loc2.word+1]]
x, y := loc1.idx, loc2.idx
n := lcm(len(w1), len(w2))
for i := 0; i < n; i++ {
if a, b := w1[x], w2[y]; a < b {
return true
} else if a > b {
return false
}
x++
if x >= len(w1) {
x = 0
}
y++
if y >= len(w2) {
y = 0
}
}
// words are equal
return false
}
func gcd(m, n int) int {
var tmp int
for m != 0 {
tmp = m
m = n % m
n = tmp
}
return n
}
func lcm(m, n int) int {
return m / gcd(m, n) * n
}