README
¶
mealy
A Mealy Machine implemenation in Go - good for making high-performance prefix-lookup dictionaries that take up little space.
Documentation
¶
Overview ¶
Implements a Mealy Machine as described in the paper at
http://www.n3labs.com/pdf/lexicon-squeeze.pdf
The machine is defined for byte values, and serializes with that assumption.
Index ¶
- func NewTransition(trigger byte, toStateId int, isTerminal bool) transition
- type BaseConstraints
- type Constraints
- type Recognizer
- func (self *Recognizer) AllSequences() (out <-chan []byte)
- func (self Recognizer) AllTriggers() []byte
- func (self *Recognizer) ConstrainedSequences(con Constraints) <-chan []byte
- func (self Recognizer) MaxStateTransitions() int
- func (self Recognizer) Recognizes(value []byte) bool
- func (self Recognizer) Start() state
- func (self Recognizer) String() string
- func (self Recognizer) TotalTransitions() int
- func (self Recognizer) UniqueTransitions() int
- func (self Recognizer) WriteTo(w io.Writer) (err error)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func NewTransition ¶
Create a new transition, triggered by "trigger", passing to state "toStateId", and with terminal status "isTerminal".
Types ¶
type BaseConstraints ¶
type BaseConstraints struct{}
A fully unconstrained Constraints implementation. Always returns true for all methods. It is (very) safe to "inherit" from this, since it has no internal state, to create your own Constraints-compatible types without having to specify all methods, e.g.,
type NotTooLarge struct {
BaseConstraints
}
func (n NotTooLarge) IsSmallEnough(size int) bool {
return size < 5
}
func (BaseConstraints) IsLargeEnough ¶
func (c BaseConstraints) IsLargeEnough(int) bool
func (BaseConstraints) IsSequenceAllowed ¶
func (c BaseConstraints) IsSequenceAllowed([]byte) bool
func (BaseConstraints) IsSmallEnough ¶
func (c BaseConstraints) IsSmallEnough(int) bool
func (BaseConstraints) IsValueAllowed ¶
func (c BaseConstraints) IsValueAllowed(int, byte) bool
type Constraints ¶
type Constraints interface {
IsSmallEnough(size int) bool
IsLargeEnough(size int) bool
IsValueAllowed(pos int, val byte) bool
IsSequenceAllowed(seq []byte) bool
}
Implement this to specify constraints for the Mealy machine output.
To specify a minimum and/or maximum length, implement IsLargeEnough and/or IsSmallEnough, respectively. They work the way you would expect: only values that are both small enough and large enough will be emitted.
They are separate functions because they are used in different places for different kinds of branch cutting, and this cannot be done properly if the two bounds are not specified separately.
If there are only some values that are allowed at certain positions, then IsValueAllowed should return true for all allowed values and false for all others. If all values are allowed, this must return true all the time.
Finally, you can always just implement IsSequenceAllowed, which passes the whole sequence to you before emission, and you can test the whole thing for compliance in whatever way you choose. You could technically implement any constraint this way, but be advised that *only* using this function will not be as efficient as size- and branch-bounding things using the other functions, because it will have to traverse every path in the automaton. It can be very useful as a finishing touch to the others, however, since they are less general.
type Recognizer ¶
type Recognizer []state
func FromChannel ¶
func FromChannel(values <-chan []byte) Recognizer
Builds a new mealy machine from an ordered list of values. Keeps working until the channel is closed, at which point it finalizes and returns.
func ReadFrom ¶
func ReadFrom(r io.Reader) (self Recognizer, err error)
Deserialize the Mealy machine from a Reader.
func (*Recognizer) AllSequences ¶
func (self *Recognizer) AllSequences() (out <-chan []byte)
Return a channel to which all recognized sequences will be sent. The channel is closed after the last sequence, making this suitable for use in "for range" constructs.
This is an alias for ConstrainedSequences(BaseConstraints{}).
func (Recognizer) AllTriggers ¶
func (self Recognizer) AllTriggers() []byte
Return a sorted slice of all byte values that trigger a transition anywhere.
func (*Recognizer) ConstrainedSequences ¶
func (self *Recognizer) ConstrainedSequences(con Constraints) <-chan []byte
Return a channel that produces all recognized sequences for this machine. The channel is closed after the last valid sequence, making this suitable for use in "for range" constructs.
Constraints are specified by following the Constraints interface above. Not all possible constraints can be specified that way, but those that are important for branch reduction are. More complex constaints should be implemented as a filter on the output, but size and allowed-value constraints can be very helpful in reducing the amount of work done by the machine to generate sequences.
func (Recognizer) MaxStateTransitions ¶
func (self Recognizer) MaxStateTransitions() int
func (Recognizer) Recognizes ¶
func (self Recognizer) Recognizes(value []byte) bool
func (Recognizer) Start ¶
func (self Recognizer) Start() state
func (Recognizer) String ¶
func (self Recognizer) String() string
func (Recognizer) TotalTransitions ¶
func (self Recognizer) TotalTransitions() int
func (Recognizer) UniqueTransitions ¶
func (self Recognizer) UniqueTransitions() int
Source Files
Directories