dafsa 1.0

Installation and usage

The library can be installed as any standard Python library with pip, and used as demonstrated in the following snippet:

In any standard Python environment, dafsa can be installed with:

$ pip install dafsa

A conda package is also available, and can be installed (from the tresoldi channel) with:

$ conda install -c tresoldi dafsa

Detailed instructions on how to use the library can be found in the official documentation. For most purposes, it is enough to pass a list of sequences to the DAFSA object:

>>> from dafsa import DAFSA
>>> print(DAFSA(["dib", "tip", "tips", "top"]))
DAFSA with 8 nodes and 9 edges (4 inserted sequences)
  +-- #0: 0(#1/4:<d>/1|#4/4:<t>/3) [('t', 4), ('d', 1)]
  +-- #1: n(#2/1:<i>/1) [('i', 2)]
  +-- #2: n(#3/1:<b>/1) [('b', 3)]
  +-- #3: F() []
  +-- #4: n(#5/3:<i>/2|#8/3:<o>/1) [('i', 5), ('o', 8)]
  +-- #5: n(#6/2:<p>/2) [('p', 6)]
  +-- #6: F(#3/2:<s>/1) [('s', 3)]
  +-- #8: n(#3/1:<p>/1) [('p', 3)]

Full documentation is available at ReadTheDocs.io.

Showcase

• Basic example:

• Output can be textual, GML, DOT, or (via dot and third-party software) PNG, PDF, ASCII-art and Unicode-art:

                                 G                                A
                             +---------------------+          +----------+
                             |                     v          |          v
    #====#  C   +---+  G   +---+  C   +---+  G   +---+  A   +---+  T   +---+  A   #===#
+-- H 0  H ---> | 5 | ---> | 6 | ---> | 7 | ---> | 8 | ---> | 9 | ---> | 3 | ---> H 4 H
|   #====#      +---+      +---+      +---+      +---+      +---+      +---+      #===#
|     |    A                                                             ^
| G   +-----------+                                                      |
|                 v                                                      |
|   +----+  G   +---+  A   +---+  T                                      |
+-> | 20 | ---> | 1 | ---> | 2 | ----------------------------------------+
    +----+      +---+      +---+

                                 G                                A
                             ┌─────────────────────┐          ┌──────────┐
                             │                     ▼          │          ▼
    ╔════╗  C   ┌───┐  G   ┌───┐  C   ┌───┐  G   ┌───┐  A   ┌───┐  T   ┌───┐  A   ╔═══╗
┌── ║ 0  ║ ───▶ │ 5 │ ───▶ │ 6 │ ───▶ │ 7 │ ───▶ │ 8 │ ───▶ │ 9 │ ───▶ │ 3 │ ───▶ ║ 4 ║
│   ╚════╝      └───┘      └───┘      └───┘      └───┘      └───┘      └───┘      ╚═══╝
│     │    A                                                             ▲
│ G   └───────────┐                                                      │
│                 ▼                                                      │
│   ┌────┐  G   ┌───┐  A   ┌───┐  T                                      │
└─▶ │ 20 │ ───▶ │ 1 │ ───▶ │ 2 │ ────────────────────────────────────────┘
    └────┘      └───┘      └───┘

• With or without single-path joining:

Changelog

Version 0.6:

• Documentation improvements following JOSS review

• Fixed bug where node finality was not considered in minimization

Version 0.5.1:

• Minor changes in preparation for submission (including tagged release)

Version 0.5:

• Improvements in speed, particularly in the __eq__() method of DAFSANode and the _minimize() method of DAFSA. The computation of a DAFSA for the contents of /usr/share/dict/words in the test machine (99,171 sequences) is now performed in under 8 minutes.

• Added code from Daciuk’s packages in an extra directory, along with notes on license

Version 0.4:

• Full documentation for existing code

• Added GML, PDF, and SVG export

• Allow to access all options from command-line

Version 0.3:

• Allow to join transitions in single sub-paths

• Allows to export a DAFSA as a networkx graph

• Preliminary documentation at ReadTheDocs

Version 0.2.1:

• Added support for segmented data

Version 0.2:

• Added support for weighted edges and nodes

• Added DOT export and Graphviz generation

• Refined minimization method, which can be skipped if desired (resulting in a standard trie)

• Added examples in the resources, also used for test data

Version 0.1:

• First public release.

Roadmap

After 1.0:

• Preliminary generation of minimal regular expressions matching the contents of a DAFSA

• Consider adding support for empty transitions (or depend on the user aligning those)

• Work on options for nicer graphviz output (colors, widths, etc.)

Community guidelines

While the author can be contacted directly for support, it is recommended that third parties use GitHub standard features, such as issues and pull requests, to contribute, report problems, or seek support.

Contributing guidelines, including a code of conduct, can be found in the CONTRIBUTING.md file.

Author and citation

The library is developed by Tiago Tresoldi (tresoldi@shh.mpg.de).

The author has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. ERC Grant #715618, Computer-Assisted Language Comparison.

If you use dafsa, please cite it as:

Tresoldi, Tiago (2020). DAFSA, a a library for computing Deterministic Acyclic Finite State Automata. Version 1.0. Jena. Available at: https://github.com/tresoldi/dafsa

In BibTeX:

@misc{Tresoldi2020dafsa,
  author = {Tresoldi, Tiago},
  title = {DAFSA, a a library for computing Deterministic Acyclic Finite State Automata. Version 1.0.},
  howpublished = {\url{https://github.com/tresoldi/dafsa}},
  address = {Jena},
  year = {2020},
}