[
https://issues.apache.org/jira/browse/LUCENE-10010?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17462880#comment-17462880
]
ASF subversion and git services commented on LUCENE-10010:
----------------------------------------------------------
Commit c972c6a7754e9ff1f838ed72ff09e7def00be5f8 in lucene's branch
refs/heads/main from Patrick Zhai
[ https://gitbox.apache.org/repos/asf?p=lucene.git;h=c972c6a ]
LUCENE-10010 Introduce NFARunAutomaton to run NFA directly (#225)
LUCENE-10010 Introduce NFARunAutomaton to run NFA directly
Created 2 new interfaces ByteRunnable and TransisitonAccessor to represent
function necessary for performing automaton run. Introduced NFARunAutomaton and
incorporated into CompiledAutomaton and enables directly running AutomatonQuery
based on NFA for all codecs.
> 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: 9.0
> Reporter: Haoyu Zhai
> Priority: Major
> Time Spent: 11h 50m
> Remaining Estimate: 0h
>
> 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.20.1#820001)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
