Documentation
¶
Overview ¶
Package index implements an inverted index for full-text search
═══════════════════════════════════════════════════════════════════════════════ WHAT IS AN INVERTED INDEX? ═══════════════════════════════════════════════════════════════════════════════ An inverted index is like the index at the back of a book, but for search engines.
Example: Given these documents:
Doc 1: "the quick brown fox" Doc 2: "the lazy dog" Doc 3: "quick brown dogs"
The inverted index would look like:
"quick" → [Doc1:Pos1, Doc3:Pos0] "brown" → [Doc1:Pos2, Doc3:Pos1] "fox" → [Doc1:Pos3] "lazy" → [Doc2:Pos1] "dog" → [Doc2:Pos2] "dogs" → [Doc3:Pos2]
═══════════════════════════════════════════════════════════════════════════════
Index ¶
- Constants
- Variables
- func AllOf(index *InvertedIndex, terms ...string) *roaring.Bitmap
- func Analyze(text string) []string
- func AnalyzeWithConfig(text string, config AnalyzerConfig) []string
- func AnyOf(index *InvertedIndex, terms ...string) *roaring.Bitmap
- func TermExcluding(index *InvertedIndex, include, exclude string) *roaring.Bitmap
- type AnalyzerConfig
- type BM25Parameters
- type DocumentStats
- type IndexOption
- type InvertedIndex
- func (idx *InvertedIndex) Decode(data []byte) error
- func (idx *InvertedIndex) Encode() ([]byte, error)
- func (idx *InvertedIndex) FindAllPhrases(query string, startPos Position) [][]Position
- func (idx *InvertedIndex) First(token string) (Position, error)
- func (idx *InvertedIndex) Index(docID uint32, document string, opts ...IndexOption)
- func (idx *InvertedIndex) Last(token string) (Position, error)
- func (idx *InvertedIndex) Next(token string, currentPos Position) (Position, error)
- func (idx *InvertedIndex) NextCover(tokens []string, startPos Position) []Position
- func (idx *InvertedIndex) NextPhrase(query string, startPos Position) []Position
- func (idx *InvertedIndex) Previous(token string, currentPos Position) (Position, error)
- func (idx *InvertedIndex) RankBM25(query string, maxResults int) []Match
- func (idx *InvertedIndex) RankProximity(query string, maxResults int) []Match
- func (idx *InvertedIndex) Upsert(docID uint32, document string, opts ...IndexOption)
- type Iterator
- type Match
- type Node
- type Position
- type QueryBuilder
- func (qb *QueryBuilder) And() *QueryBuilder
- func (qb *QueryBuilder) Execute() *roaring.Bitmap
- func (qb *QueryBuilder) ExecuteWithBM25(maxResults int) []Match
- func (qb *QueryBuilder) Group(fn func(*QueryBuilder)) *QueryBuilder
- func (qb *QueryBuilder) Not() *QueryBuilder
- func (qb *QueryBuilder) Or() *QueryBuilder
- func (qb *QueryBuilder) Phrase(phrase string) *QueryBuilder
- func (qb *QueryBuilder) Term(term string) *QueryBuilder
- type QueryOp
- type SkipList
- func (sl *SkipList) Delete(key Position) bool
- func (sl *SkipList) Find(key Position) (Position, error)
- func (sl *SkipList) FindGreaterThan(key Position) (Position, error)
- func (sl *SkipList) FindLessThan(key Position) (Position, error)
- func (sl *SkipList) Insert(key Position)
- func (sl *SkipList) Iterator() *Iterator
- func (sl *SkipList) Last() Position
- func (sl *SkipList) Search(key Position) (*Node, [MaxHeight]*Node)
Constants ¶
const MaxHeight = 32 // Maximum tower height (supports billions of elements)
Variables ¶
var ( ErrNoPostingList = errors.New("no posting list exists for token") ErrNoNextElement = errors.New("no next element found") ErrNoPrevElement = errors.New("no previous element found") )
═══════════════════════════════════════════════════════════════════════════════ ERROR DEFINITIONS ═══════════════════════════════════════════════════════════════════════════════
var ( EOF = math.MaxInt // End Of File sentinel for Offset BOF = math.MinInt // Beginning Of File sentinel for Offset )
═══════════════════════════════════════════════════════════════════════════════ SENTINEL VALUES ═══════════════════════════════════════════════════════════════════════════════ We use MaxUint32 and 0 (with a flag) as boundary markers. Since DocID is now uint32, we use a separate sentinel type.
WHY KEEP int FOR Offset? ------------------------- Offsets are word positions within a document — they never need to be document IDs, so they stay as int with MinInt/MaxInt sentinels.
var ( ErrKeyNotFound = errors.New("key not found") ErrNoElementFound = errors.New("no element found") )
var ( BOFDocument = Position{DocumentID: 0, Offset: BOF} // Before all documents EOFDocument = Position{DocumentID: math.MaxUint32, Offset: EOF} // After all documents )
Sentinel positions for convenience
Functions ¶
func AllOf ¶
func AllOf(index *InvertedIndex, terms ...string) *roaring.Bitmap
AllOf finds documents containing ALL of the given terms (AND)
func Analyze ¶
Analyze transforms raw text into searchable tokens using the default pipeline
This is the main entry point for text analysis. It applies all filters in sequence: 1. Tokenization 2. Lowercasing 3. Stopword filtering 4. Length filtering 5. Stemming
Example:
tokens := Analyze("The quick brown fox jumps over the lazy dog")
// Returns: ["quick", "brown", "fox", "jump", "lazi", "dog"]
func AnalyzeWithConfig ¶
func AnalyzeWithConfig(text string, config AnalyzerConfig) []string
AnalyzeWithConfig transforms text using a custom configuration
This allows fine-grained control over the analysis pipeline.
Example:
config := AnalyzerConfig{MinTokenLength: 3, EnableStemming: false}
tokens := AnalyzeWithConfig("The quick brown fox", config)
func AnyOf ¶
func AnyOf(index *InvertedIndex, terms ...string) *roaring.Bitmap
AnyOf finds documents containing ANY of the given terms (OR)
func TermExcluding ¶
func TermExcluding(index *InvertedIndex, include, exclude string) *roaring.Bitmap
TermExcluding finds documents with a term but excluding another
Types ¶
type AnalyzerConfig ¶
type AnalyzerConfig struct {
MinTokenLength int // Minimum token length to keep (default: 2)
EnableStemming bool // Whether to apply stemming (default: true)
EnableStopwords bool // Whether to remove stopwords (default: true)
}
AnalyzerConfig holds configuration options for text analysis
This allows customization of the analysis pipeline without modifying code. Future enhancements could add language support, custom stopwords, etc.
func DefaultConfig ¶
func DefaultConfig() AnalyzerConfig
DefaultConfig returns the standard analyzer configuration
type BM25Parameters ¶
type BM25Parameters struct {
K1 float64 // Term frequency saturation (typical: 1.2-2.0)
B float64 // Length normalization (typical: 0.75)
}
BM25Parameters holds the tuning parameters for BM25 algorithm
func DefaultBM25Parameters ¶
func DefaultBM25Parameters() BM25Parameters
DefaultBM25Parameters returns the standard BM25 parameters
type DocumentStats ¶
type DocumentStats struct {
DocID uint32 // Document identifier
Length int // Number of terms in the document
TermFreqs map[string]int // How many times each term appears
}
DocumentStats stores statistics about a single document. DocID is uint32 to match the index-wide convention.
type IndexOption ¶
type IndexOption func(*indexOptions)
IndexOption is a functional option for Index / Upsert calls.
func WithoutAnalyzer ¶
func WithoutAnalyzer() IndexOption
WithoutAnalyzer disables text analysis for a single Index/Upsert call. The document is stored as a single token exactly as provided — no lowercasing, no stop-word removal, no stemming.
Useful when documents are already pre-processed, contain structured identifiers, or when you need exact-match behaviour without any normalization.
Example:
idx.Index(42, "SKU-9021-XL", iskra.WithoutAnalyzer()) idx.Upsert(42, "SKU-9021-XL", iskra.WithoutAnalyzer())
type InvertedIndex ¶
type InvertedIndex struct {
// DOCUMENT-LEVEL STORAGE (for fast document lookups and boolean queries)
DocBitmaps map[string]*roaring.Bitmap // Term → Bitmap of document IDs
// POSITION-LEVEL STORAGE (for phrase search, proximity)
PostingsList map[string]SkipList // Term → Positions
// BM25 data
DocStats map[uint32]DocumentStats // DocID → statistics
TotalDocs int
TotalTerms int64
BM25Params BM25Parameters
// contains filtered or unexported fields
}
InvertedIndex is the main search index. DocStats and all DocID references use uint32.
func NewInvertedIndex ¶
func NewInvertedIndex() *InvertedIndex
NewInvertedIndex creates a new empty inverted index
func (*InvertedIndex) Decode ¶
func (idx *InvertedIndex) Decode(data []byte) error
Decode deserializes binary data back into an inverted index
func (*InvertedIndex) Encode ¶
func (idx *InvertedIndex) Encode() ([]byte, error)
Encode serializes the inverted index to binary format
func (*InvertedIndex) FindAllPhrases ¶
func (idx *InvertedIndex) FindAllPhrases(query string, startPos Position) [][]Position
FindAllPhrases finds ALL occurrences of a phrase in the entire index
func (*InvertedIndex) First ¶
func (idx *InvertedIndex) First(token string) (Position, error)
First returns the first occurrence of a token in the index
func (*InvertedIndex) Index ¶
func (idx *InvertedIndex) Index(docID uint32, document string, opts ...IndexOption)
Index adds a document to the inverted index.
By default the full analysis pipeline is applied (tokenization, lowercasing, stop-word removal, stemming). Pass WithoutAnalyzer() to skip all analysis and store the document as a single raw token.
Example (default):
idx.Index(1, "The Quick Brown Fox")
Example (raw, no analysis):
idx.Index(1, "SKU-9021-XL", iskra.WithoutAnalyzer())
func (*InvertedIndex) Last ¶
func (idx *InvertedIndex) Last(token string) (Position, error)
Last returns the last occurrence of a token in the index
func (*InvertedIndex) Next ¶
func (idx *InvertedIndex) Next(token string, currentPos Position) (Position, error)
Next finds the next occurrence of a token after the given position
func (*InvertedIndex) NextCover ¶
func (idx *InvertedIndex) NextCover(tokens []string, startPos Position) []Position
NextCover finds the next "cover" - a range containing all given tokens
func (*InvertedIndex) NextPhrase ¶
func (idx *InvertedIndex) NextPhrase(query string, startPos Position) []Position
NextPhrase finds the next occurrence of a phrase (sequence of words) in the index
func (*InvertedIndex) Previous ¶
func (idx *InvertedIndex) Previous(token string, currentPos Position) (Position, error)
Previous finds the previous occurrence of a token before the given position
func (*InvertedIndex) RankBM25 ¶
func (idx *InvertedIndex) RankBM25(query string, maxResults int) []Match
RankBM25 performs BM25 ranking of search results
func (*InvertedIndex) RankProximity ¶
func (idx *InvertedIndex) RankProximity(query string, maxResults int) []Match
RankProximity performs proximity-based ranking of search results
func (*InvertedIndex) Upsert ¶
func (idx *InvertedIndex) Upsert(docID uint32, document string, opts ...IndexOption)
Upsert inserts a new document or replaces the existing one for the given docID.
Accepts the same options as Index — in particular WithoutAnalyzer() to bypass the analysis pipeline and store the document text verbatim.
Example (default):
idx.Upsert(42, "updated document text")
Example (raw):
idx.Upsert(42, "SKU-9021-XL", iskra.WithoutAnalyzer())
type Iterator ¶
type Iterator struct {
// contains filtered or unexported fields
}
Iterator provides sequential access to skip list elements
type Match ¶
type Match struct {
DocID uint32 // Document identifier
Offsets []Position // Where the match was found [start, end]
Score float64 // How relevant is this match?
}
Match represents a search result with its positions and relevance score. DocID is uint32 to match the index-wide convention.
type Node ¶
type Node struct {
Key Position // The position stored in this node
Tower [MaxHeight]*Node // Array of forward pointers (one per level)
}
═══════════════════════════════════════════════════════════════════════════════ NODE: A Skip List Node ═══════════════════════════════════════════════════════════════════════════════
type Position ¶
type Position struct {
DocumentID uint32 // Which document? (uint32 matches roaring.Bitmap natively)
Offset int // Which word in the document? (int to support BOF/EOF sentinels)
}
═══════════════════════════════════════════════════════════════════════════════ POSITION: A Location in a Document ═══════════════════════════════════════════════════════════════════════════════ Position identifies a specific word in a specific document.
DocumentID is uint32: non-negative, matches roaring.Bitmap natively, and covers ~4 billion documents — more than enough for any use case.
Offset stays int so it can hold BOF (MinInt) and EOF (MaxInt) sentinels.
ORDERING: --------- Positions are ordered first by DocumentID, then by Offset:
Doc1:Pos5 < Doc1:Pos10 < Doc2:Pos0 < Doc2:Pos3
═══════════════════════════════════════════════════════════════════════════════
func (*Position) GetDocumentID ¶
GetDocumentID returns the document ID
func (*Position) IsBefore ¶
IsBefore checks if this position comes before another position
ORDERING RULES: --------------- Position A < Position B if:
- A.DocumentID < B.DocumentID, OR
- Same document AND A.Offset < B.Offset
func (*Position) IsBeginning ¶
IsBeginning checks if this is the BOF sentinel
type QueryBuilder ¶
type QueryBuilder struct {
// contains filtered or unexported fields
}
QueryBuilder provides a fluent interface for building boolean queries
func NewQueryBuilder ¶
func NewQueryBuilder(index *InvertedIndex) *QueryBuilder
NewQueryBuilder creates a new query builder
func (*QueryBuilder) Execute ¶
func (qb *QueryBuilder) Execute() *roaring.Bitmap
Execute runs the query and returns matching document IDs as a bitmap
func (*QueryBuilder) ExecuteWithBM25 ¶
func (qb *QueryBuilder) ExecuteWithBM25(maxResults int) []Match
ExecuteWithBM25 runs the query and returns ranked results using BM25
func (*QueryBuilder) Group ¶
func (qb *QueryBuilder) Group(fn func(*QueryBuilder)) *QueryBuilder
Group creates a sub-query with its own scope
func (*QueryBuilder) Phrase ¶
func (qb *QueryBuilder) Phrase(phrase string) *QueryBuilder
Phrase adds a phrase query (exact sequence of words)
func (*QueryBuilder) Term ¶
func (qb *QueryBuilder) Term(term string) *QueryBuilder
Term adds a term to the query
type SkipList ¶
type SkipList struct {
Head *Node // Sentinel head node (doesn't contain real data)
Height int // Current height of the tallest tower
}
═══════════════════════════════════════════════════════════════════════════════ SKIP LIST: The Main Data Structure ═══════════════════════════════════════════════════════════════════════════════
func (*SkipList) FindGreaterThan ¶
FindGreaterThan finds the smallest key greater than the given key
func (*SkipList) FindLessThan ¶
FindLessThan finds the largest key less than the given key