Haoyu Zhai created LUCENE-10010:
-----------------------------------
Summary: Should we have a NFA Query?
Key: LUCENE-10010
URL: https://issues.apache.org/jira/browse/LUCENE-10010
Project: Lucene - Core
Issue Type: New Feature
Components: core/search
Affects Versions: main (9.0)
Reporter: Haoyu Zhai
Today when a {{RegexpQuery}} is created, it will be translated to NFA,
determinized to DFA and eventually become an {{AutomatonQuery}}, which is very
fast. However, not every NFA could be determinized to DFA easily, the example
given in LUCENE-9981 showed how easy could a short regexp break the determinize
process.
Maybe, instead of marking those kind of queries as adversarial cases, we could
make a new kind of NFA query, which execute directly on NFA and thus no need to
worry about determinize process or determinized DFA size. It should be slower,
but also makes those adversarial cases doable.
[This article|https://swtch.com/~rsc/regexp/regexp1.html] has provided a simple
but efficient way of searching over NFA, essentially it is a partial
determinize process that only determinize the necessary part of DFA. Maybe we
could give it a try?
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
