← Back to branch summary

~john-koepi/ubuntu/trusty/golang/default

« back to all changes in this revision

Viewing changes to src/pkg/index/suffixarray/suffixarray.go

  • Committer: Bazaar Package Importer
  • Author(s): Ondřej Surý
  • Date: 2011-04-20 17:36:48 UTC
  • Revision ID: james.westby@ubuntu.com-20110420173648-ifergoxyrm832trd
Tags: upstream-2011.03.07.1
Import upstream version 2011.03.07.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/pkg/index/suffixarray/suffixarray.go
 
1
// Copyright 2010 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
// The suffixarray package implements substring search in logarithmic time
 
6
// using an in-memory suffix array.
 
7
//
 
8
// Example use:
 
9
//
 
10
//      // create index for some data
 
11
//      index := suffixarray.New(data)
 
12
//
 
13
//      // lookup byte slice s
 
14
//      offsets1 := index.Lookup(s, -1) // the list of all indices where s occurs in data
 
15
//      offsets2 := index.Lookup(s, 3)  // the list of at most 3 indices where s occurs in data
 
16
//
 
17
package suffixarray
 
18
 
 
19
import (
 
20
        "bytes"
 
21
        "regexp"
 
22
        "sort"
 
23
)
 
24
 
 
25
 
 
26
// Index implements a suffix array for fast substring search.
 
27
type Index struct {
 
28
        data []byte
 
29
        sa   []int // suffix array for data
 
30
}
 
31
 
 
32
 
 
33
// New creates a new Index for data.
 
34
// Index creation time is O(N*log(N)) for N = len(data).
 
35
func New(data []byte) *Index {
 
36
        return &Index{data, qsufsort(data)}
 
37
}
 
38
 
 
39
 
 
40
// Bytes returns the data over which the index was created.
 
41
// It must not be modified.
 
42
//
 
43
func (x *Index) Bytes() []byte {
 
44
        return x.data
 
45
}
 
46
 
 
47
 
 
48
func (x *Index) at(i int) []byte {
 
49
        return x.data[x.sa[i]:]
 
50
}
 
51
 
 
52
 
 
53
// lookupAll returns a slice into the matching region of the index.
 
54
// The runtime is O(log(N)*len(s)).
 
55
func (x *Index) lookupAll(s []byte) []int {
 
56
        // find matching suffix index range [i:j]
 
57
        // find the first index where s would be the prefix
 
58
        i := sort.Search(len(x.sa), func(i int) bool { return bytes.Compare(x.at(i), s) >= 0 })
 
59
        // starting at i, find the first index at which s is not a prefix
 
60
        j := i + sort.Search(len(x.sa)-i, func(j int) bool { return !bytes.HasPrefix(x.at(j+i), s) })
 
61
        return x.sa[i:j]
 
62
}
 
63
 
 
64
 
 
65
// Lookup returns an unsorted list of at most n indices where the byte string s
 
66
// occurs in the indexed data. If n < 0, all occurrences are returned.
 
67
// The result is nil if s is empty, s is not found, or n == 0.
 
68
// Lookup time is O(log(N)*len(s) + len(result)) where N is the
 
69
// size of the indexed data.
 
70
//
 
71
func (x *Index) Lookup(s []byte, n int) (result []int) {
 
72
        if len(s) > 0 && n != 0 {
 
73
                matches := x.lookupAll(s)
 
74
                if len(matches) < n || n < 0 {
 
75
                        n = len(matches)
 
76
                }
 
77
                if n > 0 {
 
78
                        result = make([]int, n)
 
79
                        copy(result, matches)
 
80
                }
 
81
        }
 
82
        return
 
83
}
 
84
 
 
85
 
 
86
// FindAllIndex returns a sorted list of non-overlapping matches of the
 
87
// regular expression r, where a match is a pair of indices specifying
 
88
// the matched slice of x.Bytes(). If n < 0, all matches are returned
 
89
// in successive order. Otherwise, at most n matches are returned and
 
90
// they may not be successive. The result is nil if there are no matches,
 
