fst

package
v0.0.0-...-de52fee Latest Latest
Warning

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

 Go to latest Published: Mar 8, 2026 License: Apache-2.0 Imports: 7 Imported by: 0

Documentation

Overview

Package fst provides true automata intersection for FST and regular expressions Based on the principles described in https://burntsushi.net/transducers/

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func FuzzySearch 

func FuzzySearch(fsa FSA, pattern string, maxDistance int) []string

FuzzySearch performs fuzzy search on the FSA using Levenshtein distance

func PrefixRegexSearch 

func PrefixRegexSearch(fsa FSA, prefix, pattern string) ([]string, error)

PrefixRegexSearch performs regex search on keys with a given prefix

func RegexSearch 

func RegexSearch(fsa FSA, pattern string) ([]string, error)

RegexSearch performs regex search on the FSA

Types

type Automaton 

type Automaton struct {
	States     []State
	StartState uint32
	NumStates  uint32
}

Automaton represents a finite state automaton/transducer

func NewAutomaton 

func NewAutomaton() *Automaton

NewAutomaton creates a new empty automaton

func (*Automaton) Accept 

func (a *Automaton) Accept(input []byte) bool

Accept tests if the automaton accepts the given input

func (*Automaton) AcceptWithOutput 

func (a *Automaton) AcceptWithOutput(input []byte) (bool, uint64)

AcceptWithOutput tests if the automaton accepts the input and returns the output

func (*Automaton) AddState 

func (a *Automaton) AddState(isFinal bool, output uint64) uint32

AddState adds a new state to the automaton

func (*Automaton) AddTransition 

func (a *Automaton) AddTransition(fromState uint32, label byte, toState uint32, output uint64)

AddTransition adds a transition from one state to another

func (*Automaton) FindTransition 

func (a *Automaton) FindTransition(stateID uint32, label byte) *Transition

FindTransition finds a transition from the given state with the given label

func (*Automaton) GetState 

func (a *Automaton) GetState(stateID uint32) *State

GetState returns the state with the given ID

type AutomatonBuilder 

type AutomatonBuilder struct {
	// contains filtered or unexported fields
}

AutomatonBuilder helps build automata efficiently

func NewAutomatonBuilder 

func NewAutomatonBuilder() *AutomatonBuilder

NewAutomatonBuilder creates a new automaton builder

func (*AutomatonBuilder) Build 

func (ab *AutomatonBuilder) Build() *Automaton

Build returns the constructed automaton

func (*AutomatonBuilder) BuildFromStrings 

func (ab *AutomatonBuilder) BuildFromStrings(keys []string) *Automaton

BuildFromStrings builds an automaton from a sorted list of strings

type ComplexQuery 

type ComplexQuery struct {
	// contains filtered or unexported fields
}

ComplexQuery represents a complex query combining multiple search types

func NewComplexQuery 

func NewComplexQuery(fsa FSA) *ComplexQuery

NewComplexQuery creates a new complex query

func (*ComplexQuery) Execute 

func (cq *ComplexQuery) Execute(options QueryOptions) (*QueryResult, error)

Execute executes a complex query with multiple criteria

type DFA 

type DFA struct {
	// contains filtered or unexported fields
}

DFA represents a deterministic finite automaton

func NFAtoDFA 

func NFAtoDFA(nfa *NFA) *DFA

NFAtoDFA converts NFA to DFA using subset construction This is a simplified implementation for demonstration

func (*DFA) Accept 

func (dfa *DFA) Accept(input string) bool

Accept tests if the DFA accepts the given input

type DFAState 

type DFAState struct {
	// contains filtered or unexported fields
}

DFAState represents a state in the DFA

type DFAStateID 

type DFAStateID int

DFAStateID uniquely identifies a DFA state

type DebugInfo 

type DebugInfo struct {
	Pattern            string
	NFAStates          int
	DFAStates          int
	IntersectionStates int
	MatchingKeys       []string
	Performance        PerformanceMetrics
}

DebugInfo provides debugging information about automata intersection

func (*DebugInfo) String 

func (di *DebugInfo) String() string

String returns a formatted string representation of debug info

type FSA 

