README
¶
hyb
Package hyb implements the HYB structure described in Type Less, Find More: Fast Autocompletion Search with a Succinct Index by Holger Bast and Ingmar Weber. It provides an index which gives the word completions of the last query word and returns the best hits for any of those completions.
Requirements
This package uses SIMD-BP128 integer encoding and decoding, so it requires an x86_64/AMD64 CPU that supports SSE2 instructions.
Installation
go get github.com/robskie/hyb
Usage
// Sample document structure
type Doc struct {
ID int
Keywords []string
Rank int
}
// Create a builder and add documents to it
builder := hyb.NewBuilder()
for _, d := range docs {
builder.Add(d.ID, d.Keywords, d.Rank)
}
// Build the index
index := builder.Build()
// Search the index
result := &hyb.Result{}
query := strings.Fields("abc")
index.Search(query, result)
// Get the top 10 hits
hits := result.TopHits(10)
for hits.Next() {
id := hits.ID()
}
// Get the top 5 completions
comps := result.TopCompletions(5)
for comps.Next() {
c := comps.Completion()
}
API Reference
Godoc documentation can be found here.
Benchmarks
The machine used in this benchmark is a Core i5 at 2.3GHz. The test index contains 1159741 postings taken from 357007 movie titles. The benchmark is done by choosing a random movie and taking all its prefixes and using those as query parameters. For example, given the movie, "Alien", the resulting queries would be "A", "Al", "Ali", "Alie", and "Alien" in that order.
You can run this benchmark on your machine by typing this command
go test github.com/robskie/hyb -bench=.* in terminal.
BenchmarkIndexSearch-4 5000 386297 ns/op
Documentation
¶
Overview ¶
Package hyb implements the HYB structure described in the paper — Type Less, Find More: Fast Autocompletion Search with a Succinct Index by Holger Bast and Ingmar Weber. It provides an index which gives the word completions of the last query word and returns the best hits for any of those completions.
See https://people.mpi-inf.mpg.de/~bast/papers/autocompletion-sigir.pdf for more details.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Builder ¶
type Builder struct {
// contains filtered or unexported fields
}
Builder creates a searchable index from the added documents.
type Completion ¶
Completion represents the completions of the last query word.
type Completions ¶
type Completions struct {
// contains filtered or unexported fields
}
Completions iterates over the completions of the last query word.
func (*Completions) Completion ¶
func (c *Completions) Completion() Completion
Completion returns the next word completion.
func (*Completions) Next ¶
func (c *Completions) Next() bool
Next increments the iterator to the next completion. It returns false if there are no more results to go through.
type Hits ¶
type Hits struct {
// contains filtered or unexported fields
}
Hits iterates over the result of a search.
type Index ¶
type Index struct {
// contains filtered or unexported fields
}
Index represents a group of searchable documents.
func NewIndex ¶
func NewIndex() *Index
NewIndex returns an empty index. Call Index.Read to populate it.
type Result ¶
type Result struct {
// contains filtered or unexported fields
}
Result contains the search result.
func (*Result) Completions ¶
func (r *Result) Completions() *Completions
Completions returns all word completions of the last query word sorted by decreasing number of hits.
func (*Result) TopCompletions ¶
func (r *Result) TopCompletions(k int) *Completions
TopCompletions returns the top k completions of the last query word sorted by decreasing number of hits.
Source Files