trigram

README

go-trigram: simple trigram index for searching sets of strings

godoc: http://godoc.org/github.com/dgryski/go-trigram

Documentation

Overview

Package trigram is a simple trigram index

Index

• type DocID
• type Index
  • func NewIndex(docs []string) Index
  • func (idx Index) Add(s string) DocID
  • func (idx Index) AddTrigrams(ts []T) DocID
  • func (idx Index) Delete(s string, id DocID)
  • func (idx Index) Filter(docs []DocID, ts []T) []DocID
  • func (idx Index) FilterOr(docs []DocID, tss [][]T) []DocID
  • func (idx Index) Insert(s string, id DocID)
  • func (idx Index) InsertTrigrams(ts []T, id DocID)
  • func (idx Index) Prune(pct float64) int
  • func (idx Index) Query(s string) []DocID
  • func (idx Index) QueryTrigrams(ts []T) []DocID
  • func (idx Index) Sort()
• type T
  • func Extract(s string, trigrams []T) []T
  • func ExtractAll(s string, trigrams []T) []T
  • func (t T) String() string

Types

type DocID

type DocID uint32

DocID is a document ID

type Index

type Index map[T][]DocID

Index is a trigram index

func NewIndex

func NewIndex(docs []string) Index

NewIndex returns an index for the strings in docs

func (Index) Add

func (idx Index) Add(s string) DocID

Add adds a new string to the search index

func (Index) AddTrigrams

func (idx Index) AddTrigrams(ts []T) DocID

AddTrigrams adds a set of trigrams to the search index

func (Index) Delete

func (idx Index) Delete(s string, id DocID)

Delete removes a document from the index

func (Index) Filter

func (idx Index) Filter(docs []DocID, ts []T) []DocID

Filter removes documents that don't contain the specified trigrams

func (Index) FilterOr

func (idx Index) FilterOr(docs []DocID, tss [][]T) []DocID

FilterOr removes documents that don't contain any of the list of specified trigrams in other words, it's the union of the results of invidial filters

func (Index) Insert

func (idx Index) Insert(s string, id DocID)

Insert adds a string with a given document ID

func (Index) InsertTrigrams

func (idx Index) InsertTrigrams(ts []T, id DocID)

InsertTrigrams adds a set of trigrams with a given document ID

func (Index) Prune

func (idx Index) Prune(pct float64) int

Prune removes all trigrams that are present in more than the specified percentage of the documents.

func (Index) Query

func (idx Index) Query(s string) []DocID

Query returns a list of document IDs that match the trigrams in the query s

func (Index) QueryTrigrams

func (idx Index) QueryTrigrams(ts []T) []DocID

QueryTrigrams returns a list of document IDs that match the trigram set ts

func (Index) Sort

func (idx Index) Sort()

Sort ensures all the document IDs are in order.

type T

type T uint32

T is a trigram

const TAllDocIDs T = 0xFFFFFFFF

a special (and invalid) trigram that holds all the document IDs

func Extract

func Extract(s string, trigrams []T) []T

Extract returns a list of all the unique trigrams in s

func ExtractAll

func ExtractAll(s string, trigrams []T) []T

ExtractAll returns a list of all the trigrams in s

func (T) String

func (t T) String() string