type FSA interface {
	Contains(key []byte) bool
	Iterator() FSAIterator
	PrefixIterator(prefix []byte) FSAIterator
	RangeIterator(start, end []byte) FSAIterator
	Len() int
	NumStates() int
}

FSA represents a Finite State Acceptor (ordered set).

func Difference 

func Difference(fsa FSA, others ...FSA) (FSA, error)

Difference returns this FSA minus the others

func Intersection 

func Intersection(fsa FSA, others ...FSA) (FSA, error)

Intersection returns the intersection of this FSA with others

func SymmetricDifference 

func SymmetricDifference(fsa FSA, other FSA) (FSA, error)

SymmetricDifference returns the symmetric difference with another FSA

func Union 

func Union(fsa FSA, others ...FSA) (FSA, error)

Union returns the union of this FSA with others

type FSABuilder 

type FSABuilder interface {
	Add(key []byte) error
	Build() (FSA, error)
	Reset()
	Len() int
	EstimatedSize() int
}

FSABuilder builds FSA from sorted keys.

func NewFSABuilder 

func NewFSABuilder() FSABuilder

NewFSABuilder creates a new FSA builder.

type FSAIterator 

type FSAIterator interface {
	Next() bool
	Key() []byte
	Reset()
	Seek(target []byte) bool
}

FSAIterator provides iteration over FSA keys.

type FST 

type FST struct {
	// contains filtered or unexported fields
}

FST represents a Finite State Transducer (ordered map)

func BuildFSTFromDocuments 

func BuildFSTFromDocuments(documents []string) (*FST, error)

BuildFSTFromDocuments creates an FST from a collection of documents Each word in each document becomes a key with its document index as the value

func BuildFSTFromWords 

func BuildFSTFromWords(words []string) (*FST, error)

BuildFSTFromWords creates an FST from a simple list of words

func FSTIntersection 

func FSTIntersection(fsts ...*FST) (*FST, error)

FSTIntersection performs intersection of multiple FSTs Only keys present in ALL FSTs are included, with first FST's value

func FSTUnion 

func FSTUnion(fsts ...*FST) (*FST, error)

FSTUnion performs union of multiple FSTs In case of key conflicts, the first FST's value takes precedence

func (*FST) Contains 

func (fst *FST) Contains(key []byte) bool

Contains checks if a key exists in the FST

func (*FST) Get 

func (fst *FST) Get(key []byte) (uint64, bool)

Get retrieves the value associated with a key

func (*FST) IsEmpty 

func (fst *FST) IsEmpty() bool

IsEmpty returns true if the FST is empty

func (*FST) Iterator 

func (fst *FST) Iterator() *FSTIterator

Iterator returns an iterator over all key-value pairs

func (*FST) PrefixIterator 

func (fst *FST) PrefixIterator(prefix []byte) *FSTPrefixIterator

PrefixIterator returns an iterator over key-value pairs with the given prefix

func (*FST) RangeIterator 

func (fst *FST) RangeIterator(startKey, endKey []byte) *FSTRangeIterator

RangeIterator returns an iterator over key-value pairs in the given range

func (*FST) Size 

func (fst *FST) Size() int

Size returns the number of key-value pairs

type FSTBuilder 

type FSTBuilder struct {
	// contains filtered or unexported fields
}

FSTBuilder builds FSTs with validation

func NewFSTBuilder 

func NewFSTBuilder() *FSTBuilder

NewFSTBuilder creates a new FST builder

func (*FSTBuilder) Add 

func (b *FSTBuilder) Add(key []byte, value uint64) error

Add adds a key-value pair to the FST being built

func (*FSTBuilder) Build 

func (b *FSTBuilder) Build() (*FST, error)

Build creates the final FST

type FSTFSAAdapter 

type FSTFSAAdapter struct {
	// contains filtered or unexported fields
}

FSTFSAAdapter adapts FST to implement the FSA interface for automata intersection

func NewFSTFSAAdapter 

func NewFSTFSAAdapter(fst *FST) *FSTFSAAdapter

NewFSTFSAAdapter creates an adapter to make FST implement FSA interface

func (*FSTFSAAdapter) Contains 

func (adapter *FSTFSAAdapter) Contains(key []byte) bool

Contains checks if a key exists in the FST

func (*FSTFSAAdapter) Iterator 

