пятница, 7 августа 2020 г.

Пакет suffixarray в Golang

Пакет suffixarray реализует поиск подстроки за логарифмическое время, используя массив суффиксов в памяти.

Пример использования suffixarray:

// создаем индекс для некоторых данных
index := suffixarray.New(data)

// поиск байтового среза s

// список всех индексов, где s встречается в data
offsets1 := index.Lookup(s, -1) 

// список не более 3 индексов, где s встречается в data
offsets2 := index.Lookup(s, 3)

Тип Index

Index реализует массив суффиксов для быстрого поиска подстроки.

type Index struct {
    // содержит отфильтрованные или неэкспортированные поля
}

Функция New

func New(data []byte) *Index

New создает новый Index для data. Время создания индекса составляет O(N) для N = len(data).

Метод Bytes

func (x *Index) Bytes() []byte

Bytes возвращает данные, по которым был создан индекс. Его нельзя изменять.

Метод FindAllIndex

func (x *Index) FindAllIndex(r *regexp.Regexp, n int) (result [][]int)

FindAllIndex возвращает отсортированный список неперекрывающихся совпадений регулярного выражения r, где совпадение - это пара индексов, определяющих совпадающий срез x.Bytes(). Если n < 0, все совпадения возвращаются в последовательном порядке. В противном случае возвращается не более n совпадений, и они могут быть непоследовательными. result равен nil, если совпадений нет или если n == 0.

Пример использования FindAllIndex

package main

import (
    "fmt"
    "index/suffixarray"
    "regexp"
)

func main() {
    index := suffixarray.New([]byte("banana"))
    re, err := regexp.Compile(`an.?`)
    if err != nil {
        fmt.Println(err.Error())
        return
    }
    offsets := index.FindAllIndex(re, -1)
    for _, off := range offsets {
        fmt.Println(off)
    }

}

Вывод:

[1 4]

Метод Lookup

func (x *Index) Lookup(s []byte, n int) (result []int)

Lookup возвращает несортированный список из не более n индексов, в которых байтовая строка s встречается в индексированных данных. Если n < 0, возвращаются все вхождения. result равен nil, если s пусто, s не найдено или n == 0. Время поиска равно O(log(N)*len(s) + len(result)), где N - размер проиндексированных данных.

Пример использования Lookup

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)
    }

}

Вывод:

3
1

Метод Read

func (x *Index) Read(r io.Reader) error

Read считывает индекс из r в x; x не должен быть равен nil.

Метод Write

func (x *Index) Write(w io.Writer) error

Write записывает индекс x в w.

Читайте также:


Labels:

Комментариев нет:

Отправить комментарий