dafsa — finite-state structures for sequence data

A set of sequences holds a great deal of redundancy: words share beginnings, and they share endings. A deterministic acyclic finite-state automaton stores each shared part once, so the set becomes a graph whose size reflects how much its members have in common rather than how many there are. Membership is then a walk, and the same walk answers rather more — how many sequences follow a prefix, which is the n-th in order, what a sequence weighs. dafsa builds these structures, minimises them, and lets you query and export them.

Installation

pip install dafsa

Example

from dafsa import Dafsa

lexicon = Dafsa.from_sequences(["tap", "taps", "top", "tops"])

"taps" in lexicon      # True
"ta" in lexicon        # False    a prefix is not a member
len(lexicon)           # 4        counted, not enumerated
lexicon.unrank(2)      # ('t', 'o', 'p')
lexicon.num_states     # 5        a trie would need 8

The shared ps ending is stored once, and the shared t beginning too. Nothing about the answers changes; only the space they are computed in.

What minimisation buys

trie minimised (DAFSA) minimised and compacted

Figure 1. States needed to hold a growing set of sequences. A trie grows with the total length of its input; merging equivalent states folds the shared endings away, and collapsing forced chains removes most of what is left. At 96,393 sequences: 360,103 states, 109,160, and 39,864. Reproduce with benchmarks/run.py.

Structures

Structure	Appropriate when	Cost
Trie	prefixes are shared but the structure must stay a tree	O(total)
Dafsa	a set of sequences is stored and queried; the usual choice	O(n log n)
CompactDafsa	the automaton is to be drawn, exported, or made smaller still	O(states)
SuffixAutomaton	questions are about substrings within one sequence	O(n)
Cdawg	the same, with forced chains collapsed	O(n)
Fst	sequences are mapped to sequences, not merely accepted	O(n log n)

All six share one frozen core — compressed sparse row adjacency over array.array, no object per state — and one weight algebra. Weights live in a semiring: boolean, counting, tropical, log, probability and Viterbi are built in, and any type satisfying the protocol works. Because minimisation is weight-aware, the weight of a path is the weight the sequence was inserted with.

Beyond words

Tokens need only be hashable, and a sequence is any Sequence[Hashable]. Characters are the default because a str is a sequence of them, not because the library is about text:

Lexicography. word lists and spell-checker dictionaries, indexed and ranked in place.
Phonology. sequences of phonemes or feature bundles, with multi-character segments kept whole.
Historical linguistics. sound-change rules as transducers, composed into a chain.
Genomics. substring indexes over sequence data, in linear time and space.
Anything discrete. tags, integers, tuples, mixed and mutually incomparable types.

Documentation

User Guide → API Reference → Changelog → Source (GitHub) → Package (PyPI) →

Citation

@software{tresoldi_dafsa,
  author  = {Tresoldi, Tiago},
  title   = {DAFSA: Finite-state structures for sequence data},
  year    = {2026},
  version = {2.0.0},
  doi     = {10.5281/zenodo.3668870},
  url     = {https://github.com/tresoldi/dafsa}
}