[Lightning] automata, minimal perfect hash functions, and gnu lightning

[Johnicholas Hines]

Hi. I have an application, and I was wondering whether lightning would
be appropriate.

One way to represent a set of strings is with a hash table.
To perform a lookup, you put the requested string through the hash
function, and get a bin.
If the set of strings is fixed in advance (reserved words for
programming languages), people sometimes try to pick a "good" hash
function for that set.
A "perfect" hash function is one that has no collisions.
A "minimal" hash function is one that has no empty bins.

gperf uses a probabilistic method to find minimal perfect hash
functions, and doesn't guarantee success.

A finite automaton could read a string and return a bin. Building such
a finite automaton would be a deterministic way to make minimal
perfect hash functions. If you can build the automaton fast and also
run the automaton on input fast, you might be able to use minimal
perfect hash functions in more dynamic situations than just reserved
words for programming languages.

Could I use lightning to build fast finite automata? Are there any alternatives?

Johnicholas