You may be interested in the source code for my best-of-both-worlds Aho-Corasick implementation. It runs on a state-transition matrix (the fastest implementation) in an interleaved array (the smallest-data implementation). Typically 2.5 bytes of state machine for each byte of pattern text. The matrix is tuned for L1-cache-friendliness. The original google doc describing the technique is http://goo.gl/6decc. https://github.com/mischasan/aho-corasick
So what’s the big deal about this? Well, back in the late 70’s, Robert Tarjan tried this … but found that the “compile” step was ridiculously expensive, and unsuitable for large sets of patterns. He based his work on another researcher’s ideas about “interleaved arrays” which is a very cool idea (“ACISM” in the github source refers to “Aho-Corasick Interleaved State-transition Matrix”). Unfortunately, the idea of how best to do this was by a physical analogy: if you want to fill a bucket with rocks, gravel and sand, put the bigger (coarser) things in first, because the finer-grain things will fit in the gaps around them. Unfortunately, that produces the worst-case runtime behaviour.
Instead, I tried inserting the objects in random order, while using a “hint” array to skip searching in areas where a given object couldn’t possibly fit. Tarjan was right about interleaved arrays, just missed a trick in implementation. See the .pdf at github, or the google.doc article, to see how the compilation works. Or just have fun using the code.