You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by GitBox <gi...@apache.org> on 2021/03/05 08:00:38 UTC
[GitHub] [lucene-solr] donnerpeter opened a new pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
donnerpeter opened a new pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457
<!--
_(If you are a project committer then you may remove some/all of the following template.)_
Before creating a pull request, please file an issue in the ASF Jira system for Lucene or Solr:
* https://issues.apache.org/jira/projects/LUCENE
* https://issues.apache.org/jira/projects/SOLR
You will need to create an account in Jira in order to create an issue.
The title of the PR should reference the Jira issue number in the form:
* LUCENE-####: <short description of problem or changes>
* SOLR-####: <short description of problem or changes>
LUCENE and SOLR must be fully capitalized. A short description helps people scanning pull requests for items they can work on.
Properly referencing the issue in the title ensures that Jira is correctly updated with code review comments and commits. -->
# Description
`ngram` is expensive (O(N*M*M)) but we can make it O(N) by precompiling some automatons, specialized for the case `n=3` and `weighted=false`
# Solution
Collect all substrings with length <= 3 of the misspelled word being checked against all dictionary entries, build an automaton matching them all, run it as we go along each dictionary entry, check which substrings match and add the score accordingly.
# Tests
`TestTrigramAutomaton` checks the algorithm equivalence. `TestPerformance.en_suggest` becomes ~13% faster.
# Checklist
Please review the following and check all that apply:
- [x] I have reviewed the guidelines for [How to Contribute](https://wiki.apache.org/solr/HowToContribute) and my code conforms to the standards described there to the best of my ability.
- [x] I have created a Jira issue and added the issue ID to my pull request title.
- [x] I have given Solr maintainers [access](https://help.github.com/en/articles/allowing-changes-to-a-pull-request-branch-created-from-a-fork) to contribute to my PR branch. (optional but recommended)
- [x] I have developed this patch against the `master` branch.
- [x] I have run `./gradlew check`.
- [x] I have added tests for my changes.
- [ ] I have added documentation for the [Ref Guide](https://github.com/apache/lucene-solr/tree/master/solr/solr-ref-guide) (for Solr changes only).
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] donnerpeter commented on a change in pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
donnerpeter commented on a change in pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457#discussion_r588100517
##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/GeneratingSuggester.java
##########
@@ -67,14 +66,15 @@
PriorityQueue<Weighted<Root<String>>> roots = new PriorityQueue<>(natural.reversed());
List<Root<String>> entries = new ArrayList<>();
boolean ignoreTitleCaseRoots = originalCase == WordCase.LOWER && !dictionary.hasLanguage("de");
- EnumSet<NGramOptions> options = EnumSet.of(NGramOptions.LONGER_WORSE);
+ TrigramAutomaton automaton = new TrigramAutomaton(word);
IntsRefFSTEnum<IntsRef> fstEnum = new IntsRefFSTEnum<>(dictionary.words);
InputOutput<IntsRef> mapping;
while ((mapping = nextKey(fstEnum, word.length() + 4)) != null) {
speller.checkCanceled.run();
IntsRef key = mapping.input;
+ assert key.length > 0;
Review comment:
Again, we don't store empty entries. Just make sure of that here as well :)
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] donnerpeter commented on a change in pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
donnerpeter commented on a change in pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457#discussion_r588101697
##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/GeneratingSuggester.java
##########
@@ -374,14 +373,9 @@ private static int commonPrefix(String s1, String s2) {
}
// generate an n-gram score comparing s1 and s2
- private static int ngram(int n, String s1, String s2, EnumSet<NGramOptions> opt) {
- int score = 0;
+ static int ngramScore(int n, String s1, String s2, boolean weighted) {
int l1 = s1.length();
- int l2 = s2.length();
- if (l2 == 0) {
Review comment:
Some special logic for empty dictionary entries, which we now don't have
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] donnerpeter commented on a change in pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
donnerpeter commented on a change in pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457#discussion_r588100307
##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/GeneratingSuggester.java
##########
@@ -67,14 +66,15 @@
PriorityQueue<Weighted<Root<String>>> roots = new PriorityQueue<>(natural.reversed());
List<Root<String>> entries = new ArrayList<>();
boolean ignoreTitleCaseRoots = originalCase == WordCase.LOWER && !dictionary.hasLanguage("de");
- EnumSet<NGramOptions> options = EnumSet.of(NGramOptions.LONGER_WORSE);
+ TrigramAutomaton automaton = new TrigramAutomaton(word);
Review comment:
`ngram` call has been replaced with the automaton and special logic for former `LONGER_WORSE` functionality (see below)
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] donnerpeter commented on pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
donnerpeter commented on pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457#issuecomment-791466479
Thanks for the suggestion, but it works on code points as well, which I'd
prefer to leave out for now.
On Fri, 5 Mar 2021 at 15:35, Robert Muir <no...@github.com> wrote:
> *@rmuir* commented on this pull request.
> ------------------------------
>
> In
> lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/TrigramAutomaton.java
> <https://github.com/apache/lucene-solr/pull/2457#discussion_r588339682>:
>
> > + Automaton.Builder builder = new Automaton.Builder(s1.length() * N, s1.length() * N);
> + int initialState = builder.createState();
> +
> + for (int start = 0; start < s1.length(); start++) {
> + int limit = Math.min(s1.length(), start + N);
> + for (int end = start + 1; end <= limit; end++) {
> + substringCounts.merge(s1.substring(start, end), 1, Integer::sum);
> + }
> +
> + int state = initialState;
> + for (int i = start; i < limit; i++) {
> + int next = builder.createState();
> + builder.addTransition(state, next, s1.charAt(i));
> + state = next;
> + }
> + }
>
> fyi this automaton seems to be just a set of strings, i'm not sure if
> DaciukMihovAutomatonBuilder is helpful here, because i don't know the
> threshold where it starts to matter. but it is an alternative to building
> NFA and then determinizing it
>
> —
> You are receiving this because you authored the thread.
> Reply to this email directly, view it on GitHub
> <https://github.com/apache/lucene-solr/pull/2457#pullrequestreview-605241545>,
> or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/AAA5ZGOGGRTR5SNT72G566TTCDTZTANCNFSM4YUX3ODA>
> .
>
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] rmuir merged pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
rmuir merged pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] rmuir commented on a change in pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
rmuir commented on a change in pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457#discussion_r588317811
##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/TrigramAutomaton.java
##########
@@ -0,0 +1,122 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.analysis.hunspell;
+
+import java.util.HashMap;
+import java.util.Map;
+import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.automaton.Automaton;
+import org.apache.lucene.util.automaton.CharacterRunAutomaton;
+import org.apache.lucene.util.automaton.Operations;
+
+/**
+ * An automaton allowing to achieve the same results as non-weighted {@link
+ * GeneratingSuggester#ngramScore}, but faster (in O(s2.length) time).
+ */
+class TrigramAutomaton {
+ private static final int N = 3;
+ private final CharacterRunAutomaton automaton;
+ private final int[] state2Score;
+ private final FixedBitSet countedSubstrings;
+
+ TrigramAutomaton(String s1) {
+ Map<String, Integer> substringCounts = new HashMap<>();
+
+ Automaton.Builder builder = new Automaton.Builder(s1.length() * N, s1.length() * N);
+ int initialState = builder.createState();
+
+ for (int start = 0; start < s1.length(); start++) {
+ int limit = Math.min(s1.length(), start + N);
+ for (int end = start + 1; end <= limit; end++) {
+ substringCounts.merge(s1.substring(start, end), 1, Integer::sum);
+ }
+
+ int state = initialState;
+ for (int i = start; i < limit; i++) {
+ int next = builder.createState();
+ builder.addTransition(state, next, s1.charAt(i));
+ state = next;
+ }
+ }
+
+ automaton =
+ new CharacterRunAutomaton(
Review comment:
Both Automaton.step and CharacterRunAutomaton.step are binary search (transition labels vs character classes, which probably isn't very different here)
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] donnerpeter commented on a change in pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
donnerpeter commented on a change in pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457#discussion_r588105332
##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/TrigramAutomaton.java
##########
@@ -0,0 +1,122 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.analysis.hunspell;
+
+import java.util.HashMap;
+import java.util.Map;
+import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.automaton.Automaton;
+import org.apache.lucene.util.automaton.CharacterRunAutomaton;
+import org.apache.lucene.util.automaton.Operations;
+
+/**
+ * An automaton allowing to achieve the same results as non-weighted {@link
+ * GeneratingSuggester#ngramScore}, but faster (in O(s2.length) time).
+ */
+class TrigramAutomaton {
+ private static final int N = 3;
+ private final CharacterRunAutomaton automaton;
+ private final int[] state2Score;
+ private final FixedBitSet countedSubstrings;
+
+ TrigramAutomaton(String s1) {
+ Map<String, Integer> substringCounts = new HashMap<>();
+
+ Automaton.Builder builder = new Automaton.Builder(s1.length() * N, s1.length() * N);
+ int initialState = builder.createState();
+
+ for (int start = 0; start < s1.length(); start++) {
+ int limit = Math.min(s1.length(), start + N);
+ for (int end = start + 1; end <= limit; end++) {
+ substringCounts.merge(s1.substring(start, end), 1, Integer::sum);
+ }
+
+ int state = initialState;
+ for (int i = start; i < limit; i++) {
+ int next = builder.createState();
+ builder.addTransition(state, next, s1.charAt(i));
+ state = next;
+ }
+ }
+
+ automaton =
+ new CharacterRunAutomaton(
+ Operations.determinize(builder.finish(), Operations.DEFAULT_MAX_DETERMINIZED_STATES));
+
+ state2Score = new int[automaton.getSize()];
+ for (Map.Entry<String, Integer> entry : substringCounts.entrySet()) {
+ int state = runAutomatonOnStringChars(entry.getKey());
+ assert state2Score[state] == 0;
+ state2Score[state] = entry.getValue();
+ }
+ countedSubstrings = new FixedBitSet(state2Score.length);
+ }
+
+ private int runAutomatonOnStringChars(String s) {
Review comment:
I could've used utilities, but they operate on code points, and making the original algorithm work with them isn't very trivial. So maybe another time.
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] rmuir commented on a change in pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
rmuir commented on a change in pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457#discussion_r588280433
##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/TrigramAutomaton.java
##########
@@ -0,0 +1,122 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.analysis.hunspell;
+
+import java.util.HashMap;
+import java.util.Map;
+import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.automaton.Automaton;
+import org.apache.lucene.util.automaton.CharacterRunAutomaton;
+import org.apache.lucene.util.automaton.Operations;
+
+/**
+ * An automaton allowing to achieve the same results as non-weighted {@link
+ * GeneratingSuggester#ngramScore}, but faster (in O(s2.length) time).
+ */
+class TrigramAutomaton {
+ private static final int N = 3;
+ private final CharacterRunAutomaton automaton;
+ private final int[] state2Score;
+ private final FixedBitSet countedSubstrings;
+
+ TrigramAutomaton(String s1) {
+ Map<String, Integer> substringCounts = new HashMap<>();
+
+ Automaton.Builder builder = new Automaton.Builder(s1.length() * N, s1.length() * N);
+ int initialState = builder.createState();
+
+ for (int start = 0; start < s1.length(); start++) {
+ int limit = Math.min(s1.length(), start + N);
+ for (int end = start + 1; end <= limit; end++) {
+ substringCounts.merge(s1.substring(start, end), 1, Integer::sum);
+ }
+
+ int state = initialState;
+ for (int i = start; i < limit; i++) {
+ int next = builder.createState();
+ builder.addTransition(state, next, s1.charAt(i));
+ state = next;
+ }
+ }
+
+ automaton =
+ new CharacterRunAutomaton(
Review comment:
just curious, did you try this algorithm without tableizing Automaton into RunAutomaton? The RunAutomaton has some initial construction costs... at some point when you run enough strings through it, that investment pays off and was worth your time. But I don't know the numbers here and whether or not it is worth it
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] donnerpeter commented on a change in pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
donnerpeter commented on a change in pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457#discussion_r588099915
##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/Dictionary.java
##########
@@ -1025,6 +1025,7 @@ private int writeNormalizedWordEntry(StringBuilder reuse, ByteSequencesWriter wr
assert morphSep > 0;
assert morphSep > flagSep;
int sep = flagSep < 0 ? morphSep : flagSep;
+ if (sep == 0) return 0;
Review comment:
We don't store empty dictionary entries anymore: they bring no benefits, only trouble.
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] donnerpeter commented on a change in pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
donnerpeter commented on a change in pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457#discussion_r588288024
##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/TrigramAutomaton.java
##########
@@ -0,0 +1,122 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.analysis.hunspell;
+
+import java.util.HashMap;
+import java.util.Map;
+import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.automaton.Automaton;
+import org.apache.lucene.util.automaton.CharacterRunAutomaton;
+import org.apache.lucene.util.automaton.Operations;
+
+/**
+ * An automaton allowing to achieve the same results as non-weighted {@link
+ * GeneratingSuggester#ngramScore}, but faster (in O(s2.length) time).
+ */
+class TrigramAutomaton {
+ private static final int N = 3;
+ private final CharacterRunAutomaton automaton;
+ private final int[] state2Score;
+ private final FixedBitSet countedSubstrings;
+
+ TrigramAutomaton(String s1) {
+ Map<String, Integer> substringCounts = new HashMap<>();
+
+ Automaton.Builder builder = new Automaton.Builder(s1.length() * N, s1.length() * N);
+ int initialState = builder.createState();
+
+ for (int start = 0; start < s1.length(); start++) {
+ int limit = Math.min(s1.length(), start + N);
+ for (int end = start + 1; end <= limit; end++) {
+ substringCounts.merge(s1.substring(start, end), 1, Integer::sum);
+ }
+
+ int state = initialState;
+ for (int i = start; i < limit; i++) {
+ int next = builder.createState();
+ builder.addTransition(state, next, s1.charAt(i));
+ state = next;
+ }
+ }
+
+ automaton =
+ new CharacterRunAutomaton(
Review comment:
Because `step` seems faster there (O(1) instead of binary search, if I understand correctly)
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] rmuir commented on a change in pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
rmuir commented on a change in pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457#discussion_r588339682
##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/TrigramAutomaton.java
##########
@@ -0,0 +1,122 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.analysis.hunspell;
+
+import java.util.HashMap;
+import java.util.Map;
+import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.automaton.Automaton;
+import org.apache.lucene.util.automaton.CharacterRunAutomaton;
+import org.apache.lucene.util.automaton.Operations;
+
+/**
+ * An automaton allowing to achieve the same results as non-weighted {@link
+ * GeneratingSuggester#ngramScore}, but faster (in O(s2.length) time).
+ */
+class TrigramAutomaton {
+ private static final int N = 3;
+ private final CharacterRunAutomaton automaton;
+ private final int[] state2Score;
+ private final FixedBitSet countedSubstrings;
+
+ TrigramAutomaton(String s1) {
+ Map<String, Integer> substringCounts = new HashMap<>();
+
+ Automaton.Builder builder = new Automaton.Builder(s1.length() * N, s1.length() * N);
+ int initialState = builder.createState();
+
+ for (int start = 0; start < s1.length(); start++) {
+ int limit = Math.min(s1.length(), start + N);
+ for (int end = start + 1; end <= limit; end++) {
+ substringCounts.merge(s1.substring(start, end), 1, Integer::sum);
+ }
+
+ int state = initialState;
+ for (int i = start; i < limit; i++) {
+ int next = builder.createState();
+ builder.addTransition(state, next, s1.charAt(i));
+ state = next;
+ }
+ }
Review comment:
fyi this automaton seems to be just a set of strings, i'm not sure if DaciukMihovAutomatonBuilder is helpful here, because i don't know the threshold where it starts to matter. but it is an alternative to building NFA and then determinizing it
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] rmuir commented on pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
rmuir commented on pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457#issuecomment-791471797
> The latter is ~10% faster, so there's some difference. `RunAutomaton.step` has a constant-time array access branch, and it's taken quite often, it seems.
good, thanks for checking. as long as we run enough strings against it for that up-front cost to be a win. and yeah, for latin-1 it will still be tableized for each input and very fast.
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] donnerpeter commented on a change in pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
donnerpeter commented on a change in pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457#discussion_r588100894
##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/GeneratingSuggester.java
##########
@@ -89,7 +89,8 @@
}
String lower = dictionary.toLowerCase(root);
- int sc = ngram(3, word, lower, options) + commonPrefix(word, root);
+ int sc =
+ automaton.ngramScore(lower) - longerWorsePenalty(word, lower) + commonPrefix(word, root);
Review comment:
`ngram` has been split into `ngramScore` and penalties based on previously passed flags. The former is replaced with the automaton.
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] donnerpeter commented on pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
donnerpeter commented on pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457#issuecomment-791448721
The latter is ~10% faster, so there's some difference. `RunAutomaton.step`
has a constant-time array access branch, and it's taken quite often, it
seems.
On Fri, 5 Mar 2021 at 15:03, Robert Muir <no...@github.com> wrote:
> *@rmuir* commented on this pull request.
> ------------------------------
>
> In
> lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/TrigramAutomaton.java
> <https://github.com/apache/lucene-solr/pull/2457#discussion_r588317811>:
>
> > + for (int start = 0; start < s1.length(); start++) {
> + int limit = Math.min(s1.length(), start + N);
> + for (int end = start + 1; end <= limit; end++) {
> + substringCounts.merge(s1.substring(start, end), 1, Integer::sum);
> + }
> +
> + int state = initialState;
> + for (int i = start; i < limit; i++) {
> + int next = builder.createState();
> + builder.addTransition(state, next, s1.charAt(i));
> + state = next;
> + }
> + }
> +
> + automaton =
> + new CharacterRunAutomaton(
>
> Both Automaton.step and CharacterRunAutomaton.step are binary search
> (transition labels vs character classes, which probably isn't very
> different here)
>
> —
> You are receiving this because you authored the thread.
> Reply to this email directly, view it on GitHub
> <https://github.com/apache/lucene-solr/pull/2457#discussion_r588317811>,
> or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/AAA5ZGNURLRJ3Y5KTE5YSHDTCDQEZANCNFSM4YUX3ODA>
> .
>
----------------------------------------------------------------
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.
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
[GitHub] [lucene-solr] donnerpeter commented on a change in pull request #2457: LUCENE-9824: Hunspell suggestions: speed up ngram score calculation for each dictionary entry
Posted by GitBox <gi...@apache.org>.
donnerpeter commented on a change in pull request #2457:
URL: https://github.com/apache/lucene-solr/pull/2457#discussion_r588101236
##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/GeneratingSuggester.java
##########
@@ -152,7 +153,7 @@ private void filterSuitableEntries(String word, IntsRef forms, List<Root<String>
for (String guess : expandRoot(weighted.word, misspelled)) {
String lower = dictionary.toLowerCase(guess);
int sc =
- ngram(misspelled.length(), misspelled, lower, EnumSet.of(NGramOptions.ANY_MISMATCH))
+ anyMismatchNgram(misspelled.length(), misspelled, lower, false)
Review comment:
`ANY_MISMATCH` is now baked into the method's name, `false` stands for lack of `WEIGHTED` option
----------------------------------------------------------------
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.
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