index/suffixarray

  • import "index/suffixarray"
  • 概况
  • 索引
  • 示例

概述

包后缀数组使用内存后缀数组实现对数时间的子串搜索。

使用示例:

// 为某些数据创建索引
index := suffixarray.New(data)

// 查找字节切片s
offsets1 := 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

包文件

Index 为快速子串搜索实现后缀数组。

type Index struct {
        // 包含已过滤或未导出的字段
}
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 main

import (
	"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 。

扫码关注云+社区

领取腾讯云代金券