func (adapter *FSTFSAAdapter) Iterator() FSAIterator

Iterator returns an iterator over all keys

func (*FSTFSAAdapter) Len 

func (adapter *FSTFSAAdapter) Len() int

Len returns the number of keys

func (*FSTFSAAdapter) NumStates 

func (adapter *FSTFSAAdapter) NumStates() int

NumStates returns an approximation of the number of states (simplified)

func (*FSTFSAAdapter) PrefixIterator 

func (adapter *FSTFSAAdapter) PrefixIterator(prefix []byte) FSAIterator

PrefixIterator returns an iterator over keys with the given prefix

func (*FSTFSAAdapter) RangeIterator 

func (adapter *FSTFSAAdapter) RangeIterator(start, end []byte) FSAIterator

RangeIterator returns an iterator over keys in the given range

type FSTFSAIteratorAdapter 

type FSTFSAIteratorAdapter struct {
	// contains filtered or unexported fields
}

FSTFSAIteratorAdapter adapts FST iterators to FSA iterator interface

func (*FSTFSAIteratorAdapter) Key 

func (adapter *FSTFSAIteratorAdapter) Key() []byte

Key returns the current key

func (*FSTFSAIteratorAdapter) Next 

func (adapter *FSTFSAIteratorAdapter) Next() bool

Next advances the iterator and returns true if there's a next element

func (*FSTFSAIteratorAdapter) Reset 

func (adapter *FSTFSAIteratorAdapter) Reset()

Reset resets the iterator (simplified implementation)

func (*FSTFSAIteratorAdapter) Seek 

func (adapter *FSTFSAIteratorAdapter) Seek(target []byte) bool

Seek seeks to the target key (simplified implementation)

type FSTIterator 

type FSTIterator struct {
	// contains filtered or unexported fields
}

FSTIterator provides iteration over FST key-value pairs

func (*FSTIterator) HasNext 

func (iter *FSTIterator) HasNext() bool

HasNext returns true if there are more key-value pairs

func (*FSTIterator) Next 

func (iter *FSTIterator) Next() ([]byte, uint64)

Next returns the next key-value pair

type FSTPrefixIterator 

type FSTPrefixIterator struct {
	// contains filtered or unexported fields
}

FSTPrefixIterator provides iteration over key-value pairs with a common prefix

func (*FSTPrefixIterator) HasNext 

func (iter *FSTPrefixIterator) HasNext() bool

HasNext returns true if there are more key-value pairs with the prefix

func (*FSTPrefixIterator) Next 

func (iter *FSTPrefixIterator) Next() ([]byte, uint64)

Next returns the next key-value pair with the prefix

type FSTRangeIterator 

type FSTRangeIterator struct {
	// contains filtered or unexported fields
}

FSTRangeIterator provides iteration over a range of key-value pairs

func (*FSTRangeIterator) HasNext 

func (iter *FSTRangeIterator) HasNext() bool

HasNext returns true if there are more key-value pairs in the range

func (*FSTRangeIterator) Next 

func (iter *FSTRangeIterator) Next() ([]byte, uint64)

Next returns the next key-value pair in the range

type LevenshteinAutomaton 

type LevenshteinAutomaton struct {
	Pattern     string
	MaxDistance int
	States      [][]LevenshteinState // [position][errors] -> state
}

LevenshteinAutomaton represents an automaton for fuzzy string matching using edit distance (insertions, deletions, substitutions)

func NewLevenshteinAutomaton 

func NewLevenshteinAutomaton(pattern string, maxDistance int) *LevenshteinAutomaton

NewLevenshteinAutomaton creates a Levenshtein automaton for fuzzy matching

func (*LevenshteinAutomaton) CanMatch 

func (la *LevenshteinAutomaton) CanMatch() bool

CanMatch checks if this automaton could potentially match with more input

func (*LevenshteinAutomaton) IsMatch 

func (la *LevenshteinAutomaton) IsMatch() bool

IsMatch checks if the current state represents a successful match

func (*LevenshteinAutomaton) Step 

func (la *LevenshteinAutomaton) Step(char byte) *LevenshteinAutomaton

Step advances the automaton with the given character

type LevenshteinState 

