As for our secrets - they are not really secrets; anyone who wants to learn them can simply read our code. I will outline the literal discovery approach, though, as I'm inordinately proud of it (possibly for the wrong reasons):

We find 'factor' literals in a NFA Graph (a Glushkov automata embedded in a BGL graph; Glushkov automata are both our internal intermediate representation of regexes and an occasional implementation strategy) as follows: we explore the local neighborhood of a graph node and calculate 'if I wanted to cut the graph here, which literal strings would I need to see'. For example, if we have paths "abc" and "def" to a node, we would give this a score corresponding to "2 3-character literals" (pretty good). On the other hand, we could have a single path "abcdefghij" to the node (which would be a really good score - a low score) or we could have multiple short literals (say, corresponding to the expansion of \d - 10 1-character literals - really bad - a high score). If we can't find anything reasonable at all the score is effectively infinite. This allows us to score each edge in the graph. We then wire up our graph to a source and sink (at the start and end of the pattern) and do network flow and grab a min-cut. More or less - there are some wrinkles, but that's basically it.

This may or may not be the world's best idea, but I had hankered to find some weird use of netflow ever since a Graph Theory class in 1991, where a professor of mathematics showed us an algorithm to solve the stable marriages problem by reducing it to network flow. This was made more memorable by the fact that he, probably unintentionally, posited a slightly obscene formulation: all the boys were wired to a mysterious 'source', the girls to a mysterious 'sink', and some unknown substance flowed from the former group to the latter (!).

The min-cut trick has its problems, as it does things like scoring a graph where we cut with 5 different copies of the same literal "abc" as if they were distinct literals (having thrown away the way the scores were found when we do min-cut, which just treats the scores as a magic floating point number). But it's been fairly practical. Someone with a better grasp of abstract algebra and graph theory would be welcome to come along and tell us whether the thing that implements our score in min-cut could be more complex (some sort of class that cleverly tracks some or all of the 'sums of literals' and implements operations like + and min) and still allow the min-cut algorithms to work.

Cutting is also more complex for us given the fact that a 'late' cut isn't nearly as good for us as an 'early' cut if we are streaming, as the leftover bits of an NFA graph on the left of such a cut need to be evaluated all the time in streaming mode, while this isn't true to of the parts on the right of a cut. So in practice we don't really do the netflow algorithm in the pure form above (at least, not since version 2.something) but it still gets used. The fact that we are actually decomposing our problem also means that some cuts are better than others to leave a 'clean' set of engines also messes things up.

We'd love help working on this problem (hey, we're open source) but Building Your Own regex engine seems to be the thing everyone must do. It's probably a lot more fun than trying to grab a tractable bit to work on in a 100+Kloc source base.