marisa

README

go-marisa

Go bindings for marisa-trie using wazero.

This library supports little-endian MARISA dictionaries up to 4 GiB. On 32-bit systems, the size is limited to 2 GiB. Big-endian dictionaries (i.e., ones generated with the native tools on big-endian hosts) are not supported. Concurrent usage is not currently supported. All other features are exposed with a high-level Go interface. All errors are properly handled.

On platforms which support wazero's JIT compiler (arm64, amd64), it's about 2-3x slower than the native library. Using the interpreter, it's about 100-200x slower.

This module also includes drop-in replacements for the native command-line tools. The have compatible input/output and exit codes, but the error messages may differ.

Documentation

Overview

Package marisa contains bindings for the marisa-trie library.

Index

• Constants
• func Initialize() error
• type CacheLevel
  • func (c CacheLevel) String() string
• type Config
• type Key
• type NodeOrder
  • func (t NodeOrder) String() string
• type TailMode
  • func (t TailMode) String() string
• type Trie
  • func Load(r io.Reader) (*Trie, error)
  • func New(b []byte) (*Trie, error)
  • func Open(name string) (*Trie, error)
  • func (t *Trie) AppendBinary(b []byte) ([]byte, error)
  • func (t *Trie) Build(keys iter.Seq[string], cfg Config) error
  • func (t *Trie) BuildWeights(keys iter.Seq2[string, float32], cfg Config) error
  • func (t *Trie) CommonPrefixSearch(query string, limit int) ([]Key, error)
  • func (t *Trie) CommonPrefixSearchSeq(query string) func(*error) iter.Seq2[uint32, string]
  • func (t *Trie) DiskSize() uint32
  • func (t *Trie) Dump(limit int) ([]Key, error)
  • func (t *Trie) DumpSeq() func(*error) iter.Seq2[uint32, string]
  • func (t *Trie) Lookup(key string) (uint32, bool, error)
  • func (t *Trie) MapFile(f *os.File, offset int64, length int64) error
  • func (t *Trie) MarshalBinary() ([]byte, error)
  • func (t *Trie) NodeOrder() NodeOrder
  • func (t *Trie) NumNodes() uint32
  • func (t *Trie) NumTries() uint32
  • func (t *Trie) PredictiveSearch(query string, limit int) ([]Key, error)
  • func (t *Trie) PredictiveSearchSeq(query string) func(*error) iter.Seq2[uint32, string]
  • func (t *Trie) ReadFrom(r io.Reader) (int64, error)
  • func (t *Trie) ReverseLookup(id uint32) (string, bool, error)
  • func (t *Trie) Size() uint32
  • func (t *Trie) String() string
  • func (t *Trie) TailMode() TailMode
  • func (t *Trie) TotalSize() uint32
  • func (t *Trie) UnmarshalBinary(b []byte) error
  • func (t *Trie) WriteTo(w io.Writer) (int64, error)

Constants

const (
	MinNumTries = int(_MARISA_MIN_NUM_TRIES)
	MaxNumTries = int(_MARISA_MAX_NUM_TRIES)
)

NumTries specifies the number of tries to use. Usually, more tries make a dictionary space-efficient but time-inefficient.

The limits are an implementation detail.

Functions

func Initialize

func Initialize() error

Initialize compiles the wasm binary.

This is called implicitly when Trie is used for the first time.

Types

type CacheLevel

type CacheLevel int

CacheLevel specifies the cache size. A larger cache enables faster search but takes a more space.

const (
	HugeCache CacheLevel = iota + 1
	LargeCache
	NormalCache
	SmallCache
	TinyCache
)

func (CacheLevel) String

func (c CacheLevel) String() string

type Config

type Config struct {
	NumTries   int
	CacheLevel CacheLevel
	TailMode   TailMode
	NodeOrder  NodeOrder
}

Config specifies options for a dictionary. Any unspecified options will be set to their default.

type Key

type Key struct {
	ID  uint32
	Key string
}

type NodeOrder

type NodeOrder int

NodeOrder specifies the arrangement of nodes, which affects the time cost of matching and the order of predictive search.

const (
	// LabelOrder arranges nodes in ascending label order. LabelOrder is useful
	// if an application needs to predict keys in label order.
	LabelOrder NodeOrder = iota + 1

	// WeightOrder arranges nodes in descending weight order. WeightOrder is
	// generally a better choice because it enables faster matching.
	WeightOrder
)

func (NodeOrder) String

func (t NodeOrder) String() string

type TailMode

type TailMode int

TailMode specifies the kind of TAIL implementation.

const (
	// TextTail merges last labels as zero-terminated strings. So, it is
	// available if and only if the last labels do not contain a NULL character.
	// If TextTail is specified and a NULL character exists in the last labels,
	// the setting is automatically switched to MARISA_BINARY_TAIL.
	TextTail TailMode = iota + 1

	// BinaryTail also merges last labels but as byte sequences. It uses a bit
	// vector to detect the end of a sequence, instead of NULL characters. So,
	// BinaryTail requires a larger space if the average length of labels is
	// greater than 8.
	BinaryTail
)

