| incremental_dafsa.py |
Incremental algorithm for creating a "deterministic acyclic finite state
automaton" (DAFSA). At the time of writing this algorithm, there was existing logic
that depended on a different format for the DAFSA, so this contains convenience
functions for converting to a compatible structure. This legacy format is defined
in make_dafsa.py.
|
19462 |
| make_dafsa.py |
|
12040 |
| perfecthash.py |
A perfect hash function (PHF) is a function which maps distinct elements from a
source set to a sequence of integers with no collisions.
PHFs generated by this module use a 32-bit FNV hash to index an intermediate
table. The value from that table is then used to run a second 32-bit FNV hash to
get a final index.
The algorithm works by starting with the largest set of conflicts, and testing
intermediate table values until no conflicts are generated, allowing efficient
index lookup at runtime. (see also: http://stevehanov.ca/blog/index.php?id=119)
NOTE: This perfect hash generator was designed to be simple, easy to follow, and
maintainable, rather than being as optimized as possible, due to the relatively
small dataset it was designed for. In the future we may want to optimize further.
|
13560 |