Help us shape the future of Go! Take the 2026 Go Developer Survey

iskra

package module
v0.0.2 Latest Latest
Warning

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

 Go to latest Published: Mar 28, 2026 License: MIT Imports: 17 Imported by: 0

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

View Source 
const MaxHeight = 32 // Maximum tower height (supports billions of elements)

Variables

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

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

View Source 
var (
	ErrKeyNotFound    = errors.New("key not found")
	ErrNoElementFound = errors.New("no element found")
)
View Source 
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 

func Analyze(text string) []string

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) Delete added in v0.0.2 

func (idx *InvertedIndex) Delete(docID uint32) bool

Delete removes a document from the index

All positional entries, bitmaps bits, BM25 statistics, and DocStats for the given docID are cleaned up automatically under the index lock. Terms that have no remaining postings after the removal are pruned from both PostingsList and DocBitmaps, keeping the index compact.

Returns true if the document existed and was removed, false if it was not present in the index.

Example:

removed := idx.Delete(42) 

if !removed {
  log.Println("document 42 was not in the 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

func (*Iterator) HasNext 

func (it *Iterator) HasNext() bool

HasNext checks if there are more elements to iterate

func (*Iterator) Next 

func (it *Iterator) Next() Position

Next advances to and returns the next position

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.

func (*Match) GetKey 

func (m *Match) GetKey() (string, error)

GetKey generates a unique identifier for the match

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) Equals 

func (p *Position) Equals(other Position) bool

Equals checks if two positions are identical

func (*Position) GetDocumentID 

func (p *Position) GetDocumentID() uint32

GetDocumentID returns the document ID

func (*Position) GetOffset 

func (p *Position) GetOffset() int

GetOffset returns the offset

func (*Position) IsAfter 

func (p *Position) IsAfter(other Position) bool

IsAfter checks if this position comes after another position

func (*Position) IsBefore 

func (p *Position) IsBefore(other Position) bool

IsBefore checks if this position comes before another position

ORDERING RULES: --------------- Position A < Position B if:

  1. A.DocumentID < B.DocumentID, OR
  2. Same document AND A.Offset < B.Offset

func (*Position) IsBeginning 

func (p *Position) IsBeginning() bool

IsBeginning checks if this is the BOF sentinel

func (*Position) IsEnd 

func (p *Position) IsEnd() bool

IsEnd checks if this is the EOF 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) And 

func (qb *QueryBuilder) And() *QueryBuilder

And adds an AND operation

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) Not 

func (qb *QueryBuilder) Not() *QueryBuilder

Not negates the next term

func (*QueryBuilder) Or 

func (qb *QueryBuilder) Or() *QueryBuilder

Or adds an OR operation

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 QueryOp 

type QueryOp int

QueryOp represents a pending boolean operation 

const (
	OpNone QueryOp = iota
	OpAnd
	OpOr
)

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 NewSkipList 

func NewSkipList() *SkipList

NewSkipList creates an empty skip list

func (*SkipList) Delete 

func (sl *SkipList) Delete(key Position) bool

Delete removes a key from the skip list

func (*SkipList) Find 

func (sl *SkipList) Find(key Position) (Position, error)

Find searches for an exact key match

func (*SkipList) FindGreaterThan 

func (sl *SkipList) FindGreaterThan(key Position) (Position, error)

FindGreaterThan finds the smallest key greater than the given key

func (*SkipList) FindLessThan 

func (sl *SkipList) FindLessThan(key Position) (Position, error)

FindLessThan finds the largest key less than the given key

func (*SkipList) Insert 

func (sl *SkipList) Insert(key Position)

Insert adds a new key to the skip list (or updates if it exists)

func (*SkipList) Iterator 

func (sl *SkipList) Iterator() *Iterator

Iterator creates a new iterator starting at the first element

func (*SkipList) Last 

func (sl *SkipList) Last() Position

Last returns the last position in the skip list

func (*SkipList) Search 

func (sl *SkipList) Search(key Position) (*Node, [MaxHeight]*Node)

Search finds a key in the skip list and returns the path taken

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.