lexical

package
v0.1.0-alpha.5 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 16, 2026 License: MIT Imports: 11 Imported by: 0

README

graph/lexical

Word search over the text of graph entities. An Index holds, for each entity, the words of a short name and a longer body, and ranks the entities that match a query with BM25: a standard scoring formula that rewards a word that is frequent in the entity and rare across all entities, and that discounts long texts. Words in the name count twice (NameWeight). The index is in memory and needs no external provider. The package imports no NATS client and reads no storage: the caller decides what text each entity has and writes it with Put.

The graph-lexical component (processor/graph-lexical) fills an index from ENTITY_STATES and answers graph.lexical.query.search with it; its README covers configuration, memory and restart cost. A product that wants something else builds an Index and keeps it current itself. Nothing persists: after a restart the caller writes the entities again, as the component does by reading the bucket.

Who word search helps

Word search helps only entities that have text: documents, notes, descriptions, names. An entity whose facts are numbers, such as sensor or drone telemetry, gains nothing from it: there are no words to match, and a reading such as 41.7 is one more word, not a quantity.

Such entities are reached through the structure of the graph instead, by the read requests graph-ingest, graph-index and graph-query answer today:

  • By ID prefix: every entity whose ID starts with given parts, for example every entity of one source (prefix).
  • By predicate: every entity holding a predicate, such as sensor.reading.temperature, with counts per predicate and AND or OR over several predicates (predicate, predicateList, predicateStats, predicateCompound).
  • By relationship: the entities one entity points to, and those pointing to it (outgoing, incoming, relationships), and a walk outward from one entity (pathSearch).
  • By name and by alias: an entity's name or one of its aliases (byName, alias, entityByAlias).
  • By group: graph/clustering groups entities by the first parts of their IDs; the grouping needs no text.

Two limits apply to numeric data today:

  • The predicate request can filter on a value, but it matches the value written as a string, exactly: a stored 85 matches "85" and nothing else. Nothing offers a numeric range, such as "temperature above 80".
  • The time-range request (graph.temporal.query.range) and the bounding-box request (graph.spatial.query.bounds) are declared, but nothing in this repository answers them, so graph-query's temporal and spatial requests, which forward to them, cannot be answered either.

Basic use

ix := lexical.NewIndex()
err := ix.Put("acme.ops.docs.runbook.page.restart", lexical.Document{
    Name: "Restart the cooling pump",
    Body: "Stop it with docker compose down, then call withRetry until the pump reports ready.",
})
// ...
q, err := lexical.ParseQuery(`pump -telemetry`)
// ...
res, err := ix.Search(q, lexical.Options{Limit: 10})
for _, hit := range res.Hits {
    fmt.Println(hit.EntityID, hit.Score)
}

ExampleIndex in example_test.go writes two entities and runs five queries; go test checks its 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

What is here

Name What it does
NewIndex, Index An empty index; safe for concurrent use, and a search sees each write whole or not at all
Document The text an entity is found by: Name and Body
Index.Put Replaces everything an entity held with the words of a document; a document with no words removes the entity. Refuses an ID that is not a canonical six-part entity ID (ErrInvalidEntityID)
Index.Delete, Index.Len Removes an entity; the number of entities held
ParseQuery, Query Reads a query (rules below); the zero Query matches nothing
Query.Excluded The excluded terms, each as its words, so a caller can say which words removed entities
Index.Search, Options The best Limit hits (at least 1, else ErrInvalidLimit) among entities under one of the Scope ID prefixes (all entities when Scope is empty; a malformed prefix is ErrInvalidScope)
Result, Hit Hits ordered by score, then by entity ID; Matched counts every match in scope before the limit
Tokens The one tokenizer, used for documents and queries alike
NameWeight How many times a name word counts against a body word: 2

How text becomes words

Tokens splits text at everything that is not a letter or a digit, so graph.query.status gives graph, query and status, and pump-7 gives pump and 7. A run also splits where an identifier changes case: withRetry splits into with and retry, HTTPServer into http and server. The joined form is not kept, so withretry finds nothing; search for retry or withRetry. An acronym in the plural keeps its capitals together: a run that ends in a lower-case s right after two or more capitals drops the s, so IDs gives id, URLs gives url and UUIDs gives uuid. This applies only at the end of a run; EntityIDsByType gives entity, i, ds and type, because inside a run the same letters are as often an acronym followed by a word, as in EntityIDIsTerminated.

