You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "rmuir (via GitHub)" <gi...@apache.org> on 2025/02/06 18:52:13 UTC
[PR] Fix Operations.reverse() to not add non-deterministic dead states [lucene]
rmuir opened a new pull request, #14212:
URL: https://github.com/apache/lucene/pull/14212
Operations.reverse() can create dead states, but ones that have non-determinism, which is worse than just creating dead states since it causes Automaton.isDeterministic() to return false, e.g. treated as NFA. This can lead to unnecessary det() calls expecially if automaton gets bigger or more complex.
Operations.reverse() serves multiple use-cases today:
* Search engine use-cases trying to speed up leading wildcards
* Testing/academic use-case (Brzozowski minimize)
In the search engine use-case, it is used by both Lucene and Solr.
Lucene uses this method for infinite
automata (e.g. leading wildcard) to compute a common suffix. if the expression has one (e.g. "*foo"), then we'll need to evaluate many candidates: so we reverse the automaton as part of computing the common suffix. Then memcmp can be used to filter out candidates quickly.
Solr uses this method, where users can opt-in to also indexing the reversed form of every term, with a special marker to prevent false-positives from the extra reversed terms. At query-time, the reversed wildcard queries can be turned into something that looks more like a prefix query: https://github.com/apache/solr/blob/bca4cd630b9cff66ecc0431397a99f5289a6462b/solr/core/src/java/org/apache/solr/parser/SolrQueryParserBase.java#L1291-L1324
Move Operations.reverse(Automaton, Set) to AutomatonTestUtil, since it is too difficult to improve while also supporting this hook.
Fix Operations.reverse(Automaton) to remove dead states.
### Description
<!--
If this is your first contribution to Lucene, please make sure you have reviewed the contribution guide.
https://github.com/apache/lucene/blob/main/CONTRIBUTING.md
-->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Fix Operations.reverse() to not add non-deterministic dead states [lucene]
Posted by "rmuir (via GitHub)" <gi...@apache.org>.
rmuir merged PR #14212:
URL: https://github.com/apache/lucene/pull/14212
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org