xsearch

xsearch

Fuzzy search library for Go. Per-field BM25 and Jaccard trigram scoring with optional bloom filter pre-rejection. Index any type. Handle typos, prefix matching, and group fallback — all in-process.

go get github.com/mbow/xsearch

Usage

Implement Searchable on your type:

type Drink struct {
    ID          string
    Name        string
    Category    string
    Ingredients []string
    Tags        map[string][]string
}

func (d Drink) SearchID() string { return d.ID }

func (d Drink) SearchFields() []xsearch.Field {
    fields := []xsearch.Field{
        {Name: "name", Values: []string{d.Name}, Weight: 1.0},
        {Name: "category", Values: []string{d.Category}, Weight: 0.5},
    }
    if len(d.Ingredients) > 0 {
        fields = append(fields, xsearch.Field{
            Name: "ingredients", Values: d.Ingredients, Weight: 0.4,
        })
    }
    for key, vals := range d.Tags {
        fields = append(fields, xsearch.Field{
            Name: key, Values: vals, Weight: 0.3,
        })
    }
    return fields
}

Build and search:

engine, err := xsearch.New(drinks,
    xsearch.WithBloom(100),
    xsearch.WithFallbackField("category"),
    xsearch.WithLimit(20),
)

results := engine.Search("smoky scotch")
for _, r := range results {
    item, _ := engine.Get(r.ID)
    fmt.Printf("%s (score: %.3f)\n", item.Fields[0].Values[0], r.Score)
}

Configuration

External Scoring

Pass a Scorer per search to blend relevance with popularity or business logic:

results := engine.Search("lager", xsearch.WithScoring(scorer))

The library normalizes scorer output per search (max-normalized to [0, 1]) and blends with relevance using alpha. Negative values, NaN, and Inf are clamped to zero.

Prefix Cache

Precompute results for high-traffic queries (typically 1-2 character prefixes):

// Extract prefixes from your data.
var prefixes []string
seen := make(map[string]struct{})
for _, item := range items {
    name := strings.ToLower(item.Name)
    if len(name) >= 1 {
        if _, ok := seen[name[:1]]; !ok { seen[name[:1]] = struct{}{}; prefixes = append(prefixes, name[:1]) }
    }
    if len(name) >= 2 {
        if _, ok := seen[name[:2]]; !ok { seen[name[:2]] = struct{}{}; prefixes = append(prefixes, name[:2]) }
    }
}

engine, err := xsearch.New(items,
    xsearch.WithPrefixCache(prefixes),
)

// Cached queries return in ~30ns with zero heap allocations.
// When WithScoring is used, the cache is bypassed for fresh scored results.
results := engine.Search("b") // cache hit

Snapshots

Build indices once, serialize to CBOR, reload fast:

data, _ := engine.Snapshot()
engine2, _ := xsearch.NewFromSnapshot(data, items)

Snapshots are self-contained CBOR blobs with a version header (XSRC). Build-time index options are stored in the snapshot, including WithUnicodeFold(). Load-time options WithLimit, WithPrefixCache, and WithScopes may still be supplied on restore.

Snapshot version 2 breaks compatibility with older snapshot blobs. Rebuild any existing snapshots before calling NewFromSnapshot.

Bloom Filter

Use standalone or integrated via WithBloom():

bf := xsearch.NewBloom(10000, 100) // 10K items, 100 bits per item
bf.Add("trigram")
bf.MayContain("trigram") // true (no false negatives)
bf.MayContain("absent")  // false (rare false positives)

Scoring Model

Each field is scored independently. Final relevance is the weighted sum:

BM25 path (primary): relevance = sum(bm25(field_i, query) * field_i.Weight)

Jaccard fallback (typos): relevance = sum(jaccard(field_i_trigrams, query_trigrams) * field_i.Weight)

Prefix boosting applies to the highest-weighted field only.

Performance

These numbers are machine-dependent. Refresh this section with make bench-readme after make bench-record, or use make bench-publish.

Generated from profiles/benchmarks/bench-latest.txt via make bench-readme. Metric cells are medians across the recorded samples.

• Commit: 09ff3d0
• Branch: main (dirty)
• Date: 2026-04-09T19:16:04+01:00
• Filter: .
• Count: 5
• Time: 1s
• CPU: 1
• Package: .

Build Engine

Snapshot Encode

Snapshot Load

Component

Search

Parallel Search

License

MIT

Changelog

v0.2.0

• Snapshot format bumped to version 2; rebuild any existing snapshot blobs before calling NewFromSnapshot.
• WithUnicodeFold() is now serialized into snapshots and restored on load, so folded engines round-trip without behavior drift.
• NewFromSnapshot now rejects WithUnicodeFold() as a load-time override because it is part of the persisted snapshot config.

v0.1.0

• Fold(s string) string — exported Unicode NFKD normalization with combining-mark stripping and ligature expansion (œ→oe, æ→ae, ß→ss). Idempotent.
• WithUnicodeFold() Option — index- and query-time accent-insensitive search using Fold. Integrated with WithPrefixCache so prewarm keys hit after folding+normalization.
• Engine.SearchWithFallback(primary, cascade, opts ...SearchOption) ([]Result, int) — runs primary; if empty, walks cascade in order and returns the first non-empty level. Level -1 = primary matched; 0..len(cascade)-1 = cascade index; len(cascade) = no match.
• WithFilter(pred func(id string) bool) SearchOption — per-search predicate applied after scope filtering and before scoring/limit. Prefix-cache fast path is bypassed when a filter is set. Nil filter is zero-overhead.