I am attempting to understand the inner workings of the open source string matching library Hyperscan.
It takes a multiple-engine approach to the problem of generating string matches, and I'm still in the early stages of following through the debugging output to see how it does what it does.
However, one design decision already visible at this point puzzles me: when constructing an NFA, it doesn't use the traditional model of a directed graph with edges labeled with characters, and nodes labeled with whether or not they accept. Instead, it seems to use a model (*) of a directed graph with unlabeled edges and nodes labeled with a set of characters that can reach this node, along with designated special nodes for accepting strings. (specifically, it has a special
NODE_ACCEPT node and a special
NODE_ACCEPT_EOD node; nodes that mean "accept and ignore remaining input" have edges to
NODE_ACCEPT and nodes that mean "accept if at end of input" have edges to
I think this model is equivalent to the standard NFA model, but I can't find any references to this NFA model anywhere; I wonder if it goes by a standard name that I just don't know, and therefore can't search for. (My attempts just get buried in page after page of explanations of the standard NFA model)
So, has anyone seen an NFA model like this before? Are there any references I can look at to find out why one might prefer a model like this?
(On the off chance that anyone has already written up something on how the compiler and the various string matching engines embedded inside the Hyperscan library work, I'd also love any pointers to that. I primarily want to learn about state-of-the-art string-matching techniques, not about how to reverse-engineer C++.)
(*) I'm simplifying slightly here and ignoring bits of node and edge labels that seem unused at the initial stages.