/dictomaton

Finite state dictionaries in Java

Primary LanguageJavaApache License 2.0Apache-2.0

dictomaton

Introduction

This Java library implements dictionaries that are stored in finite state automata. Dictomaton has the following features:

  • Finite state dictionaries that implement the Java Set interface.
  • Perfect hash dictionaries, that provide a unique hash for each character sequence that is in the dictionary. Perfect hash dictionaries can be used in two directions: (1) obtaining the hash code for a character sequence and (2) obtaining the character sequence for a hash code.
  • Levenshtein automata, that allow you to efficiently find all the sequences in the dictionary that are within the given edit distance of a sequence.
  • String to primitive type mappings, where the keys are stored in a perfect hashing automaton and the values in an (unboxed) array.

Comparisons

The following table compares the sizes of the object graphs of the Dictionary type of this library to that of TreeSet and HashSet. The comparisons were obtained by storing all the words in the web2 and web2a dictionaries and were measured using memory-measurer

Data typeObjectsReferencescharintbooleanfloat
TreeSet936277187255531937496241843120910
HashSet9362771772657319374993627711
Dictionary411889454642416939703311

Benchmarks

Benchmarks are in a different test group than normal unit tests. You can run benchmarks via Maven, adding the Benchmarks group:

mvn test -Djunit.groups=eu.danieldk.dictomaton.categories.Benchmarks

Changelog

0.0.4

  • Added Levenshtein automata for looking up sequences in a Dictionary that are within a certain edit distance of a sequence.

0.0.3

  • Fix an off-by-one error in integer width of the state table.

0.0.2

  • Rename the project from fsadict-java to dictomaton.
  • Store the state and transition tables as packed int arrays, resulting in drastically smaller automata.

Release plan

  • 0.0.5: add ImmutableStringStringMap, wherein values are also stored in an automaton.
  • 0.0.6: generic object values.
  • 1.0.0: first stable release.

Plans for 1.2.0: Perhaps an explicit, fast, and compact data storage format as an alternative to Java serialization. C or C++ version.