type LevenshteinState struct {
	Position int  // Position in the target string
	Errors   int  // Number of errors so far
	IsValid  bool // Whether this state is reachable
}

LevenshteinState represents a state in the Levenshtein automaton

type MinimizedFST 

type MinimizedFST struct {
	// contains filtered or unexported fields
}

MinimizedFST represents a fully minimized FST

func (*MinimizedFST) Contains 

func (fst *MinimizedFST) Contains(key []byte) bool

Contains checks if a key exists in the minimized FST

func (*MinimizedFST) EstimateMemoryUsage 

func (fst *MinimizedFST) EstimateMemoryUsage() int

EstimateMemoryUsage estimates memory usage in bytes

func (*MinimizedFST) Get 

func (fst *MinimizedFST) Get(key []byte) (uint64, bool)

Get retrieves a value from the minimized FST

func (*MinimizedFST) NumStates 

func (fst *MinimizedFST) NumStates() int

NumStates returns the number of states (simplified for now)

type MinimizingBuilder 

type MinimizingBuilder struct {
	// contains filtered or unexported fields
}

MinimizingBuilder builds FSTs with automatic minimization

func NewMinimizingBuilder 

func NewMinimizingBuilder() *MinimizingBuilder

NewMinimizingBuilder creates a new minimizing FST builder

func (*MinimizingBuilder) Add 

func (b *MinimizingBuilder) Add(key []byte, value uint64) error

Add inserts a key-value pair into the FST being built

func (*MinimizingBuilder) Build 

func (b *MinimizingBuilder) Build() (*MinimizedFST, error)

Build finalizes the FST construction

func (*MinimizingBuilder) SetMaxStates 

func (b *MinimizingBuilder) SetMaxStates(max int)

SetMaxStates configures the maximum number of unfrozen states (placeholder)

type NFA 

type NFA struct {
	// contains filtered or unexported fields
}

NFA represents a non-deterministic finite automaton compiled from regex

func RegexToNFA 

func RegexToNFA(pattern string) (*NFA, error)

RegexToNFA converts a regex pattern to NFA for benchmarking and testing

func (*NFA) States 

func (nfa *NFA) States() map[NFAStateID]*NFAState

States returns the internal states map for debugging

type NFAState 

type NFAState struct {
	// contains filtered or unexported fields
}

NFAState represents a single state in the NFA

type NFAStateID 

type NFAStateID int

NFAStateID uniquely identifies a state in the NFA

type PerformanceMetrics 

type PerformanceMetrics struct {
	NFAConstructionTimeNs int64
	DFAConstructionTimeNs int64
	IntersectionTimeNs    int64
	TotalTimeNs           int64
}

PerformanceMetrics tracks performance data

type QueryOptions 

type QueryOptions struct {
	Prefix           string // Prefix filter
	StartKey         string // Range start (inclusive)
	EndKey           string // Range end (exclusive)
	RegexPattern     string // Regex pattern to match
	FuzzyPattern     string // Pattern for fuzzy search
	FuzzyMaxDistance int    // Maximum edit distance for fuzzy search
	Limit            int    // Maximum number of results (0 = no limit)
}

QueryOptions represents options for complex queries

type QueryResult 

type QueryResult struct {
	Keys  []string
	Count int
}

QueryResult represents the result of a complex query

type RegexAutomaton 

type RegexAutomaton struct {
	// contains filtered or unexported fields
}

RegexAutomaton represents a simple regex-based automaton This is a simplified implementation - a full implementation would convert regex to NFA/DFA for better performance

func NewRegexAutomaton 

func NewRegexAutomaton(pattern string) (*RegexAutomaton, error)

NewRegexAutomaton creates a regex automaton

func (*RegexAutomaton) Accept 

func (ra *RegexAutomaton) Accept(input []byte) bool

Accept tests if the automaton accepts the input

type RegexMatcher 

type RegexMatcher struct {
	// contains filtered or unexported fields
}

RegexMatcher provides regex matching capabilities for FSAs

func NewRegexMatcher 

func NewRegexMatcher(pattern string) (*RegexMatcher, error)

NewRegexMatcher creates a new regex matcher

func (*RegexMatcher) FindMatches 

func (rm *RegexMatcher) FindMatches(keys []string) []string

FindMatches finds all matches in the given strings