91
// or if n == 0.
 
92
//
 
93
func (x *Index) FindAllIndex(r *regexp.Regexp, n int) (result [][]int) {
 
94
        // a non-empty literal prefix is used to determine possible
 
95
        // match start indices with Lookup
 
96
        prefix, complete := r.LiteralPrefix()
 
97
        lit := []byte(prefix)
 
98
 
 
99
        // worst-case scenario: no literal prefix
 
100
        if prefix == "" {
 
101
                return r.FindAllIndex(x.data, n)
 
102
        }
 
103
 
 
104
        // if regexp is a literal just use Lookup and convert its
 
105
        // result into match pairs
 
106
        if complete {
 
107
                // Lookup returns indices that may belong to overlapping matches.
 
108
                // After eliminating them, we may end up with fewer than n matches.
 
109
                // If we don't have enough at the end, redo the search with an
 
110
                // increased value n1, but only if Lookup returned all the requested
 
111
                // indices in the first place (if it returned fewer than that then
 
112
                // there cannot be more).
 
113
                for n1 := n; ; n1 += 2 * (n - len(result)) /* overflow ok */ {
 
114
                        indices := x.Lookup(lit, n1)
 
115
                        if len(indices) == 0 {
 
116
                                return
 
117
                        }
 
118
                        sort.SortInts(indices)
 
119
                        pairs := make([]int, 2*len(indices))
 
120
                        result = make([][]int, len(indices))
 
121
                        count := 0
 
122
                        prev := 0
 
123
                        for _, i := range indices {
 
124
                                if count == n {
 
125
                                        break
 
126
                                }
 
127
                                // ignore indices leading to overlapping matches
 
128
                                if prev <= i {
 
129
                                        j := 2 * count
 
130
                                        pairs[j+0] = i
 
131
                                        pairs[j+1] = i + len(lit)
 
132
                                        result[count] = pairs[j : j+2]
 
133
                                        count++
 
134
                                        prev = i + len(lit)
 
135
                                }
 
136
                        }
 
137
                        result = result[0:count]
 
138
                        if len(result) >= n || len(indices) != n1 {
 
139
                                // found all matches or there's no chance to find more
 
140
                                // (n and n1 can be negative)
 
141
                                break
 
142
                        }
 
143
                }
 
144
                if len(result) == 0 {
 
145
                        result = nil
 
146
                }
 
147
                return
 
148
        }
 
149
 
 
150
        // regexp has a non-empty literal prefix; Lookup(lit) computes
 
151
        // the indices of possible complete matches; use these as starting
 
152
        // points for anchored searches
 
153
        // (regexp "^" matches beginning of input, not beginning of line)
 
154
        r = regexp.MustCompile("^" + r.String()) // compiles because r compiled
 
155
 
 
156
        // same comment about Lookup applies here as in the loop above
 
157
        for n1 := n; ; n1 += 2 * (n - len(result)) /* overflow ok */ {
 
158
                indices := x.Lookup(lit, n1)
 
159
                if len(indices) == 0 {
 
160
                        return
 
161
                }
 
162
                sort.SortInts(indices)
 
163
                result = result[0:0]
 
164
                prev := 0
 
165
                for _, i := range indices {
 
166
                        if len(result) == n {
 
167
                                break
 
168
                        }
 
169
                        m := r.FindIndex(x.data[i:]) // anchored search - will not run off
 
170
                        // ignore indices leading to overlapping matches
 
171
                        if m != nil && prev <= i {
 
172
                                m[0] = i // correct m
 
173
                                m[1] += i
 
174
                                result = append(result, m)
 
175
                                prev = m[1]
 
176
                        }
 
177
                }
 
178
                if len(result) >= n || len(indices) != n1 {
 
179
                        // found all matches or there's no chance to find more
 
180
                        // (n and n1 can be negative)
 
181
                        break
 
182
                }
 
183
        }
 
184
        if len(result) == 0 {
 
185
                result = nil
 
186
        }
 
187
        return
 
188
}