BM25 Search¶

BM25 (Best Matching 25) is a probabilistic retrieval function for ranking documents based on keyword matching. It's fast, requires no external dependencies, and works well for exact term matching.

Overview¶

BM25 uses term frequency and inverse document frequency to score documents:

score(D, Q) = Σ IDF(qi) × (f(qi, D) × (k1 + 1)) / (f(qi, D) + k1 × (1 - b + b × |D|/avgdl))

Where:

f(qi, D) = frequency of term qi in document D
|D| = document length
avgdl = average document length
k1 = term frequency saturation (default: 1.2)
b = length normalization (default: 0.75)

Quick Start¶

import "github.com/plexusone/omniretrieve/bm25"

// Create index
index := bm25.NewIndex()

// Add documents
index.Add("doc1", "The quick brown fox jumps over the lazy dog")
index.Add("doc2", "A fast red fox leaps across the sleepy hound")
index.Add("doc3", "The dog barks loudly at the mailman")

// Search
results := index.Search("quick fox", 5)

for _, r := range results {
    fmt.Printf("%.3f: %s\n", r.Score, r.ID)
}
// Output:
// 0.847: doc1
// 0.623: doc2

Configuration¶

index := bm25.NewIndex(bm25.Config{
    K1: 1.2,  // Term frequency saturation
    B:  0.75, // Length normalization
})

Parameters¶

Parameter	Default	Description
`K1`	1.2	Controls term frequency saturation. Higher values give more weight to term frequency.
`B`	0.75	Controls length normalization. 0 = no normalization, 1 = full normalization.

Tuning Guidelines¶

Scenario	K1	B
Short documents	1.2-1.5	0.5-0.75
Long documents	0.8-1.2	0.75-1.0
Varying lengths	1.2	0.75
Uniform lengths	1.5	0.0

API Reference¶

Creating an Index¶

// Default configuration
index := bm25.NewIndex()

// Custom configuration
index := bm25.NewIndex(bm25.Config{
    K1: 1.5,
    B:  0.5,
})

Adding Documents¶

// Add single document
index.Add("doc1", "Document content here")

// Add multiple documents
docs := map[string]string{
    "doc1": "First document",
    "doc2": "Second document",
    "doc3": "Third document",
}
for id, content := range docs {
    index.Add(id, content)
}

Searching¶

// Search with limit
results := index.Search("search query", 10)

// Results are sorted by score (highest first)
for _, r := range results {
    fmt.Printf("ID: %s, Score: %.3f\n", r.ID, r.Score)
}

Removing Documents¶

index.Remove("doc1")

Index Statistics¶

stats := index.Stats()
fmt.Printf("Documents: %d\n", stats.NumDocuments)
fmt.Printf("Terms: %d\n", stats.NumTerms)
fmt.Printf("Avg length: %.1f\n", stats.AvgDocLength)

Document Structure¶

type Document struct {
    ID        string
    Content   string
    TermFreqs map[string]int
    Length    int
}

type ScoredDocument struct {
    ID    string
    Score float64
}

Text Processing¶

BM25 applies these text processing steps:

Lowercasing - Convert to lowercase
Tokenization - Split on whitespace and punctuation
Stopword removal - (Optional) Remove common words

Custom Tokenization¶

index := bm25.NewIndex(bm25.Config{
    Tokenizer: func(text string) []string {
        // Custom tokenization logic
        return strings.Fields(strings.ToLower(text))
    },
})

Performance¶

Complexity¶

Operation	Time Complexity
Add document	O(n) where n = terms
Remove document	O(n)
Search	O(q × d) where q = query terms, d = docs with term

Memory Usage¶

// Approximate memory per document:
// - Term frequencies: ~100-500 bytes
// - Document metadata: ~50 bytes
// - Inverted index entry: ~20 bytes per unique term

Benchmarks¶

BenchmarkAdd-8         100000      12034 ns/op
BenchmarkSearch-8       50000      28456 ns/op
BenchmarkRemove-8      200000       8912 ns/op

Use Cases¶

Document Search¶

// Build index from files
for _, file := range files {
    content, _ := os.ReadFile(file)
    index.Add(file, string(content))
}

// Search
results := index.Search("error handling golang", 10)

Autocomplete¶

// Use prefix matching for autocomplete
func autocomplete(index *bm25.Index, prefix string, limit int) []string {
    // Search with prefix
    results := index.Search(prefix, limit*2)

    // Filter to matches starting with prefix
    var suggestions []string
    for _, r := range results {
        if strings.HasPrefix(strings.ToLower(r.ID), prefix) {
            suggestions = append(suggestions, r.ID)
        }
    }
    return suggestions[:min(limit, len(suggestions))]
}

Log Search¶

// Index log entries
for i, line := range logLines {
    index.Add(fmt.Sprintf("line-%d", i), line)
}

// Find error messages
results := index.Search("error exception failed", 20)

Integration with Hybrid Search¶

BM25 works best when combined with vector search:

import (
    "github.com/plexusone/omniretrieve/bm25"
    "github.com/plexusone/omniretrieve/hybrid"
)

bm25Index := bm25.NewIndex()
// ... add documents

searcher := hybrid.NewSearcher(hybrid.Config{
    BM25Index: bm25Index,
    Alpha:     0.5, // 50% BM25, 50% vector
})