func (*RegexMatcher) Match 

func (rm *RegexMatcher) Match(input []byte) bool

Match tests if the regex matches the given input

type SearchEngine 

type SearchEngine struct {
	// contains filtered or unexported fields
}

SearchEngine provides high-level search functionality using FST and automata intersection

func NewSearchEngine 

func NewSearchEngine(fst *FST, documents []string, scoreFunc func(string, string) float64) *SearchEngine

NewSearchEngine creates a new search engine with FST index and documents

func (*SearchEngine) ExactSearch 

func (se *SearchEngine) ExactSearch(word string) ([]SearchResult, error)

ExactSearch searches for documents containing the exact word

func (*SearchEngine) GetIntersectionDebugInfo 

func (se *SearchEngine) GetIntersectionDebugInfo(pattern string) (*DebugInfo, error)

GetIntersectionDebugInfo provides detailed debugging information about automata intersection

func (*SearchEngine) IntersectionRegexSearch 

func (se *SearchEngine) IntersectionRegexSearch(pattern string) ([]SearchResult, error)

IntersectionRegexSearch performs automata intersection between FST and regex pattern This is the mathematically optimal approach that avoids iterating over all FST keys

func (*SearchEngine) PrefixSearch 

func (se *SearchEngine) PrefixSearch(prefix string) ([]SearchResult, error)

PrefixSearch searches for documents containing words with the given prefix

func (*SearchEngine) RegexSearch 

func (se *SearchEngine) RegexSearch(pattern string) ([]SearchResult, error)

RegexSearch performs naive regex search by iterating over all documents This is the traditional O(n) approach for comparison

type SearchResult 

type SearchResult struct {
	Word  string  // The document text
	DocID int     // Document ID
	Score float64 // Relevance score
}

SearchResult represents a search result with the matching document and metadata

type SetOperation 

type SetOperation struct {
	// contains filtered or unexported fields
}

SetOperation performs set operations between multiple FSAs

func NewSetOperation 

func NewSetOperation(operation SetOperationType, fsas ...FSA) *SetOperation

NewSetOperation creates a new set operation

func (*SetOperation) Execute 

func (so *SetOperation) Execute() (FSA, error)

Execute performs the set operation and returns the result as a new FSA

type SetOperationType 

type SetOperationType int

SetOperationType represents the type of set operation 

const (
	UnionOp SetOperationType = iota
	IntersectionOp
	DifferenceOp
	SymmetricDifferenceOp
)

type SimpleFSA 

type SimpleFSA struct {
	// contains filtered or unexported fields
}

SimpleFSA provides a simple FSA implementation for testing.

func NewSimpleFSA 

func NewSimpleFSA(keys [][]byte) *SimpleFSA

NewSimpleFSA creates a new simple FSA from sorted keys.

func (*SimpleFSA) Contains 

func (fsa *SimpleFSA) Contains(key []byte) bool

Contains returns true if the key is in the set.

func (*SimpleFSA) Iterator 

func (fsa *SimpleFSA) Iterator() FSAIterator

Iterator returns an iterator over all keys in lexicographic order.

func (*SimpleFSA) Len 

func (fsa *SimpleFSA) Len() int

Len returns the number of keys in the set.

func (*SimpleFSA) NumStates 

func (fsa *SimpleFSA) NumStates() int

NumStates returns the total number of states.

func (*SimpleFSA) PrefixIterator 

func (fsa *SimpleFSA) PrefixIterator(prefix []byte) FSAIterator

PrefixIterator returns an iterator over keys with the given prefix.

func (*SimpleFSA) RangeIterator 

func (fsa *SimpleFSA) RangeIterator(start, end []byte) FSAIterator

RangeIterator returns an iterator over keys in the given range [start, end).

type SimpleFSABuilder 

type SimpleFSABuilder struct {
	// contains filtered or unexported fields
}

SimpleFSABuilder implements FSABuilder with a simple approach.

func (*SimpleFSABuilder) Add 

func (builder *SimpleFSABuilder) Add(key []byte) error

Add inserts a key into the FSA being built.

func (*SimpleFSABuilder) Build 

func (builder *SimpleFSABuilder) Build() (FSA, error)

Build finalizes construction and returns the FSA.

