re: predicting the future/streaming/"stitching", how do you need to remember more state for quantification beyond the state that needs to be maintained to suppo

re: predicting the future/streaming/"stitching", how do you need to remember more state for quantification beyond the state that needs to be maintained to support streaming at all? Why do you need to make a decision when you've reached the current block--can't that decision wait until you've seen more data or been told there is no more data? -- ...I can see that if you're using bit vectors to represent active states, that's how you can make use of SSE4/string instructions and POPCNT... I've been thinking about how to do that but it just doesn't seem to work with a VM implementation. Maybe for a hybrid filtration scheme, though... -- Have you implemented Watson's MultiRE with input skipping, or Wu-Manber? I've tried some hacky approaches to skipping before and the problem seems to be that a sufficiently large pattern set will always include a short pattern (e.g., "PE") and now you're stuck with a bad l-min. -- Ordering is horrible, both between patterns and within patterns (Perl's ordered alternation rules). It took us a couple years to get full compatibility with PCRE (for forensics, correctness is more important than line speed searching; and most of our input comes from spinning rust, not ephemeral packets). We had to sacrifice the strict guarantee on O(M)/static memory usage during searching in order to gain full compatibility. Fortunately, branch prediction and reserving memory remove pretty much remove that cost, so that with normal pattern sets we don't see mallocs. Streaming matching is criminally understudied from a theoretical perspective. You cannot match some patterns in O(M) memory in a streaming model as an NFA algorithm should. The one we know about is any time a lower priority path is a prefix for a higher priority prefix; you have to buffer the lower priority match until the high priority match resolves. E.g., "a+b|a" on a string of a's is pathological. These kinds of patterns can be detected; what I don't know is whether there are other classes (I don't think so, but...). -- I've always found the DPI use case fascinating, as it is a completely different input model than what I've worked on, which has its own rules, and yet has many of the same demanding theoretical requirements in its treatment of automata.