Welcome to dafsa’s documentation!¶
dafsa is a Python library for computing
Deterministic Acyclic Finite State
Automata
(also known as “directed acyclic word graphs”, or DAWG) for purposes of
data exploration and visualization. DAFSAs are data
structures derived from tries
that allow to represent a set of sequences (typically character strings
or n-grams) in the form of a directed acyclic graph with a single
source vertex (the start symbol shared by all sequences) and at least one
sink edge (final symbols, each pointed to by one or more sequences), such
as in the following image.
Example of a DAFSA graph from a selection of segmented Italian words transcribed in the International Phonetic Alphabet