func (*SimpleFSABuilder) EstimatedSize 

func (builder *SimpleFSABuilder) EstimatedSize() int

EstimatedSize returns an estimate of the final automaton size in bytes.

func (*SimpleFSABuilder) Len 

func (builder *SimpleFSABuilder) Len() int

Len returns the number of items added so far.

func (*SimpleFSABuilder) Reset 

func (builder *SimpleFSABuilder) Reset()

Reset clears the builder state for reuse.

type SimpleFSAIterator 

type SimpleFSAIterator struct {
	// contains filtered or unexported fields
}

SimpleFSAIterator implements FSAIterator for SimpleFSA.

func (*SimpleFSAIterator) Key 

func (iter *SimpleFSAIterator) Key() []byte

Key returns the current key.

func (*SimpleFSAIterator) Next 

func (iter *SimpleFSAIterator) Next() bool

Next advances the iterator and returns true if a value is available.

func (*SimpleFSAIterator) Reset 

func (iter *SimpleFSAIterator) Reset()

Reset resets the iterator to the beginning.

func (*SimpleFSAIterator) Seek 

func (iter *SimpleFSAIterator) Seek(target []byte) bool

Seek positions the iterator at the first key >= target.

type SimpleRegexAutomaton 

type SimpleRegexAutomaton struct {
	// contains filtered or unexported fields
}

SimpleRegexAutomaton provides a simplified regex automaton that uses Go's regexp internally This is a fallback implementation while we debug the full NFA construction

func NewSimpleRegexAutomaton 

func NewSimpleRegexAutomaton(pattern string) (*SimpleRegexAutomaton, error)

NewSimpleRegexAutomaton creates a simple regex automaton

func (*SimpleRegexAutomaton) IntersectWithFST 

func (sra *SimpleRegexAutomaton) IntersectWithFST(fsa FSA) ([]string, error)

IntersectWithFST provides the same interface as TrueRegexAutomaton

func (*SimpleRegexAutomaton) MatchString 

func (sra *SimpleRegexAutomaton) MatchString(s string) bool

MatchString tests if a string matches the regex

func (*SimpleRegexAutomaton) TrueAutomataIntersection 

func (sra *SimpleRegexAutomaton) TrueAutomataIntersection(fst *FST) ([]string, error)

TrueAutomataIntersection performs intersection using Go's regex engine

type State 

type State struct {
	ID          uint32
	IsFinal     bool
	Output      uint64 // For FST - the value associated with this state
	Transitions []Transition
}

State represents a single state in the automaton

type Transition 

type Transition struct {
	Label  byte   // The input character/byte
	Target uint32 // Target state ID
	Output uint64 // Output for this transition (FST only)
}

Transition represents a labeled edge between states

type TrueRegexAutomaton 

type TrueRegexAutomaton struct {
	// contains filtered or unexported fields
}

RegexAutomaton represents a compiled regular expression as a finite state automaton that can be intersected with FSTs using product construction

func NewTrueRegexAutomaton 

func NewTrueRegexAutomaton(pattern string) (*TrueRegexAutomaton, error)

NewRegexAutomaton compiles a regular expression into an NFA using Thompson's Construction

func (*TrueRegexAutomaton) InternalNFA 

func (ra *TrueRegexAutomaton) InternalNFA() *NFA

InternalNFA exposes the internal NFA for debugging

func (*TrueRegexAutomaton) IntersectWithFST 

func (ra *TrueRegexAutomaton) IntersectWithFST(fsa FSA) ([]string, error)

IntersectWithFST performs true automata intersection using product construction This is the key algorithm from burntsushi.net/transducers/

func (*TrueRegexAutomaton) MatchString 

func (ra *TrueRegexAutomaton) MatchString(s string) bool

MatchString tests if a string matches the regex (fallback to Go's regexp)

func (*TrueRegexAutomaton) SimulateNFA 

func (ra *TrueRegexAutomaton) SimulateNFA(input string) bool

SimulateNFA exposes NFA simulation for testing

func (*TrueRegexAutomaton) TrueAutomataIntersection 

func (ra *TrueRegexAutomaton) TrueAutomataIntersection(fst *FST) ([]string, error)

TrueAutomataIntersection performs mathematical intersection of FST and NFA

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.