Documentation
¶
Overview ¶
Package bm25 provides Okapi BM25 ranking for code-aware corpora.
Stability ¶
This package is part of the public import surface of github.com/0xmhha/code-knowledge-graph. The exported API — Scorer, Okapi, NewOkapi, Document, ScoredDoc, Tokenize, and the two default constants — follows semantic versioning:
- Minor releases may add new types, methods, or fields.
- Patch releases fix bugs without changing the API surface.
- The Scorer interface will not gain methods in a minor release; a breaking change to Scorer requires a new major version.
External consumers (ckv, cks) should depend on the Scorer interface and construct via NewOkapi. Direct field access on Okapi (K1, B) is stable for tuning but the unexported fields are not part of the contract.
Typical usage (external consumer) ¶
import "github.com/0xmhha/code-knowledge-graph/pkg/bm25"
scorer := bm25.NewOkapi()
scorer.Index([]bm25.Document{
{ID: "node-1", Tokens: bm25.Tokenize("HandleDeposit")},
{ID: "node-2", Tokens: bm25.Tokenize("processWithdraw")},
})
hits := scorer.TopK(bm25.Tokenize("deposit"), 10)
Package bm25 implements Okapi BM25 ranking for code-aware corpora.
The algorithm is the standard Okapi BM25 formulation (Robertson, Walker 1994) with the conventional smoothing IDF (`log(1 + (N-n+0.5)/(n+0.5))`). The implementation is hand-written in Go from the algorithm description alone — no source copied from any library. Behaviour was cross-checked against two reference implementations:
- github.com/blevesearch/bleve (Apache-2.0) — search/scorer/scorer_term.go
- github.com/dorianbrown/rank_bm25 (Apache-2.0, Python) — bm25.BM25Okapi
Algorithm authors and reference implementations are credited above; this file contains no derivative code from either project.
Index ¶
Constants ¶
const ( DefaultK1 = 1.5 DefaultB = 0.75 )
Default Okapi BM25 hyperparameters. K1 controls term-frequency saturation (higher = more weight to repeated matches); B controls length normalization (0 = ignore length, 1 = full normalization). 1.5 / 0.75 is the most widely cited starting point in the literature and matches both bleve and rank_bm25 defaults.
Variables ¶
This section is empty.
Functions ¶
func Tokenize ¶
Tokenize converts an arbitrary string into BM25 tokens with code-aware splitting. The output preserves the joined identifier (lowercased) AND its sub-words so a query for either form scores. Concretely:
- "parseFile" → ["parsefile", "parse", "file"]
- "HTTPServer" → ["httpserver", "http", "server"]
- "read_file" → ["read_file", "read", "file"]
- "pkg.Type.Method" → ["pkg", "type", "method"]
- "json-rpc/v1" → ["json", "rpc", "v1"]
All tokens are lowercased; tokens of length < 2 are dropped (they add noise without helping rank). Caller-supplied tokens are not deduped — repetition is meaningful to BM25's TF term.
Types ¶
type Document ¶
Document is one indexable record. Tokens are pre-tokenized — call Tokenize for the package's standard code-aware splitter, or supply custom tokens for a domain-specific corpus.
type Okapi ¶
Okapi is the standard BM25Okapi scorer. Concurrent reads (Score, TopK) after a completed Index are safe; do NOT call Index concurrently with a reader. Build once, query many.
func NewOkapi ¶
func NewOkapi() *Okapi
NewOkapi returns a scorer with default hyperparameters. Override K1/B directly on the returned struct before calling Index.
func (*Okapi) Index ¶
Index registers the corpus. Empty input is allowed — the scorer will return 0 for all queries until a non-empty Index call replaces state.
type ScoredDoc ¶
ScoredDoc pairs a document ID with its BM25 score for the most recent query. Score is always >= 0; documents with no matching terms are not returned by TopK.
type Scorer ¶
type Scorer interface {
// Index registers the full corpus. Repeated calls overwrite earlier
// state — Scorer is not append-only.
Index(docs []Document)
// Score returns the BM25 score for one document under one query.
// Returns 0 when docID is unknown or no query term matches.
Score(query []string, docID string) float64
// TopK returns the top-k documents by score, descending. k <= 0
// returns every matching document.
TopK(query []string, k int) []ScoredDoc
}
Scorer is the contract every BM25 implementation in this package satisfies. The two-phase pattern (Index then Score / TopK) lets callers build the corpus once per build and reuse for many queries.
Source Files