Words are lower-cased and plurals folded to the singular (services to service, ids to id, prs to pr). The plain rule drops a final s, but not us or ss, from a word of 3 bytes or more, so os and ms keep theirs and bus and class stay as written. Because the rule cannot tell a plural from a word that only ends in s, it also joins some words that are not plurals:

  • its meets it;
  • a three-letter acronym ending in s meets its first two letters: TLS gives tl, CAS (compare-and-swap) meets CA (certificate authority), and ios meets Go's io;
  • a duration meets its bare number (10s and 10);
  • a two-letter stop word with an s is dropped like the stop word: ins goes with in, and DOS gives no word, so a query of only DOS is refused with ErrEmptyQuery.

A short list of stop words (the, and, with and the like) is dropped, and so is any word longer than 32 bytes after folding, which in practice is hex such as a commit hash.

Query rules

  • Plain words rank the results. An entity matches when it holds at least one of them (or a phrase, below); entities holding more of them, and rarer ones, rank higher.
  • A phrase is text in double quotes. Its words must stand next to each other, in order, within the name or within the body. Quoting makes any text literal: only tokenizing applies inside quotes, so "name:pump" or "-race" is searched as words. Because stop words are dropped first, "out of memory" also matches "out the memory". A quote left open ends at the end of the query.
  • An exclusion is a term outside quotes starting with a single - followed by a letter, a digit or a quote. It removes every entity holding it, and adds nothing to a score. So go test -race excludes race, while --force is the plain word force. To search for a flag such as -race, quote it.
  • Reserved syntax is refused with ErrReservedSyntax, so a later query form can give it a meaning without changing an answer given today: a term outside quotes that starts with name: or body: followed by more text, or that ends in a letter or digit followed by * (pump*). The error names the term and says to quote it, which searches it as text. A term that also starts with * is emphasis, so *bold* is the word bold. Every other mark separates words: HEAD~ is the word head.
  • A query with no plain word and no phrase left after tokenizing (only stop words, punctuation or exclusions) is refused with ErrEmptyQuery. A query with more than graph.MaxSearchTerms (32) distinct words, plain, phrase and excluded counted together, is refused with ErrQueryTooLong.

How good the ranking is

TestScorecardHoldsItsFloor asks 500 known-item questions (each has one right section as its answer) of 2,000 sections of this repository's own Markdown, frozen under testdata/scorecard/. The index puts the right answer in the first ten hits for 56.0% of them, and the test fails below 55.0%. A plain BM25 ranker over the body alone, using the tier-0 embedder's tokenizer, scored 52.6% on the same questions. That ranker is not part of the package or its tests; its source and how to rerun it are in 2.4-reference.go.txt and 2.4.md. The figures say how the index does on this repository's prose, not on any other text.

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

View Source
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

View Source
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")
)
View Source
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

func Tokens(text string) []string

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

type Document struct {
	Name string
	Body string
}

Document is the text an entity is found by. Words in Name weigh NameWeight times as much as words in Body.

type Hit

type Hit struct {
	EntityID string
	Score    float64
}

Hit is one entity a search found, with its score.

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 NewIndex

func NewIndex() *Index

NewIndex returns an empty index.

func (*Index) Delete

func (ix *Index) Delete(entityID string)

Delete removes entityID. It does nothing for an entity the index does not hold.

func (*Index) Len

func (ix *Index) Len() int

Len is the number of entities the index holds.

func (*Index) Put

func (ix *Index) Put(entityID string, doc Document) error

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

func (ix *Index) Search(q Query, opts Options) (Result, error)

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

type Options struct {
	Scope []string
	Limit int
}

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

func ParseQuery(text string) (Query, error)

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.

func (Query) Excluded

func (q Query) Excluded() [][]string

Excluded returns the query's excluded terms, each as its words in order, in the order the query gave them, so a caller can say which words removed entities. The slices are the caller's own.

type Result

type Result struct {
	Hits    []Hit
	Matched int
}

Result is a search's answer: the best hits, ordered by score and then by entity ID, and the number of entities matched in scope before the limit.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL