API Reference¶

This page is generated automatically from the docstrings in the dafsa package, so it always matches the installed code.

Finite-state structures for sequence data.

Sets of sequences are stored as automata in which every shared beginning and every shared ending is held once. The package structure, the API contract, the audit of 1.0 that motivated the 2.0 rewrite, and the decisions taken along the way are in ARCHITECTURE.md at the root of the repository.

The pieces: the frozen core (Alphabet, Automaton), the semiring layer (dafsa.semirings), the dictionary structures Trie, Dafsa and CompactDafsa, the substring indexes SuffixAutomaton and Cdawg, the counting layer that makes an automaton an index rather than only a set, the transducers Fst, and dafsa.export.

Examples:

>>> import dafsa
>>> automaton = dafsa.Dafsa.from_sequences(["tap", "taps", "top", "tops"])
>>> "taps" in automaton
True

>>> counted = dafsa.Dafsa.from_sequences(
...     ["tip", "tip", "tap"], semiring=dafsa.semirings.COUNTING
... )
>>> counted.weight("tip")
2

The automaton is also an index over its own language:

>>> len(automaton), automaton.unrank(0), automaton.rank(("t", "o", "p", "s"))
(4, ('t', 'a', 'p'), 3)

Alphabet ¶

Alphabet(tokens: Iterable[Token])

An ordered, immutable vocabulary of tokens.

Symbols are assigned by position: the token at index i of tokens has symbol i. The constructor preserves the order it is given; use from_sequences to derive a canonically ordered alphabet from data.

Parameters:

Name	Type	Description	Default
`tokens`	`Iterable[Token]`	The tokens, in the order symbols should be assigned. Repeats are ignored, keeping the first occurrence.	required

Examples:

>>> alphabet = Alphabet("abc")
>>> alphabet.id("b")
1
>>> alphabet.encode("cab")
(2, 0, 1)
>>> alphabet.decode((2, 0, 1))
('c', 'a', 'b')

tokens `property` ¶

tokens: tuple[Token, ...]

The tokens, indexed by symbol.

from_sequences `classmethod` ¶

from_sequences(sequences: Iterable[Sequence[Token]]) -> Alphabet

Build an alphabet from the tokens appearing in sequences.

Parameters:

Name	Type	Description	Default
`sequences`	`Iterable[Sequence[Token]]`	The sequences whose tokens make up the vocabulary.	required

Returns:

Type	Description
`Alphabet`	An alphabet over every distinct token seen, in sorted order where
`Alphabet`	the tokens are mutually comparable and in first-encountered order
`Alphabet`	otherwise.

Examples:

>>> Alphabet.from_sequences(["tip", "tap"]).tokens
('a', 'i', 'p', 't')

id ¶

id(token: Token) -> Symbol

Return the symbol for token.

Parameters:

Name	Type	Description	Default
`token`	`Token`	The token to look up.	required

Returns:

Type	Description
`Symbol`	The symbol assigned to `token`.

Raises:

Type	Description
`UnknownTokenError`	If `token` is not in the alphabet.

token ¶

token(symbol: Symbol) -> Token

Return the token for symbol.

Parameters:

Name	Type	Description	Default
`symbol`	`Symbol`	The symbol to look up.	required

Returns:

Type	Description
`Token`	The token assigned to `symbol`.

Raises:

Type	Description
`IndexError`	If `symbol` is out of range.

encode ¶

encode(sequence: Sequence[Token]) -> tuple[Symbol, ...]

Encode a sequence of tokens as symbols.

Parameters:

Name	Type	Description	Default
`sequence`	`Sequence[Token]`	The tokens to encode.	required

Returns:

Type	Description
`tuple[Symbol, ...]`	The encoded sequence.

Raises:

Type	Description
`UnknownTokenError`	If any token is not in the alphabet. Use `try_encode` when an unknown token is an expected outcome rather than an error.

try_encode ¶

try_encode(sequence: Sequence[Token]) -> tuple[Symbol, ...] | None

Encode a sequence of tokens, or report that it cannot be encoded.

This is what membership tests use: a sequence containing a token the automaton has never seen is simply not accepted, which is an answer rather than an error.

Parameters:

Name	Type	Description	Default
`sequence`	`Sequence[Token]`	The tokens to encode.	required

Returns:

Type	Description
`tuple[Symbol, ...] \| None`	The encoded sequence, or `None` if any token is unknown.

decode ¶

decode(symbols: Iterable[Symbol]) -> tuple[Token, ...]

Decode symbols back into tokens.

Parameters:

Name	Type	Description	Default
`symbols`	`Iterable[Symbol]`	The symbols to decode.	required

Returns:

Type	Description
`tuple[Token, ...]`	The decoded tokens.

Raises:

Type	Description
`IndexError`	If any symbol is out of range.

Automaton ¶

Automaton(alphabet: Alphabet, first: array[int], symbol: array[int], target: array[int], flags: array[int], semiring: Semiring[Any] = BOOLEAN, transition_weights: list[Any] | None = None, final_weights: list[Any] | None = None, labels: list[tuple[Symbol, ...]] | None = None, initial_weight: Any = None)

An immutable, deterministic, acyclic automaton in CSR form.

Instances are produced by a builder's freeze() and are not meant to be constructed directly: the constructor trusts its arguments, because the builder is what establishes the invariants they have to satisfy.

Parameters:

Name	Type	Description	Default
`alphabet`	`Alphabet`	The alphabet the symbols refer to.	required
`first`	`array[int]`	Offsets into the transition arrays, of length `num_states + 1`. The transitions of state `q` are `first[q]:first[q + 1]`.	required
`symbol`	`array[int]`	Transition symbols, ascending within each state's slice.	required
`target`	`array[int]`	Transition targets, parallel to `symbol`.	required
`flags`	`array[int]`	Per-state flag bits, one entry per state.	required
`semiring`	`Semiring[Any]`	The semiring the weights belong to.	`BOOLEAN`
`transition_weights`	`list[Any] \| None`	One weight per transition, or `None` when every transition weight is the semiring's `one`.	`None`
`final_weights`	`list[Any] \| None`	One weight per state, or `None` when every accepting state's weight is the semiring's `one`.	`None`
`labels`	`list[tuple[Symbol, ...]] \| None`	One compound label per transition, or `None` when every transition consumes exactly one token. A label is a tuple of symbols whose first element equals the transition's entry in `symbol`.	`None`
`initial_weight`	`Any`	A weight applied to every accepted sequence. `None` means the semiring's `one`. Weight pushing is what makes it non-trivial: moving weight towards the front has to leave it somewhere.	`None`

Notes

The invariants the constructor assumes, all established by freeze(): first is non-decreasing and starts at zero; symbol is strictly ascending within each state's slice, which is what makes the binary search in step correct and encodes determinism; every state is reachable from ROOT; and the transitions contain no cycle.

The two weight arrays are None in the common unweighted case rather than filled with copies of one. A plain acceptor therefore costs nothing for weights it does not use, which matters because memory frugality is much of the point of this representation. labels follows the same rule.

Compound labels do not change the CSR layout. symbol continues to hold one symbol per transition — the first of its label — so determinism, ascending order within a state, and the binary search in step all work exactly as before. What changes is only how many tokens a transition consumes.

alphabet `property` ¶

alphabet: Alphabet

The alphabet this automaton's symbols refer to.

semiring `property` ¶

semiring: Semiring[Any]

The semiring this automaton's weights belong to.

initial_weight `property` ¶

initial_weight: Any

The weight every accepted sequence carries before its path.

is_weighted `property` ¶

is_weighted: bool

Whether any weight differs from the semiring's one.

False means the automaton is a plain acceptor and stores no weight arrays; weight still answers, with one for accepted sequences.

is_compact `property` ¶

is_compact: bool

Whether any transition consumes more than one token.

num_states `property` ¶

num_states: int

The number of states.

num_transitions `property` ¶

num_transitions: int

The number of transitions.

states ¶

states() -> range

Return the states, as a range over their dense ids.

Returns:

Type	Description
`range`	`range(num_states)`, in canonical order.

is_final ¶

is_final(state: State) -> bool

Return whether state is accepting.

Parameters:

Name	Type	Description	Default
`state`	`State`	The state to inspect.	required

Returns:

Type	Description
`bool`	Whether a sequence ending at `state` is accepted.

out_degree ¶

out_degree(state: State) -> int

Return the number of transitions leaving state.

Parameters:

Name	Type	Description	Default
`state`	`State`	The state to inspect.	required

Returns:

Type	Description
`int`	The number of outgoing transitions.

final_weight ¶

final_weight(state: State) -> Any

Return the weight contributed by accepting at state.

Parameters:

Name	Type	Description	Default
`state`	`State`	The state to inspect.	required

Returns:

Type	Description
`Any`	The state's final weight, or the semiring's `zero` if the state is
`Any`	not accepting.

transition_weight ¶

transition_weight(index: int) -> Any

Return the weight of the transition at index.

Parameters:

Name	Type	Description	Default
`index`	`int`	A transition index, as produced by `transition_index`.	required

Returns:

Type	Description
`Any`	The transition's weight, or the semiring's `one` if the automaton
`Any`	stores no transition weights.

transition_indices ¶

transition_indices(state: State) -> range

Return the indices of state's transitions, in symbol order.

The index-based accessors below exist so that the dynamic programs can walk the arrays without allocating a Transition per step.

Parameters:

Name	Type	Description	Default
`state`	`State`	The state whose transitions to index.	required

Returns:

Type	Description
`range`	Indices into the transition arrays.

transition_symbol ¶

transition_symbol(index: int) -> Symbol

Return the first symbol consumed by the transition at index.

transition_target ¶

transition_target(index: int) -> State

Return the state entered by the transition at index.

transition_label ¶

transition_label(index: int) -> tuple[Symbol, ...]

Return every symbol consumed by the transition at index.

One symbol for an ordinary transition, several for a compacted one.

Parameters:

Name	Type	Description	Default
`index`	`int`	A transition index.	required

Returns:

Type	Description
`tuple[Symbol, ...]`	The transition's label.

transition_tokens ¶

transition_tokens(index: int) -> tuple[Token, ...]

Return the transition's label as caller-facing tokens.

Parameters:

Name	Type	Description	Default
`index`	`int`	A transition index.	required

Returns:

Type	Description
`tuple[Token, ...]`	The tokens the transition consumes.

transitions ¶

transitions(state: State) -> Iterator[Transition]

Iterate over the transitions leaving state, in symbol order.

Parameters:

Name	Type	Description	Default
`state`	`State`	The state whose transitions to yield.	required

Yields:

Type	Description
`Transition`	Each outgoing transition, carrying its weight.

all_transitions ¶

all_transitions() -> Iterator[Transition]

Iterate over every transition, ordered by source then symbol.

Yields:

Type	Description
`Transition`	Each transition in the automaton.

transition_index ¶

transition_index(state: State, symbol: Symbol) -> int | None

Return the index of state's transition on symbol.

The binary search is over one state's slice of the symbol array, which is ascending — the invariant that makes this correct is established by freeze().

Parameters:

Name	Type	Description	Default
`state`	`State`	The state to leave.	required
`symbol`	`Symbol`	The symbol to consume.	required

Returns:

Type	Description
`int \| None`	The transition's index into the transition arrays, or `None` if
`int \| None`	there is no such transition.

step ¶

step(state: State, symbol: Symbol) -> State | None

Follow one transition.

Parameters:

Name	Type	Description	Default
`state`	`State`	The state to leave.	required
`symbol`	`Symbol`	The symbol to consume.	required

Returns:

Type	Description
`State \| None`	The state reached, or `None` if `state` has no transition on
`State \| None`	`symbol`.

walk ¶

walk(symbols: Iterable[Symbol], start: State = ROOT) -> State | None

Follow a sequence of symbols.

The traversal is a loop, not a recursion, so sequence length is bounded by memory rather than by the interpreter's stack.

Parameters:

Name	Type	Description	Default
`symbols`	`Iterable[Symbol]`	The symbols to consume in order.	required
`start`	`State`	The state to start from. Defaults to `ROOT`.	`ROOT`

Returns:

Type	Description
`State \| None`	The state reached after consuming every symbol, or `None` if the
`State \| None`	path leaves the automaton partway through.

accepts ¶

accepts(sequence: Sequence[Token]) -> bool

Return whether sequence is accepted.

A sequence containing a token outside the alphabet is not accepted; that is an answer, not an error.

Parameters:

Name	Type	Description	Default
`sequence`	`Sequence[Token]`	The tokens to test.	required

Returns:

Type	Description
`bool`	Whether the automaton accepts `sequence`.

weight ¶

weight(sequence: Sequence[Token]) -> Any

Return the weight sequence is accepted with.

The weight is the semiring product of the transition weights along the path and the final weight of the state it ends at — which, for an automaton built from weighted sequences, is exactly the weight that sequence was inserted with.

This is the query 1.0's lookup() was reaching for and got wrong: there, weights were counters over a minimized graph, so the returned "cumulative weight" summed the frequencies of every sequence sharing an edge. DAFSA(["dib", "tip", "tips", "top"]).lookup("tip") gave 7 for a sequence inserted once.

Parameters:

Name	Type	Description	Default
`sequence`	`Sequence[Token]`	The tokens to weigh.	required

Returns:

Type	Description
`Any`	The sequence's weight, or the semiring's `zero` if it is not
`Any`	accepted. `zero` is the weight of a path that does not exist, so a
`Any`	rejection needs no special case at the call site.

match ¶

match(sequence: Sequence[Token]) -> Match | None

Return the full path sequence takes, or None if it is rejected.

Parameters:

Name	Type	Description	Default
`sequence`	`Sequence[Token]`	The tokens to match.	required

Returns:

Type	Description
`Match \| None`	The states visited, the transitions taken, and the weight.

Examples:

>>> from dafsa import Dafsa
>>> found = Dafsa.from_sequences(["tap"]).match("tap")
>>> found.states
(0, 1, 2, 3)
>>> len(found.transitions)
3

paths ¶

paths(sequence: Sequence[Token]) -> Iterator[Match]

Yield every accepting path for sequence.

A deterministic acceptor has at most one, so this yields nothing or one Match and match is the direct way to ask. It exists so that code written against the transducers — where a single input can have several analyses — reads the same against an acceptor.

Parameters:

Name	Type	Description	Default
`sequence`	`Sequence[Token]`	The tokens to match.	required

Yields:

Type	Description
`Match`	Each accepting path.

longest_prefix_of ¶

longest_prefix_of(sequence: Sequence[Token]) -> tuple[Token, ...] | None

Return the longest accepted prefix of sequence.

Useful for segmentation: repeatedly taking the longest accepted prefix of what remains is greedy longest-match tokenisation against a lexicon.

Parameters:

Name	Type	Description	Default
`sequence`	`Sequence[Token]`	The tokens to search within.	required

Returns:

Type	Description
`tuple[Token, ...] \| None`	The longest prefix of `sequence` that the automaton accepts, or
`tuple[Token, ...] \| None`	`None` if no prefix is accepted. The empty tuple is a valid answer
`tuple[Token, ...] \| None`	when the root is accepting.

Examples:

>>> from dafsa import Dafsa
>>> lexicon = Dafsa.from_sequences(["can", "candle"])
>>> lexicon.longest_prefix_of("candles")
('c', 'a', 'n', 'd', 'l', 'e')
>>> lexicon.longest_prefix_of("cane")
('c', 'a', 'n')
>>> lexicon.longest_prefix_of("dog") is None
True

starts_with ¶

starts_with(prefix: Sequence[Token]) -> Iterator[tuple[Token, ...]]

Yield the accepted sequences beginning with prefix, in order.

Costs the size of the answer, not the size of the language: the prefix is followed once to reach a state, and only that state's subtree is walked. This is the query an autocomplete is made of.

Parameters:

Name	Type	Description	Default
`prefix`	`Sequence[Token]`	The tokens every yielded sequence must start with.	required

Yields:

Type	Description
`tuple[Token, ...]`	Each accepted sequence extending `prefix`, in the alphabet's order.

Examples:

>>> from dafsa import Dafsa
>>> automaton = Dafsa.from_sequences(["tap", "taps", "top"])
>>> list(automaton.starts_with("ta"))
[('t', 'a', 'p'), ('t', 'a', 'p', 's')]

rank ¶

rank(sequence: Sequence[Token]) -> int

Return the position of sequence in iteration order.

Together with unrank this makes the automaton a minimal perfect hash over its own language: every accepted sequence maps to a distinct integer in range(len(automaton)), and back.

Parameters:

Name	Type	Description	Default
`sequence`	`Sequence[Token]`	An accepted sequence.	required

Returns:

Type	Description
`int`	Its zero-based position in `__iter__` order.

Raises:

Type	Description
`ValueError`	If the sequence is not accepted.

Examples:

>>> from dafsa import Dafsa
>>> automaton = Dafsa.from_sequences(["tap", "taps", "top"])
>>> [automaton.rank(word) for word in ("tap", "taps", "top")]
[0, 1, 2]

unrank ¶

unrank(position: int) -> tuple[Token, ...]

Return the accepted sequence at position.

The inverse of rank, and cheaper than it looks: whole subtrees are skipped by their known sizes, so the cost tracks the sequence's length rather than its position.

Parameters:

Name	Type	Description	Default
`position`	`int`	A zero-based position in `__iter__` order.	required

Returns:

Type	Description
`tuple[Token, ...]`	The sequence at that position.

Raises:

Type	Description
`IndexError`	If `position` is outside `range(len(automaton))`.

Examples:

>>> from dafsa import Dafsa
>>> Dafsa.from_sequences(["tap", "taps", "top"]).unrank(2)
('t', 'o', 'p')

suffix_count ¶

suffix_count(state: State) -> int

Return how many sequences are accepted from state.

Parameters:

Name	Type	Description	Default
`state`	`State`	The state to count from.	required

Returns:

Type	Description
`int`	The size of the state's right language.

topological_order ¶

topological_order() -> list[State]

Return the states with every state before all of its successors.

Exposed because it is the order any dynamic program over the structure needs, and because the canonical breadth-first numbering is not topological — a fact easy to assume otherwise and get wrong.

Returns:

Type	Description
`list[State]`	The states, sources before targets.

total_weight ¶

total_weight() -> Any

Return the semiring sum of every accepted sequence's weight.

For COUNTING this is the total number of insertions, as distinct from len(), which is the number of distinct sequences.

Returns:

Type	Description
`Any`	The total, or the semiring's `zero` for an empty language.

Examples:

>>> from dafsa import Dafsa
>>> from dafsa.semirings import COUNTING
>>> automaton = Dafsa.from_sequences(["tip", "tip", "tap"], semiring=COUNTING)
>>> len(automaton), automaton.total_weight()
(2, 3)

push ¶

push() -> Any

Return an equivalent automaton with its weight moved towards the front.

Every accepted sequence keeps exactly the weight it had. What changes is where along its path that weight sits: afterwards, the weights leaving any state combine with its final weight to the semiring's one, so a prefix's weight already tells you as much as it can about what follows.

Returns:

Type	Description
`Any`	A new automaton of the same class.

Raises:

Type	Description
`NotImplementedError`	If the semiring is not divisible, or if its multiplication does not commute.
`ZeroDivisionError`	If some state cannot reach an accepting state, since its potential is then the semiring's `zero`.

k_best ¶

k_best(k: int) -> list[tuple[tuple[Token, ...], Any]]

Return the k best accepted sequences with their weights.

Only meaningful when the semiring is idempotent, so that plus selects a better weight instead of accumulating.

Parameters:

Name	Type	Description	Default
`k`	`int`	How many to return.	required

Returns:

Type	Description
`list[tuple[tuple[Token, ...], Any]]`	Up to `k` `(sequence, weight)` pairs, best first.

Raises:

Type	Description
`NotImplementedError`	If the semiring is not idempotent.

Examples:

>>> from dafsa import Dafsa
>>> from dafsa.semirings import TROPICAL
>>> automaton = Dafsa.from_weighted(
...     [("tap", 2.0), ("taps", 0.5), ("top", 1.0)], semiring=TROPICAL
... )
>>> automaton.k_best(2)
[(('t', 'a', 'p', 's'), 0.5), (('t', 'o', 'p'), 1.0)]

Match ¶

Bases: NamedTuple

Everything known about one accepted sequence.

Returned by Automaton.match. This is the resolution of issue #8: 1.0's lookup() returned only the final node and an uninterpretable cumulative weight, so the path a sequence took was not recoverable without dropping to a graph library.

Transition ¶

Bases: NamedTuple

One outgoing transition of a state.

weight is typed Any because it belongs to whichever semiring the automaton was built over, and the automaton does not carry that type as a parameter. For an unweighted automaton it is the semiring's one.

AcyclicityError ¶

Bases: DafsaError, ValueError

The transitions being frozen contain a cycle.

Every structure in this library is acyclic; the algorithms that traverse a frozen automaton rely on it, so the cycle is rejected at freeze() rather than allowed to cause a non-terminating traversal later.

DafsaError ¶

Bases: Exception

Base class for every error raised by this library.

DeterminismError ¶

Bases: DafsaError, ValueError

A state was given two outgoing transitions on the same symbol.

The structures in this library are deterministic by construction, so this signals a defect in whatever drove the builder.

ExportError ¶

Bases: DafsaError, RuntimeError

An export could not be produced.

Raised when an external tool an export depends on is missing or fails — Graphviz, in practice. The automaton itself is fine; only the rendering of it could not be made.

UnknownTokenError ¶

Bases: DafsaError, KeyError

A token is not present in the alphabet.

Raised when encoding a sequence that contains a token the alphabet was not built from. Membership tests do not raise this: an unknown token simply means the sequence cannot be accepted.

Fst ¶

Fst(alphabet: Alphabet, first: array[int], symbol: array[int], target: array[int], flags: array[int], semiring: Semiring[Any] = BOOLEAN, transition_weights: list[Any] | None = None, final_weights: list[Any] | None = None, labels: list[tuple[Symbol, ...]] | None = None, initial_weight: Any = None)

Bases: Automaton

An acyclic weighted transducer over (input, output) pairs.

Examples:

>>> fst = Fst.from_pairs([("cat", "chat"), ("dog", "chien")])
>>> fst.apply("cat")
[('c', 'h', 'a', 't')]
>>> fst.apply("cow")
[]

Ambiguity is allowed, and reported as several results:

>>> ambiguous = Fst.from_alignments(
...     [[("a", "x")], [("a", "y")]]
... )
>>> sorted(ambiguous.apply("a"))
[('x',), ('y',)]

from_alignments `classmethod` ¶

from_alignments(alignments: Iterable[Sequence[Pair]], *, semiring: Semiring[Any] = BOOLEAN) -> Fst

Build a transducer from aligned pairs.

Parameters:

Name	Type	Description	Default
`alignments`	`Iterable[Sequence[Pair]]`	Each alignment is a sequence of `(input, output)` pairs, read in order. Either side of a pair may be `EPSILON`.	required
`semiring`	`Semiring[Any]`	The semiring weights belong to.	`BOOLEAN`

Returns:

Type	Description
`Fst`	The frozen, minimal transducer.

from_weighted_alignments `classmethod` ¶

from_weighted_alignments(pairs: Iterable[tuple[Sequence[Pair], Any]], *, semiring: Semiring[Any]) -> Fst

Build a transducer from weighted aligned pairs.

Parameters:

Name	Type	Description	Default
`pairs`	`Iterable[tuple[Sequence[Pair], Any]]`	`(alignment, weight)` pairs. Repeated alignments have their weights combined with the semiring's `plus`.	required
`semiring`	`Semiring[Any]`	The semiring the weights belong to.	required

Returns:

Type	Description
`Fst`	The frozen, minimal transducer.

from_pairs `classmethod` ¶

from_pairs(pairs: Iterable[tuple[Sequence[Token], Sequence[Token]]], *, semiring: Semiring[Any] = BOOLEAN) -> Fst

Build a transducer from unaligned sequence pairs.

Convenience only. The two sides are zipped position by position and the shorter one padded with EPSILON at the end. That is an alignment, not the right one for any particular linguistic purpose — for that, align deliberately and use from_alignments.

Parameters:

Name	Type	Description	Default
`pairs`	`Iterable[tuple[Sequence[Token], Sequence[Token]]]`	`(input, output)` sequence pairs.	required
`semiring`	`Semiring[Any]`	The semiring weights belong to.	`BOOLEAN`

Returns:

Type	Description
`Fst`	The frozen, minimal transducer.

apply ¶

apply(sequence: Sequence[Token]) -> list[tuple[Token, ...]]

Return every output the transducer relates to sequence.

Parameters:

Name	Type	Description	Default
`sequence`	`Sequence[Token]`	The input tokens.	required

Returns:

Type	Description
`list[tuple[Token, ...]]`	Each output, in the alphabet's order. Empty when the input is not
`list[tuple[Token, ...]]`	related to anything, several when the transducer is ambiguous.

project ¶

project(side: str = 'input') -> Dafsa

Return the acceptor for one side of the relation.

Parameters:

Name	Type	Description	Default
`side`	`str`	`"input"` or `"output"`.	`'input'`

Returns:

Type	Description
`Dafsa`	The minimal acceptor for the projected sequences, with epsilons
`Dafsa`	removed.

Raises:

Type	Description
`ValueError`	If `side` is neither `"input"` nor `"output"`.

Notes

The projection is unweighted. Projecting collapses the distinction between paths that shared a side, and reconciling their weights is weighted determinization — a genuinely different algorithm, and out of scope here. Dropping the weights is the honest option; carrying one arbitrary path's weight would not be.

Semiring ¶

Bases: Protocol[W]

The interface every semiring satisfies.

This is a Protocol, so any object with these members works — a caller's own semiring needs no inheritance and no registration. The built-ins below are annotated as Semiring[...] at the point they are created, which makes conformance a type error rather than a runtime surprise.

Attributes:

Name	Type	Description
`zero`	`W`	Additive identity and multiplicative annihilator. Conventionally the weight of a path that does not exist.
`one`	`W`	Multiplicative identity. The weight of the empty path.
`idempotent`	`bool`	Whether `plus(a, a) == a`. True for the min/max-based semirings, which lets algorithms discard all but the best of several paths.
`commutative`	`bool`	Whether `times` commutes. `plus` is required to commute by the semiring axioms, so this refers to `times` alone; it is false for things like a string-concatenation semiring.
`divisible`	`bool`	Whether `divide` is defined, which is what weight pushing needs.

plus ¶

plus(left: W, right: W) -> W

Combine weights of alternative paths.

times ¶

times(left: W, right: W) -> W

Combine weights along a single path.

key ¶

key(weight: W) -> Hashable

Return a hashable canonical form of weight.

Used as part of a state's signature during minimization. It exists so that a semiring whose weights are unhashable, or which represents one value in several ways, can still be minimized.

divide ¶

divide(left: W, right: W) -> W

Return the w with times(w, right) == left.

Raises:

Type	Description
`NotImplementedError`	If `divisible` is false.

CompactDafsa ¶

CompactDafsa(alphabet: Alphabet, first: array[int], symbol: array[int], target: array[int], flags: array[int], semiring: Semiring[Any] = BOOLEAN, transition_weights: list[Any] | None = None, final_weights: list[Any] | None = None, labels: list[tuple[Symbol, ...]] | None = None, initial_weight: Any = None)

Bases: _Structure

A path-compacted automaton: transitions may consume several tokens.

Produced by _Structure.compact. Where an ordinary automaton spends a state on each token of a forced chain, this spends one transition on the whole chain, which is what makes a drawn automaton readable at any size.

The token contract is unchanged. Membership, weights, ranking and iteration all still take and return sequences of the original tokens; the compound labels are an internal matter, visible through transition_tokens when a renderer needs them.

Examples:

>>> compacted = Dafsa.from_sequences(["tapas", "topos"]).compact()
>>> "tapas" in compacted, "tapa" in compacted
(True, False)
>>> sorted("".join(str(t) for t in s) for s in compacted)
['tapas', 'topos']

The single t transition out of the root now carries the whole forced prefix, and 1.0 raised IndexError on exactly this input:

>>> compacted.transition_tokens(0)
('t',)
>>> compacted.num_states
4

Dafsa ¶

Dafsa(alphabet: Alphabet, first: array[int], symbol: array[int], target: array[int], flags: array[int], semiring: Semiring[Any] = BOOLEAN, transition_weights: list[Any] | None = None, final_weights: list[Any] | None = None, labels: list[tuple[Symbol, ...]] | None = None, initial_weight: Any = None)

Bases: _Structure

A minimal deterministic acyclic finite-state automaton.

Equivalent states are shared, so the structure is as small as a deterministic automaton for this language can be. That sharing is what makes state ids meaningless as identifiers — a suffix state is reached by every prefix that leads to it — and it is why the counting layer, rather than the states themselves, is what answers questions about individual sequences.

Examples:

>>> dafsa = Dafsa.from_sequences(["tap", "taps", "top", "tops"])
>>> "tops" in dafsa, "to" in dafsa
(True, False)

The shared ps suffix is stored once, where a trie would store it twice:

>>> words = ["tap", "taps", "top", "tops"]
>>> dafsa.num_states < Trie.from_sequences(words).num_states
True

Weights mean what they say, which is the thing 1.0 could not do:

>>> from dafsa.semirings import COUNTING
>>> counted = Dafsa.from_sequences(["tip", "tip", "tap"], semiring=COUNTING)
>>> counted.weight("tip"), counted.weight("tap"), counted.weight("nope")
(2, 1, 0)

from_sequences `classmethod` ¶

from_sequences(sequences: Iterable[Sequence[Token]], *, semiring: Semiring[Any] = BOOLEAN) -> Dafsa

Build the minimal automaton accepting exactly sequences.

Parameters:

Name	Type	Description	Default
`sequences`	`Iterable[Sequence[Token]]`	The sequences to accept. Each is a sequence of hashable tokens; a `str` is one token per character. Order does not matter — the sorting the algorithm needs is done internally, over encoded symbols rather than over the caller's tokens.	required
`semiring`	`Semiring[Any]`	The semiring weights belong to. With the default, the result is a plain acceptor. With `COUNTING`, each sequence contributes `1`, so a repeated sequence gets its multiplicity.	`BOOLEAN`

Returns:

Type	Description
`Dafsa`	The frozen, minimal automaton.

from_weighted `classmethod` ¶

from_weighted(pairs: Iterable[tuple[Sequence[Token], Any]], *, semiring: Semiring[Any]) -> Dafsa

Build the minimal automaton from (sequence, weight) pairs.

Parameters:

Name	Type	Description	Default
`pairs`	`Iterable[tuple[Sequence[Token], Any]]`	The sequences and their weights. Repeated sequences have their weights combined with the semiring's `plus`.	required
`semiring`	`Semiring[Any]`	The semiring the weights belong to.	required

Returns:

Type	Description
`Dafsa`	The frozen, minimal automaton. Minimization is weight-aware: two
`Dafsa`	states are shared only if their weights agree as well as their
`Dafsa`	transitions, so `weight(seq)` returns what `seq` was inserted
`Dafsa`	with. That is stricter than unweighted minimization and yields more
`Dafsa`	states — the price of weights that mean something.

Trie ¶

Trie(alphabet: Alphabet, first: array[int], symbol: array[int], target: array[int], flags: array[int], semiring: Semiring[Any] = BOOLEAN, transition_weights: list[Any] | None = None, final_weights: list[Any] | None = None, labels: list[tuple[Symbol, ...]] | None = None, initial_weight: Any = None)

Bases: _Structure

A prefix tree: shared prefixes, no shared suffixes.

A trie is the honest baseline for the comparison this library was originally built to illustrate, and it remains useful whenever states need to be distinguishable by the prefix that reaches them — which minimization destroys, since a shared suffix state is reached by many prefixes.

Construction costs the same as Dafsa minus the register lookups, so a trie is never the cheaper choice; it is the choice that keeps prefixes distinct.

Examples:

>>> trie = Trie.from_sequences(["tap", "taps", "top"])
>>> "taps" in trie, "ta" in trie
(True, False)

One state per distinct prefix — t, ta, tap, taps, to, top — plus the root:

>>> trie.num_states
7

from_sequences `classmethod` ¶

from_sequences(sequences: Iterable[Sequence[Token]], *, semiring: Semiring[Any] = BOOLEAN) -> Trie

Build a trie accepting exactly sequences.

Parameters:

Name	Type	Description	Default
`sequences`	`Iterable[Sequence[Token]]`	The sequences to accept. Each is a sequence of hashable tokens; a `str` is one token per character.	required
`semiring`	`Semiring[Any]`	The semiring weights belong to. With the default, the result is a plain acceptor. With `COUNTING`, each sequence contributes `1`, so a repeated sequence gets its multiplicity.	`BOOLEAN`

Returns:

Type	Description
`Trie`	The frozen trie.

from_weighted `classmethod` ¶

from_weighted(pairs: Iterable[tuple[Sequence[Token], Any]], *, semiring: Semiring[Any]) -> Trie

Build a trie from (sequence, weight) pairs.

Parameters:

Name	Type	Description	Default
`pairs`	`Iterable[tuple[Sequence[Token], Any]]`	The sequences and their weights. Repeated sequences have their weights combined with the semiring's `plus`.	required
`semiring`	`Semiring[Any]`	The semiring the weights belong to.	required

Returns:

Type	Description
`Trie`	The frozen trie.

Cdawg ¶

Cdawg(alphabet: Alphabet, first: array[int], symbol: array[int], target: array[int], flags: array[int], semiring: Semiring[Any] = BOOLEAN, transition_weights: list[Any] | None = None, final_weights: list[Any] | None = None, labels: list[tuple[Symbol, ...]] | None = None, initial_weight: Any = None)

Bases: _SubstringIndex

A compact directed acyclic word graph: a path-compacted suffix automaton.

Produced by SuffixAutomaton.compact. Chains of states that every occurrence is forced through collapse into single transitions labelled with several tokens, which is what makes the structure small enough to draw and cheap enough to store for a long text.

Every query still takes and returns ordinary token sequences. A substring may now end part-way along a label, at a position with no state of its own; the queries account for that.

Examples:

>>> index = SuffixAutomaton.from_sequence("banana")
>>> compacted = index.compact()
>>> compacted.num_states < index.num_states
True
>>> compacted.contains_substring("nan"), compacted.contains_substring("nab")
(True, False)
>>> compacted.num_substrings() == index.num_substrings()
True

SuffixAutomaton ¶

SuffixAutomaton(alphabet: Alphabet, first: array[int], symbol: array[int], target: array[int], flags: array[int], semiring: Semiring[Any] = BOOLEAN, transition_weights: list[Any] | None = None, final_weights: list[Any] | None = None, labels: list[tuple[Symbol, ...]] | None = None, initial_weight: Any = None)

Bases: _SubstringIndex

The minimal automaton accepting every suffix of one sequence.

Accepting states mark the suffixes. Every substring is walkable from the root whether or not it ends at an accepting state, which is why contains_substring ignores acceptance and in does not.

Examples:

>>> index = SuffixAutomaton.from_sequence("banana")
>>> sorted("".join(s) for s in index)
['', 'a', 'ana', 'anana', 'banana', 'na', 'nana']

Every suffix is accepted; a substring merely occurs. nan occurs inside banana but is not a suffix of it, and the two queries differ:

>>> "nan" in index, index.contains_substring("nan")
(False, True)
>>> "nana" in index, index.contains_substring("nana")
(True, True)
>>> index.contains_substring("bana"), index.contains_substring("nab")
(True, False)

from_sequence `classmethod` ¶

from_sequence(sequence: Sequence[Token], *, semiring: Semiring[Any] = BOOLEAN) -> SuffixAutomaton

Build the suffix automaton of sequence.

Parameters:

Name	Type	Description	Default
`sequence`	`Sequence[Token]`	The sequence to index. A `str` is one token per character.	required
`semiring`	`Semiring[Any]`	The semiring weights belong to. Every weight is `one`; the parameter exists so an index composes with the rest of the library.	`BOOLEAN`

Returns:

Type	Description
`SuffixAutomaton`	The frozen index.

compact ¶

compact() -> Cdawg

Return the compacted form of this index.

Returns:

Type	Description
`Cdawg`	The compact directed acyclic word graph for the same sequence.

tokenize ¶

tokenize(text: str, sep: str | None = None) -> tuple[str, ...]

Split text into tokens.

The library's input contract is a sequence of tokens, and a str is a sequence of single characters. Multi-character tokens therefore need an explicit split, and this is it.

That explicitness is the fix for issue #17. 1.0 took a delimiter parameter that was never used to split anything — it only joined labels when compacting — so DAFSA(["a b c"], delimiter=" ") silently treated the spaces as tokens. The command-line tool split on whitespace before calling the library, which is why the CLI appeared to work while the API did not.

Parameters:

Name	Type	Description	Default
`text`	`str`	The text to split.	required
`sep`	`str \| None`	The separator. `None` splits on runs of whitespace and discards empty fields, matching `str.split`.	`None`

Returns:

Type	Description
`tuple[str, ...]`	The tokens.

Examples:

>>> tokenize("a b c")
('a', 'b', 'c')
>>> tokenize("a-b-c", "-")
('a', 'b', 'c')

Without it, a string is characters — which is a reasonable default, and now a visible choice rather than a surprise:

>>> tuple("a b")
('a', ' ', 'b')

compose ¶

compose(left: Fst, right: Fst, *, semiring: Semiring[Any] | None = None) -> Fst

Return the transducer relating left's input to right's output.

The standard product construction: a state of the result is a state of each input plus a filter marker, and a transition matches left's output against right's input.

Parameters:

Name	Type	Description	Default
`left`	`Fst`	The transducer applied first. Its output alphabet is matched against `right`'s input alphabet by token equality.	required
`right`	`Fst`	The transducer applied second.	required
`semiring`	`Semiring[Any] \| None`	The semiring of the result. Defaults to `left`'s.	`None`

Returns:

Type	Description
`Fst`	The composed transducer.

Raises:

Type	Description
`DeterminismError`	If the composition is ambiguous — if two composed paths carry the same `(input, output)` pair out of the same state. Resolving that needs weighted determinization, which is out of scope; the error names the pair so the ambiguity can be found in the inputs.

Notes

Epsilons are filtered after Mohri, Pereira and Riley: without a filter, a composition where left deletes and right inserts produces the same path by several interleavings.

Examples:

>>> upper = Fst.from_pairs([("cat", "CAT")])
>>> reverse = Fst.from_pairs([("CAT", "gato")])
>>> compose(upper, reverse).apply("cat")
[('g', 'a', 't', 'o')]

API Reference¶

Alphabet ¶

tokens property ¶

from_sequences classmethod ¶

id ¶

token ¶

encode ¶

try_encode ¶

decode ¶

Automaton ¶

alphabet property ¶

semiring property ¶

initial_weight property ¶

is_weighted property ¶

is_compact property ¶

num_states property ¶

num_transitions property ¶

states ¶

is_final ¶

out_degree ¶

final_weight ¶

transition_weight ¶

transition_indices ¶

transition_symbol ¶

transition_target ¶

transition_label ¶

transition_tokens ¶

transitions ¶

all_transitions ¶

transition_index ¶

step ¶

walk ¶

accepts ¶

weight ¶

match ¶

paths ¶

longest_prefix_of ¶

starts_with ¶

rank ¶

unrank ¶

suffix_count ¶

topological_order ¶

total_weight ¶

push ¶

k_best ¶

Match ¶

Transition ¶

AcyclicityError ¶

DafsaError ¶

DeterminismError ¶

ExportError ¶

UnknownTokenError ¶

Fst ¶

from_alignments classmethod ¶

from_weighted_alignments classmethod ¶

from_pairs classmethod ¶

apply ¶

project ¶

Semiring ¶

plus ¶

times ¶

key ¶

divide ¶

CompactDafsa ¶

Dafsa ¶

from_sequences classmethod ¶

from_weighted classmethod ¶

Trie ¶

from_sequences classmethod ¶

from_weighted classmethod ¶

Cdawg ¶

SuffixAutomaton ¶

from_sequence classmethod ¶

compact ¶

tokenize ¶

compose ¶

tokens `property` ¶

from_sequences `classmethod` ¶

alphabet `property` ¶

semiring `property` ¶

initial_weight `property` ¶

is_weighted `property` ¶

is_compact `property` ¶

num_states `property` ¶

num_transitions `property` ¶

from_alignments `classmethod` ¶

from_weighted_alignments `classmethod` ¶

from_pairs `classmethod` ¶

from_sequences `classmethod` ¶

from_weighted `classmethod` ¶

from_sequences `classmethod` ¶

from_weighted `classmethod` ¶

from_sequence `classmethod` ¶