Name Description Size
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