GO 前缀数组 index / suffixarray
GO 标准库 suffixarray 模块提供了基于 前缀数组 的子串检索功能 能够在 byte数组 中检索指定子串 并获得其索引下标
创建前缀数组
通过New方法创建一个前缀数组
func New(data []byte) *Index
此外可以通过其Bytes方法 获取原始byte数组
func (x *Index) Bytes() []byte
数据检索
Index对象 上提供了两种检索方法 FindAllIndex 和 Lookup
其中 FindAllIndex 接收一个 正则表达式 并返回长度不超过n的匹配索引列表 n<0 时返回全部结果
func (x *Index) FindAllIndex(r *regexp.Regexp, n int) (result [][]int)
而Lookup方法接收一个 byte列表 返回长度不超过n的匹配索引列表 n<0 时返回全部结果
func (x *Index) Lookup(s []byte, n int) (result []int)
使用实例
package main
import (
"index/suffixarray"
"fmt"
"sort"
)
func main() {
source := []byte("hello world, hello china")
index := suffixarray.New(source)
offsets := index.Lookup([]byte("hello"), -1)
sort.Ints(offsets)
fmt.Printf("%v", offsets)//[0 13]
}
import "index/suffixarray"
包 后缀数组使用内存 后缀数组实现对数时间的子串搜索
使用示例
// 为某些数据创建索引 index := suffixarray.New(data)
// 查找字节切片 soffsets1 := index.Lookup(s, -1)
// 数据中出现s的所有索引的列表 offsets2 := index.Lookup(s, 3) // 最多3个索引的列表 其中s出现在数据中
type Index
func New(data []byte) *Index
func (x *Index) Bytes() []byte
func (x *Index) FindAllIndex(r *regexp.Regexp, n int) (result [][]int)
func (x *Index) Lookup(s []byte, n int) (result []int)
func (x *Index) Read(r io.Reader) error
func (x *Index) Write(w io.Writer) error
示例
Index.Lookup
包文件
qsufsort.go suffixarray.go
type Index
Index 为快速子串搜索实现后缀数组
type Index struct { // 包含已过滤或未导出的字段}
func New
func New(data []byte) *Index
New 为数据创建一个新的索引 对于N = len(data) 索引创建时间为 O(N*log(N))
func (*Index) Bytes
func (x *Index) Bytes() []byte
Bytes 返回索引创建的数据 它不能被修改
func (*Index) FindAllIndex
func (x *Index) FindAllIndex(r *regexp.Regexp, n int) (result [][]int)
FindAllIndex 返回正则表达式r的非重叠匹配的排序列表 其中匹配是指定 x.Bytes()的匹配切片的一对索引
如果 n <0 则所有匹配按照连续顺序返回 否则 最多返回 n 个匹配 并且可能不连续 如果没有匹配 或者如果 n == 0 结果为零
func (*Index) Lookup
func (x *Index) Lookup(s []byte, n int) (result []int)
Lookup 返回索引数据中至多有 n 个索引的未排序列表 其中字节串 s 出现 如果 n <0 则返回所有发生的事件
如果 s 为空 s 未找到或 n == 0 则结果为 nil 查找时间为 O(log(N)*len(s) + len(result))其中 N 是索引数据的大小
示例
package mainimport ("fmt""index/suffixarray")func main() {
index := suffixarray.New([]byte("banana"))
offsets := index.Lookup([]byte("ana"), -1)for _, off := range offsets {
fmt.Println(off)}}
func (*Index) Read
func (x *Index) Read(r io.Reader) error
Read 读取从 r 到 x 的索引;x 不能为零
func (*Index) Write
func (x *Index) Write(w io.Writer) error
Write 将索引 x 写入 w
GO 标准库 suffixarray 模块提供了基于 前缀数组 的子串检索功能 能够在 byte数组 中检索指定子串 并获得其索引下标
创建前缀数组
通过New方法创建一个前缀数组
func New(data []byte) *Index
此外可以通过其Bytes方法 获取原始byte数组
func (x *Index) Bytes() []byte
数据检索
Index对象 上提供了两种检索方法 FindAllIndex 和 Lookup
其中 FindAllIndex 接收一个 正则表达式 并返回长度不超过n的匹配索引列表 n<0 时返回全部结果
func (x *Index) FindAllIndex(r *regexp.Regexp, n int) (result [][]int)
而Lookup方法接收一个 byte列表 返回长度不超过n的匹配索引列表 n<0 时返回全部结果
func (x *Index) Lookup(s []byte, n int) (result []int)
使用实例
package main
import (
"index/suffixarray"
"fmt"
"sort"
)
func main() {
source := []byte("hello world, hello china")
index := suffixarray.New(source)
offsets := index.Lookup([]byte("hello"), -1)
sort.Ints(offsets)
fmt.Printf("%v", offsets)//[0 13]
}
import "index/suffixarray"
包 后缀数组使用内存 后缀数组实现对数时间的子串搜索
使用示例
// 为某些数据创建索引 index := suffixarray.New(data)
// 查找字节切片 soffsets1 := index.Lookup(s, -1)
// 数据中出现s的所有索引的列表 offsets2 := index.Lookup(s, 3) // 最多3个索引的列表 其中s出现在数据中
type Index
func New(data []byte) *Index
func (x *Index) Bytes() []byte
func (x *Index) FindAllIndex(r *regexp.Regexp, n int) (result [][]int)
func (x *Index) Lookup(s []byte, n int) (result []int)
func (x *Index) Read(r io.Reader) error
func (x *Index) Write(w io.Writer) error
示例
Index.Lookup
包文件
qsufsort.go suffixarray.go
type Index
Index 为快速子串搜索实现后缀数组
type Index struct { // 包含已过滤或未导出的字段}
func New
func New(data []byte) *Index
New 为数据创建一个新的索引 对于N = len(data) 索引创建时间为 O(N*log(N))
func (*Index) Bytes
func (x *Index) Bytes() []byte
Bytes 返回索引创建的数据 它不能被修改
func (*Index) FindAllIndex
func (x *Index) FindAllIndex(r *regexp.Regexp, n int) (result [][]int)
FindAllIndex 返回正则表达式r的非重叠匹配的排序列表 其中匹配是指定 x.Bytes()的匹配切片的一对索引
如果 n <0 则所有匹配按照连续顺序返回 否则 最多返回 n 个匹配 并且可能不连续 如果没有匹配 或者如果 n == 0 结果为零
func (*Index) Lookup
func (x *Index) Lookup(s []byte, n int) (result []int)
Lookup 返回索引数据中至多有 n 个索引的未排序列表 其中字节串 s 出现 如果 n <0 则返回所有发生的事件
如果 s 为空 s 未找到或 n == 0 则结果为 nil 查找时间为 O(log(N)*len(s) + len(result))其中 N 是索引数据的大小
示例
package mainimport ("fmt""index/suffixarray")func main() {
index := suffixarray.New([]byte("banana"))
offsets := index.Lookup([]byte("ana"), -1)for _, off := range offsets {
fmt.Println(off)}}
func (*Index) Read
func (x *Index) Read(r io.Reader) error
Read 读取从 r 到 x 的索引;x 不能为零
func (*Index) Write
func (x *Index) Write(w io.Writer) error
Write 将索引 x 写入 w
尊贵的董事大人
英文标题不为空时 视为本栏投稿
需要关键字 描述 英文标题