  We revisit the popular \emph{delayed deterministic finite automaton}
(\ddfa{}) compression algorithm introduced by Kumar~et~al.~[SIGCOMM 2006] for
compressing deterministic finite automata (DFAs) used in intrusion detection
systems. This compression scheme exploits similarities in the outgoing sets of
transitions among states to achieve strong compression while maintaining high
throughput for matching.
  The \ddfa{} algorithm and later variants of it, unfortunately, require at
least quadratic compression time since they compare all pairs of states to
compute an optimal compression. This is too slow and, in some cases, even
infeasible for collections of regular expression in modern intrusion detection
systems that produce DFAs of millions of states.
  Our main result is a simple, general framework for constructing \ddfa{} based
on locality-sensitive hashing that constructs an approximation of the optimal
\ddfa{} in near-linear time. We apply our approach to the original \ddfa{}
compression algorithm and two important variants, and we experimentally
evaluate our algorithms on DFAs from widely used modern intrusion detection
systems. Overall, our new algorithms compress up to an order of magnitude
faster than existing solutions with either no or little loss of compression
size. Consequently, our algorithms are significantly more scalable and can
handle larger collections of regular expressions than previous solutions.
