-
Notifications
You must be signed in to change notification settings - Fork 148
/
Copy pathindex_suffixarray.htm
69 lines (68 loc) · 5.63 KB
/
index_suffixarray.htm
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
<!DOCTYPE html>
<html lang="en">
<head profile="http://a9.com/-/spec/opensearch/1.1/">
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link href="../assets/site.css" rel="stylesheet">
<title>index/suffixarray</title>
</head>
<body>
<div class="container">
<h2 id="pkg-overview">package suffixarray</h2>
<p><code>import "index/suffixarray"</code>
<p align="left">suffixarrayb包通过使用内存中的后缀树实现了对数级时间消耗的子字符串搜索。</p>
<p align="left">用法举例：</p>
<pre>// 创建数据的索引
index := suffixarray.New(data)
// 查找切片s
offsets1 := index.Lookup(s, -1) // 返回data中所有s出现的位置
offsets2 := index.Lookup(s, 3) // 返回data中最多3个所有s出现的位置</pre>
<h3 id="pkg-index" class="section-header">Index <a class="permalink" href="#pkg-index">¶</a></h3>
<a href="../main.html"><h3>返回首页</h3></a>
</br>
<li><a href="#Index">type Index</a></li>
<ul>
<li><a href="#New">func New(data []byte) *Index</a></li>
<li><a href="#Index.Bytes">func (x *Index) Bytes() []byte</a></li>
<li><a href="#Index.Read">func (x *Index) Read(r io.Reader) error</a></li>
<li><a href="#Index.Write">func (x *Index) Write(w io.Writer) error</a></li>
<li><a href="#Index.Lookup">func (x *Index) Lookup(s []byte, n int) (result []int)</a></li>
<li><a href="#Index.FindAllIndex">func (x *Index) FindAllIndex(r *regexp.Regexp, n int) (result [][]int)</a></li>
</ul>
</ul>
<h3 id="Index">type <a title="View Source" href="https://github.com/golang/go/blob/master/src/index/suffixarray/suffixarray.go?name=release#28">Index</a> <a class="permalink" href="#pkg-index">¶</a></h3>
<pre>type Index struct {
<span class="com">// 内含隐藏或非导出字段</span>
}</pre>
<p>Index类型实现了用于快速子字符串搜索的后缀数组。</p>
<h4 id="New">func <a title="View Source" href="https://github.com/golang/go/blob/master/src/index/suffixarray/suffixarray.go?name=release#35">New</a> <a class="permalink" href="#pkg-index">¶</a></h4>
<pre class="funcdecl">func New(data []<a href="builtin.htm#byte">byte</a>) *<a href="#Index">Index</a></pre>
<p>使用给出的[]byte数据生成一个*Index，时间复杂度O(N*log(N))。</p>
<h4 id="Index.Bytes">func (*Index) <a title="View Source" href="https://github.com/golang/go/blob/master/src/index/suffixarray/suffixarray.go?name=release#165">Bytes</a> <a class="permalink" href="#pkg-index">¶</a></h4>
<pre class="funcdecl">func (x *<a href="#Index">Index</a>) Bytes() []<a href="builtin.htm#byte">byte</a></pre>
<p>返回创建x时提供的[]byte数据，注意不能修改返回值。</p>
<h4 id="Index.Read">func (*Index) <a title="View Source" href="https://github.com/golang/go/blob/master/src/index/suffixarray/suffixarray.go?name=release#98">Read</a> <a class="permalink" href="#pkg-index">¶</a></h4>
<pre class="funcdecl">func (x *<a href="#Index">Index</a>) Read(r <a href="io.htm">io</a>.<a href="io.htm#Reader">Reader</a>) <a href="builtin.htm#error">error</a></pre>
<p>从r中读取一个index写入x，x不能为nil。</p>
<h4 id="Index.Write">func (*Index) <a title="View Source" href="https://github.com/golang/go/blob/master/src/index/suffixarray/suffixarray.go?name=release#137">Write</a> <a class="permalink" href="#pkg-index">¶</a></h4>
<pre class="funcdecl">func (x *<a href="#Index">Index</a>) Write(w <a href="io.htm">io</a>.<a href="io.htm#Writer">Writer</a>) <a href="builtin.htm#error">error</a></pre>
<p>将x中的index写入w中，x不能为nil。</p>
<h4 id="Index.Lookup">func (*Index) <a title="View Source" href="https://github.com/golang/go/blob/master/src/index/suffixarray/suffixarray.go?name=release#190">Lookup</a> <a class="permalink" href="#pkg-index">¶</a></h4>
<pre class="funcdecl">func (x *<a href="#Index">Index</a>) Lookup(s []<a href="builtin.htm#byte">byte</a>, n <a href="builtin.htm#int">int</a>) (result []<a href="builtin.htm#int">int</a>)</pre>
<p>返回一个未排序的列表，内为s在被索引为index的切片数据中出现的位置。如果n<0，返回全部匹配；如果n==0或s为空，返回nil；否则n为result的最大长度。时间复杂度O(log(N)*len(s) + len(result))，其中N是被索引的数据的大小。</p>
<h4 id="Index.FindAllIndex">func (*Index) <a title="View Source" href="https://github.com/golang/go/blob/master/src/index/suffixarray/suffixarray.go?name=release#212">FindAllIndex</a> <a class="permalink" href="#pkg-index">¶</a></h4>
<pre class="funcdecl">func (x *<a href="#Index">Index</a>) FindAllIndex(r *<a href="regexp.htm">regexp</a>.<a href="regexp.htm#Regexp">Regexp</a>, n <a href="builtin.htm#int">int</a>) (result [][]<a href="builtin.htm#int">int</a>)</pre>
<p>返回一个正则表达式r的不重叠的匹配的经过排序的列表，一个匹配表示为一对指定了匹配结果的切片的索引（相对于x.Bytes())。如果n<0，返回全部匹配；如果n==0或匹配失败，返回nil；否则n为result的最大长度。</p>
</div>
<div id="x-footer" class="clearfix">
<div class="container">
<a href="http://studygolang.com/" target="_blank">Go语言中文网</a>
<span class="text-muted">|</span> <a href="http://golang.org/" target="_blank">Go Language</a>
<span class="pull-right"><a href="#">Back to top</a></span>
</div>
</div>
<script src="../assets/jquery-2.0.3.min.js"></script>
<script src="../assets/bootstrap.min.js"></script>
<script src="../assets/site.js"></script>
</body>
</html>