Confirm
574
edits
Changes
→Challenge: Fast Regex Matching: Linked to my half-completed work on regex trigram extraction.
ES lacks out-of-the-box support for trigram-accelerated regex searches. It does offer [https://lucene.apache.org/core/4_3_0/core/index.html?org%2Fapache%2Flucene%2Futil%2Fautomaton%2FRegExp.html some regexp query support] which uses term indices and [https://lucene.apache.org/core/4_3_0/core/index.html?org%2Fapache%2Flucene%2Futil%2Fautomaton%2FRegExp.html some clever enumeration] to deliver non-naive performance, but I wonder if it would be enough. I don't see how you can use a term index to accelerate a regex that may span terms. I suppose you could index each line as a single term and then start every non-anchored regex search with <code>.*</code>, but that seems like a great way to have an enormous number of unique terms and be super slow.
Here's how we could get ES up to trilite speeds without too much trouble. If we're willing to extract trigrams ourselves, we can could easily tell ES to filter down to the docs containing those, then run a regex prosaically across them. And it just so happens that PythonI's stdlib regex machinery is written in Pythonve done some work toward this. (I couldnHere't believe it eithers [https://github.) Take a look at sre_compilecom/erikrose/dxr/blob/trigrammer/dxr/trigrammer.py #L218 where I left off], and sre_parse.py. They literally build a Python list of instructions, like <code>here are ['charset', 'groupref_ignore', https://github...]<com/erikrose/dxr/blob/trigrammer/code>, and then pass that to <code>_sre.compile()<tests/code>, which is the only C speedup I seetest_trigrammer. Presumably, that returns a fast matcher of py some kind, with guts in machine language. So, we harness that existing regex parser, extract trigrams, and go to townpassing tests]. This actually gives us flexibility beyond what trilite provides, in that we have the option of running non-accelerated regex queries, foolish though that may be. And we have full control over the complexity of regexes that we allow, since that isn't buried in <code>re2</code> any longer. At any rate, it's something to consider.
=== Tentative Roadmap ===