func (TailMode) String

func (t TailMode) String() string

type Trie

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

Trie is a read-only in-memory little-endian MARISA dictionary.

At the moment, it must not be used concurrently. This restriction may be lifted in the future. It's okay to nest iterators or call methods from within one.

On 64-bit systems, the maximum dictionary size is 4GiB. On 32-bit systems, the maximum dictionary size is 2 GiB. Note that if you build/load the same trie twice, it needs twice the amount of memory since it swaps it at the end.

func Load

func Load(r io.Reader) (*Trie, error)

Load is shorthand for initializing a dictionary with Trie.ReadFrom.

func New

func New(b []byte) (*Trie, error)

New is shorthand for initializing a dictionary with Trie.UnmarshalBinary. Using Load with a bytes.Reader may result in a more optimal in-memory layout.

func Open

func Open(name string) (*Trie, error)

Open opens a dictionary from a file.

func (*Trie) AppendBinary

func (t *Trie) AppendBinary(b []byte) ([]byte, error)

func (*Trie) Build

func (t *Trie) Build(keys iter.Seq[string], cfg Config) error

Build builds a dictionary out of the specified set of keys, with a weight of 1 for each.

func (*Trie) BuildWeights

func (t *Trie) BuildWeights(keys iter.Seq2[string, float32], cfg Config) error

BuildWeights builds a dictionary out of the specified set of keys and weights. If a key is specified multiple times, the weights are accumulated.

func (*Trie) CommonPrefixSearch

func (t *Trie) CommonPrefixSearch(query string, limit int) ([]Key, error)

CommonPrefixSearchSeq returns keys which equal any prefix of the query string.

func (*Trie) CommonPrefixSearchSeq

func (t *Trie) CommonPrefixSearchSeq(query string) func(*error) iter.Seq2[uint32, string]

CommonPrefixSearchSeq returns keys which equal any prefix of the query string.

func (*Trie) DiskSize

func (t *Trie) DiskSize() uint32

DiskSize returns the serialized size of the dictionary.

func (*Trie) Dump

func (t *Trie) Dump(limit int) ([]Key, error)

Dump dumps all keys.

func (*Trie) DumpSeq

func (t *Trie) DumpSeq() func(*error) iter.Seq2[uint32, string]

DumpSeq dumps all keys.

func (*Trie) Lookup

func (t *Trie) Lookup(key string) (uint32, bool, error)

Lookup checks whether a key is registered or not, returning its ID.

func (*Trie) MapFile

func (t *Trie) MapFile(f *os.File, offset int64, length int64) error

MapFile mmaps a file and loads the dictionary from it. On error, the trie is left unchanged. If not supported by the current platform, an error matching errors.ErrUnsupported is returned.

func (*Trie) MarshalBinary

func (t *Trie) MarshalBinary() ([]byte, error)

MarshalBinary serializes the dictionary.

func (*Trie) NodeOrder

func (t *Trie) NodeOrder() NodeOrder

NodeOrder returns the tail mode of the dictionary. If unknown, it returns zero.

func (*Trie) NumNodes

func (t *Trie) NumNodes() uint32

NumNodes returns the number of nodes in the dictionary.

func (*Trie) NumTries

func (t *Trie) NumTries() uint32

NumTries returns the number of tries in the dictionary

func (*Trie) PredictiveSearch

func (t *Trie) PredictiveSearch(query string, limit int) ([]Key, error)

PredictiveSearch returns keys starting with a query string.

func (*Trie) PredictiveSearchSeq

func (t *Trie) PredictiveSearchSeq(query string) func(*error) iter.Seq2[uint32, string]

PredictiveSearch returns keys starting with a query string.

func (*Trie) ReadFrom

func (t *Trie) ReadFrom(r io.Reader) (int64, error)

ReadFrom reads a dictionary from r. On success, it will have read exactly the size of the dictionary. On error, the trie is left unchanged.

func (*Trie) ReverseLookup

func (t *Trie) ReverseLookup(id uint32) (string, bool, error)

ReverseLookup gets a key by its ID.

func (*Trie) Size

func (t *Trie) Size() uint32

Size returns the number of keys in the dictionary. Key are numbered from 0 to Size-1.

func (*Trie) String

func (t *Trie) String() string

String returns a human-readable description of the dictionary.

func (*Trie) TailMode

func (t *Trie) TailMode() TailMode

TailMode returns the tail mode of the dictionary. If unknown, it returns zero.

func (*Trie) TotalSize

func (t *Trie) TotalSize() uint32

TotalSize returns the in-memory size of the dictionary.

func (*Trie) UnmarshalBinary

func (t *Trie) UnmarshalBinary(b []byte) error

UnmarshalBinary copies b and maps the trie directly from it. This is faster than Trie.ReadFrom, but may have a less optimal memory layout. On error, the trie is left unchanged.

func (*Trie) WriteTo

func (t *Trie) WriteTo(w io.Writer) (int64, error)

WriteTo serializes the dictionary to w.