dafsa

Store sets of sequences as finite-state automata.

dafsa turns a collection of sequences into a graph in which every shared beginning and every shared ending is stored once, then answers membership, counting, ranking, prefix and weight queries by walking it. Tokens are anything hashable — characters, phonemes, tags, integers, tuples — so it is as much at home in phonology or genomics as in a spell checker.

from dafsa import Dafsa

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

lexicon.num_states  # 5   — a trie would need 8
len(lexicon)  # 4   — counted, not enumerated
lexicon.unrank(2)  # ('t', 'o', 'p')

That third line is the point beyond compression: because a minimal acyclic automaton knows how many sequences leave each state, it is also a minimal perfect hash over its own language. Every accepted sequence has a position, every position has a sequence, and reaching the millionth costs no more than reaching the first.

Install

pip install dafsa

No required dependencies. pip install "dafsa[graph]" adds networkx for the three graph exports; writing image files additionally needs Graphviz on the path.

The interface

Six structures share one frozen core, so they all answer the same queries.

from dafsa import Dafsa, SuffixAutomaton, Fst
from dafsa.semirings import COUNTING

counted = Dafsa.from_sequences(["tip", "tip", "tap"], semiring=COUNTING)
counted.weight("tip")  # 2 — what it was inserted with, not a path sum

index = SuffixAutomaton.from_sequence("banana")
index.contains_substring("nan")  # True

translate = Fst.from_pairs([("cat", "chat")])
translate.apply("cat")  # [('c', 'h', 'a', 't')]

Weights belong to an explicit semiring — boolean, counting, tropical, log, probability and Viterbi are built in, and any type satisfying the protocol works. Because minimization is weight-aware, the weight of a path is the weight the sequence was inserted with. There is also a command line: dafsa --help.

Choosing a structure

Structure	Use it for	Note
Dafsa	storing and querying a set of sequences	the usual choice
Trie	when the structure must stay a tree	states grow with total input length
CompactDafsa	drawing, exporting, or shrinking further	via .compact()
SuffixAutomaton	what occurs inside one long sequence	online, linear time and space
Cdawg	the same, with forced chains collapsed	via .compact()
Fst	mapping sequences to sequences	may be ambiguous, so apply returns a list

Why dafsa

• Weights that mean what they say. Minimization is weight-aware, so weight(seq) returns what seq was inserted with. 1.0's lookup() returned the sum of shared edge counters along the path — 7 for a sequence inserted once.
• An index, not only a set. Constant-time len(), rank/unrank, ordered iteration, prefix queries, total_weight and k_best.
• Flat arrays, no object graph. Compressed sparse row adjacency over array.array, so 96,393 sequences build in under four seconds where 1.0's changelog records "under 8 minutes" for a comparable corpus — and RecursionError is structurally unreachable.
• Typed and tested. Full type hints (py.typed), strict linting and type-checking, 100% branch coverage, and property-based tests checking the automata against independent references rather than against themselves.

Documentation

• Documentation site — user guide and full API reference.
• User Guide — concepts, choosing a structure, and worked examples across lexicography, phonology, historical linguistics and genomics.
• API Reference — every public class and function, generated from the source.
• MIGRATION.md — 2.0 is a deliberate break from 1.0; this maps the old API onto the new one.
• ARCHITECTURE.md — how the library is put together, and why.

Citation

If you use dafsa in academic research, please cite:

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

License

MIT — see LICENSE.