Documentation
¶
Overview ¶
Package lexical is tier 0 word search: an in-memory index that ranks entities by field-weighted BM25 over the words of their text.
Tokens is the one tokenizer: text written into an index and the text of a query go through it alone, so a query word and an indexed word agree when they come from the same written word, its plural (an acronym's too: "IDs" and "ids" meet "id"), or one part of a split identifier. Folding the plural also joins a few words that are not plurals: "its" meets "it", and a three-letter acronym ending in "s" meets its first two letters ("TLS" and "tl", "CAS" and "CA").
ParseQuery reads a query of plain words, "quoted phrases" and -excluded terms. Phrases and exclusions decide which entities match; plain and phrase words decide their order.
The package is pure: it imports no NATS client and reads no storage.
Index ¶
Examples ¶
Constants ¶
const NameWeight = 2
NameWeight is how many times a word in a document's Name counts against the same word in its Body, both in term frequency and in length.
Variables ¶
var ( // ErrInvalidEntityID is returned by Put for an ID that is not a canonical // six-part entity ID, so every held entity can be matched by scope. ErrInvalidEntityID = errors.New("lexical: invalid entity ID") // ErrInvalidScope is returned by Search for a malformed scope prefix. ErrInvalidScope = errors.New("lexical: invalid scope prefix") // ErrInvalidLimit is returned by Search for a limit below 1. ErrInvalidLimit = errors.New("lexical: limit must be at least 1") )
var ( // ErrEmptyQuery is returned by ParseQuery for a query left with no plain // word and no phrase after tokenizing. ErrEmptyQuery = errors.New("lexical: query has nothing to search for") // ErrReservedSyntax is returned by ParseQuery for syntax kept for a later // query form, so that adding the form changes no answer given today. ErrReservedSyntax = errors.New("lexical: query uses syntax reserved for a later query form") // ErrQueryTooLong is returned by ParseQuery for a query holding more than // graph.MaxSearchTerms distinct words. ErrQueryTooLong = errors.New("lexical: query holds too many distinct words") )
Functions ¶
func Tokens ¶
Tokens returns the words of text in order, repeats kept.
A word starts as a run of Unicode letters and digits, so "graph.query.status" and "pump-7" split at their punctuation and one-letter words such as "v" stay. A run that ends in a lower-case "s" right after two or more capitals is an acronym in the plural: the "s" goes and the capitals stay one part, so "IDs" gives "id" and "URLs" gives "url". Only the end of a run counts, because inside one the same letters are as often an acronym followed by a word ("EntityIDIsTerminated"), so "EntityIDsByType" splits by the rules below. A run splits again where an identifier changes case: at a lower-case letter followed by a capital, and before the last capital of a run of capitals followed by lower case, so "withRetry" gives "with" and "retry" and "HTTPServer" gives "http" and "server". The joined form ("withretry") is not a word. Each part is lower-cased and its plural folded to the singular ("services" to "service", "caches" to "cach", like "cache", "ids" to "id"). A word is dropped when it or its fold is a stopword, so "wills" goes with "will" and "ins" with "in", or when its fold is over 32 bytes.
Tokenizing the words Tokens returns, joined by spaces, gives them back unchanged.
Types ¶
type Document ¶
Document is the text an entity is found by. Words in Name weigh NameWeight times as much as words in Body.
type Index ¶
type Index struct {
// contains filtered or unexported fields
}
Index ranks the entities it holds by field-weighted BM25 over their words. It is safe for concurrent use: a search sees each Put or Delete whole or not at all.
It holds each entity and each word once, under a number, and refers to them everywhere else by that number: four bytes in place of a string.
Example ¶
package main
import (
"errors"
"fmt"
"github.com/c360studio/semengine/graph/lexical"
)
func main() {
ix := lexical.NewIndex()
docs := map[string]lexical.Document{
"acme.ops.docs.runbook.page.restart": {
Name: "Restart the cooling pump",
Body: "Stop it with docker compose down, then call withRetry until the pump reports ready.",
},
"acme.ops.docs.runbook.page.readings": {
Name: "Pump telemetry",
Body: "Pressure and flow readings for pump-7, sampled every second.",
},
}
for id, doc := range docs {
if err := ix.Put(id, doc); err != nil {
fmt.Println(err)
return
}
}
for _, text := range []string{`pump retry`, `pump -telemetry`, `"compose down"`, `withretry`, `pump*`} {
q, err := lexical.ParseQuery(text)
if errors.Is(err, lexical.ErrReservedSyntax) {
fmt.Printf("%s: reserved syntax\n", text)
continue
}
if err != nil {
fmt.Println(err)
return
}
res, err := ix.Search(q, lexical.Options{Limit: 10})
if err != nil {
fmt.Println(err)
return
}
fmt.Printf("%s: %d matched", text, res.Matched)
for _, hit := range res.Hits {
fmt.Printf(" %s", hit.EntityID)
}
fmt.Println()
}
}
Output: pump retry: 2 matched acme.ops.docs.runbook.page.restart acme.ops.docs.runbook.page.readings pump -telemetry: 1 matched acme.ops.docs.runbook.page.restart "compose down": 1 matched acme.ops.docs.runbook.page.restart withretry: 0 matched pump*: reserved syntax
func (*Index) Delete ¶
Delete removes entityID. It does nothing for an entity the index does not hold.
func (*Index) Put ¶
Put replaces everything entityID held with the words of doc. A document with no words removes the entity. An ID that is not a canonical entity ID is refused with an error matching ErrInvalidEntityID.
func (*Index) Search ¶
Search scores every entity in scope that holds one of the query's plain or phrase words, every one of its phrases and none of its excluded terms, and returns the best opts.Limit of them. A score sums BM25F over the distinct plain and phrase words; excluded words never add to it. The entity count, each word's entity count and the average length are those of the entities held when the search runs; scope filters before the limit and never changes a score.
type Options ¶
Options bound a search. An empty Scope searches every entity; otherwise only entities under one of its ID prefixes are matched (an empty prefix matches every entity). Limit is the most hits returned, at least 1.
type Query ¶
type Query struct {
// contains filtered or unexported fields
}
Query is what Search looks for. ParseQuery builds one; the zero Query matches nothing.
func ParseQuery ¶
ParseQuery reads a query typed by a person or passed on by a product.
Text in double quotes is a phrase, and is literal: only tokenizing applies inside quotes. A quote left open ends at the end of the text. A term outside quotes starting with a single "-" followed by a letter, a digit or a quote is excluded: "go test -race" excludes "race", while "--force" is the word "force". Everything else is plain words. Every form is tokenized as documents are, and a phrase or excluded term left with no word is ignored.
A term outside quotes starting with "name:" or "body:" followed by more text, or ending in a letter or digit followed by "*", is refused with an error matching ErrReservedSyntax, whose message names the term and says to quote it. A term that also starts with "*" is emphasis, as in "*bold*", and is read as its words. Every other mark, "~" among them, separates words, so "HEAD~" is the word "head". A query with no plain word and no phrase is refused with ErrEmptyQuery, and one holding more than graph.MaxSearchTerms distinct words, plain, phrase and excluded counted together, with ErrQueryTooLong.