hyperscan

Dyalog implementor here. The hot loops in this function are running my code! I'm not surprised at all about this result, although I certainly wouldn't use it to make a pronouncement about Dyalog or C as a whole. But there are some places where interpreted array languages have a major advantage over typical compiled languages. One of the advantages seen in this wc function is our use of bit booleans rather than byte booleans. Packing 8 bits in a byte uses eight times less space, and can lead to drastic speed improvements: 2-8 times faster than even code which uses short ints. On that note, the function words←{(~(¯1)↑⍵)++/1=(1↓⍵)-(¯1)↓⍵} can be improved by keeping the data boolean. 1=(1↓⍵)-(¯1)↓⍵ is equivalent to the windowed reduction 2</⍵ which identifies places where the boolean argument increased in value. We get: words←{(~¯1↑⍵)++/

We wrote a generalization of the Levenshtein distance algorithm for regular expressions in Hyperscan (https://github.com/intel/hyperscan), which allows you to do Levenstein distance matching over regular expressions. It is not necessarily a cheap thing to do, given that incautious use of edit distances and permissive regular expressions can result in automata that match almost anything. I believe that the first widely available approximate regex matcher was Tre (https://laurikari.net/tre/). However, while everybody wants to talk about approximate matching like they have something to say, most algorithmists act like they forgot about Tre.

But if you want faster, (but more complicated): https://github.com/intel/hyperscan

It looks like there are some interesting things in this project beyond regex, but the way that it skates over the fact that there are already automata-based multiple pattern matchers is pretty rank. When we started developing automata-based pattern matching s/w in 2006 - 2006! - we were well aware that it wasn't really a new thing. 12 years of work on Hyperscan (https://github.com/intel/hyperscan), 1 acquisition and 1 open source release later - as well as multiple other projects doing similar things (re2, Rust regex, Parabix, icgrep, Rosie Pattern Language, ...) has only added to this crowded field. All this has taught me many things, but the thing that I keep returning to is that "a lot of people apparently don't know about prior art, or assiduously pretend not to". It will be interesting to see what they try to patent.

> 2. Nevod matches MULTIPLE patterns against document in ONE PASS. Patters/expressions are indexed by state machine and filtered effectively during matching. This is a good idea. It's such a good idea that we did it in 2006, sold a company to Intel based around in in 2013 and open-sourced the resulting library (https://github.com/intel/hyperscan) in 2015. All multi-pattern systems get a huge improvement over one-at-a-time regex. It would be embarrassing if they did not. Our rule of thumb for Hyperscan was that it should be about 5-10x faster than libpcre on single patterns and the gap should get progressively bigger. I don't doubt that there is quite a bit of interesting work (entirely outside of regex - the word-based focus looks interesting) going on in this project, but the fact that you couldn't be bothered to Google around for a sens