dweiss commented on code in PR #975:
URL: https://github.com/apache/lucene/pull/975#discussion_r906351080
##########
lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/Hunspell.java:
##########
@@ -340,9 +339,14 @@ public List<AffixedWord> analyzeSimpleWord(String word) {
return result;
}
- private AffixedWord.Affix toPresentableAffix(int affixId) {
- char flag = dictionary.affixData(affixId, AFFIX_FLAG);
- return new
AffixedWord.Affix(dictionary.flagParsingStrategy.printFlag(flag));
+ /**
+ * Generate all word forms for all dictionary entries with the given root
word. The result order
+ * is stable but not specified. This is equivalent to "unmunch" from the
"hunspell-tools" package.
+ *
+ * @see WordFormGenerator for finer-grained APIs
+ */
+ public List<AffixedWord> expandRoot(String root) {
Review Comment:
Maybe just rename it getAllWordForms(String root)? Seems like it'd be more
intuitive and consistent with the docs.
##########
lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/WordFormGenerator.java:
##########
@@ -0,0 +1,245 @@
+/*
+ * 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 static org.apache.lucene.analysis.hunspell.Dictionary.AFFIX_APPEND;
+import static org.apache.lucene.analysis.hunspell.Dictionary.AFFIX_FLAG;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import org.apache.lucene.analysis.hunspell.AffixedWord.Affix;
+import org.apache.lucene.util.IntsRef;
+import org.apache.lucene.util.fst.FST;
+import org.apache.lucene.util.fst.IntsRefFSTEnum;
+
+/** A utility class used for generating possible word forms by adding affixes
to stems */
+public class WordFormGenerator {
+ private final Dictionary dictionary;
+ private final Map<Character, List<AffixEntry>> affixes = new HashMap<>();
+ private final Stemmer stemmer;
+
+ public WordFormGenerator(Dictionary dictionary) {
+ this.dictionary = dictionary;
+ fillAffixMap(dictionary.prefixes, AffixKind.PREFIX);
+ fillAffixMap(dictionary.suffixes, AffixKind.SUFFIX);
+ stemmer = new Stemmer(dictionary);
+ }
+
+ private void fillAffixMap(FST<IntsRef> fst, AffixKind kind) {
+ if (fst == null) return;
+
+ IntsRefFSTEnum<IntsRef> fstEnum = new IntsRefFSTEnum<>(fst);
+ try {
+ while (true) {
+ IntsRefFSTEnum.InputOutput<IntsRef> io = fstEnum.next();
+ if (io == null) break;
+
+ IntsRef affixIds = io.output;
+ for (int j = 0; j < affixIds.length; j++) {
+ int id = affixIds.ints[affixIds.offset + j];
+ char flag = dictionary.affixData(id, AFFIX_FLAG);
+ var entry =
+ new AffixEntry(id, flag, kind, toString(kind, io.input),
strip(id), condition(id));
+ affixes.computeIfAbsent(flag, __ -> new ArrayList<>()).add(entry);
+ }
+ }
+ } catch (IOException e) {
+ throw new RuntimeException(e);
Review Comment:
UncheckedIOException(e), maybe?
##########
lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/WordFormGenerator.java:
##########
@@ -280,4 +300,188 @@ private boolean
isCompatibleWithPreviousAffixes(AffixedWord stem, Dictionary dic
return true;
}
}
+
+ private class WordCompressor {
+ private final Set<String> forbidden;
+ private final Runnable checkCanceled;
+ private final Set<String> wordSet;
+ private final Set<String> existingStems;
+ private final Map<String, Set<FlagSet>> stemToPossibleFlags = new
HashMap<>();
+ private final Map<String, Integer> stemCounts = new LinkedHashMap<>();
+
+ WordCompressor(List<String> words, Set<String> forbidden, Runnable
checkCanceled) {
+ this.forbidden = forbidden;
+ this.checkCanceled = checkCanceled;
+ wordSet = new HashSet<>(words);
+
+ Stemmer.StemCandidateProcessor processor =
+ new Stemmer.StemCandidateProcessor(WordContext.SIMPLE_WORD) {
+ @Override
+ boolean processStemCandidate(
+ char[] word,
+ int offset,
+ int length,
+ int lastAffix,
+ int outerPrefix,
+ int innerPrefix,
+ int outerSuffix,
+ int innerSuffix) {
+ String candidate = new String(word, offset, length);
+ stemCounts.merge(candidate, 1, Integer::sum);
+ Set<Character> flags = new LinkedHashSet<>();
+ if (outerPrefix >= 0)
flags.add(dictionary.affixData(outerPrefix, AFFIX_FLAG));
+ if (innerPrefix >= 0)
flags.add(dictionary.affixData(innerPrefix, AFFIX_FLAG));
+ if (outerSuffix >= 0)
flags.add(dictionary.affixData(outerSuffix, AFFIX_FLAG));
+ if (innerSuffix >= 0)
flags.add(dictionary.affixData(innerSuffix, AFFIX_FLAG));
+ stemToPossibleFlags
+ .computeIfAbsent(candidate, __ -> new LinkedHashSet<>())
+ .add(new FlagSet(flags, dictionary));
+ return true;
+ }
+ };
+
+ for (String word : words) {
+ checkCanceled.run();
+ stemCounts.merge(word, 1, Integer::sum);
+ stemToPossibleFlags.computeIfAbsent(word, __ -> new LinkedHashSet<>());
Review Comment:
LinkedHashSet::new didn't work?
##########
lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/WordFormGenerator.java:
##########
@@ -0,0 +1,245 @@
+/*
+ * 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 static org.apache.lucene.analysis.hunspell.Dictionary.AFFIX_APPEND;
+import static org.apache.lucene.analysis.hunspell.Dictionary.AFFIX_FLAG;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import org.apache.lucene.analysis.hunspell.AffixedWord.Affix;
+import org.apache.lucene.util.IntsRef;
+import org.apache.lucene.util.fst.FST;
+import org.apache.lucene.util.fst.IntsRefFSTEnum;
+
+/** A utility class used for generating possible word forms by adding affixes
to stems */
+public class WordFormGenerator {
+ private final Dictionary dictionary;
+ private final Map<Character, List<AffixEntry>> affixes = new HashMap<>();
+ private final Stemmer stemmer;
+
+ public WordFormGenerator(Dictionary dictionary) {
+ this.dictionary = dictionary;
+ fillAffixMap(dictionary.prefixes, AffixKind.PREFIX);
+ fillAffixMap(dictionary.suffixes, AffixKind.SUFFIX);
+ stemmer = new Stemmer(dictionary);
+ }
+
+ private void fillAffixMap(FST<IntsRef> fst, AffixKind kind) {
+ if (fst == null) return;
+
+ IntsRefFSTEnum<IntsRef> fstEnum = new IntsRefFSTEnum<>(fst);
+ try {
+ while (true) {
+ IntsRefFSTEnum.InputOutput<IntsRef> io = fstEnum.next();
+ if (io == null) break;
+
+ IntsRef affixIds = io.output;
+ for (int j = 0; j < affixIds.length; j++) {
+ int id = affixIds.ints[affixIds.offset + j];
+ char flag = dictionary.affixData(id, AFFIX_FLAG);
+ var entry =
+ new AffixEntry(id, flag, kind, toString(kind, io.input),
strip(id), condition(id));
+ affixes.computeIfAbsent(flag, __ -> new ArrayList<>()).add(entry);
Review Comment:
ArrayList::new didn't work?
##########
lucene/analysis/common/src/test/org/apache/lucene/analysis/hunspell/TestHunspell.java:
##########
@@ -134,4 +138,32 @@ private Hunspell loadNoTimeout(String name) throws
Exception {
Dictionary dictionary = loadDictionary(false, name + ".aff", name +
".dic");
return new Hunspell(dictionary, TimeoutPolicy.NO_TIMEOUT, () -> {});
}
+
+ @Test
+ public void testExpandRootApi() throws Exception {
+ Hunspell h = loadNoTimeout("base");
+ String[] createFormsBase = {
+ "create", "created", "creates", "creating", "creation", "creations"
+ };
+ List<String> expected =
+ Stream.concat(
+ Stream.of(createFormsBase).flatMap(s -> Stream.of(s, "pro" +
s, "re" + s)),
+ Stream.of("creative"))
+ .sorted()
+ .toList();
+
+ Map<String, AffixedWord> expanded =
+ TestSpellChecking.checkExpansionGeneratesCorrectWords(h, "create",
"base").stream()
+ .collect(Collectors.toMap(w -> w.getWord(), w -> w));
+ assertEquals(expected, expanded.keySet().stream().sorted().toList());
Review Comment:
You could make expected a set, then no sorting would be needed (for both), I
think.
##########
lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/WordFormGenerator.java:
##########
@@ -245,6 +240,31 @@ private LinkedHashSet<Character> appendFlags(AffixEntry
affix) {
return appendId <= 0 ? new LinkedHashSet<>() :
toSet(dictionary.flagLookup.getFlags(appendId));
}
+ /**
+ * Given a list of words, try to produce a smaller set of dictionary entries
(with some flags)
Review Comment:
This is pretty neat.
##########
lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/WordFormGenerator.java:
##########
@@ -0,0 +1,245 @@
+/*
+ * 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 static org.apache.lucene.analysis.hunspell.Dictionary.AFFIX_APPEND;
+import static org.apache.lucene.analysis.hunspell.Dictionary.AFFIX_FLAG;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import org.apache.lucene.analysis.hunspell.AffixedWord.Affix;
+import org.apache.lucene.util.IntsRef;
+import org.apache.lucene.util.fst.FST;
+import org.apache.lucene.util.fst.IntsRefFSTEnum;
+
+/** A utility class used for generating possible word forms by adding affixes
to stems */
Review Comment:
I'd give a link to the method that actually makes use of this (expandRoot)
and make all of this package-private.
##########
lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/WordFormGenerator.java:
##########
@@ -280,4 +300,188 @@ private boolean
isCompatibleWithPreviousAffixes(AffixedWord stem, Dictionary dic
return true;
}
}
+
+ private class WordCompressor {
+ private final Set<String> forbidden;
+ private final Runnable checkCanceled;
+ private final Set<String> wordSet;
+ private final Set<String> existingStems;
+ private final Map<String, Set<FlagSet>> stemToPossibleFlags = new
HashMap<>();
+ private final Map<String, Integer> stemCounts = new LinkedHashMap<>();
+
+ WordCompressor(List<String> words, Set<String> forbidden, Runnable
checkCanceled) {
+ this.forbidden = forbidden;
+ this.checkCanceled = checkCanceled;
+ wordSet = new HashSet<>(words);
+
+ Stemmer.StemCandidateProcessor processor =
+ new Stemmer.StemCandidateProcessor(WordContext.SIMPLE_WORD) {
+ @Override
+ boolean processStemCandidate(
+ char[] word,
+ int offset,
+ int length,
+ int lastAffix,
+ int outerPrefix,
+ int innerPrefix,
+ int outerSuffix,
+ int innerSuffix) {
+ String candidate = new String(word, offset, length);
+ stemCounts.merge(candidate, 1, Integer::sum);
+ Set<Character> flags = new LinkedHashSet<>();
+ if (outerPrefix >= 0)
flags.add(dictionary.affixData(outerPrefix, AFFIX_FLAG));
+ if (innerPrefix >= 0)
flags.add(dictionary.affixData(innerPrefix, AFFIX_FLAG));
+ if (outerSuffix >= 0)
flags.add(dictionary.affixData(outerSuffix, AFFIX_FLAG));
+ if (innerSuffix >= 0)
flags.add(dictionary.affixData(innerSuffix, AFFIX_FLAG));
+ stemToPossibleFlags
+ .computeIfAbsent(candidate, __ -> new LinkedHashSet<>())
+ .add(new FlagSet(flags, dictionary));
+ return true;
+ }
+ };
+
+ for (String word : words) {
+ checkCanceled.run();
+ stemCounts.merge(word, 1, Integer::sum);
+ stemToPossibleFlags.computeIfAbsent(word, __ -> new LinkedHashSet<>());
+ stemmer.removeAffixes(word.toCharArray(), 0, word.length(), true, -1,
-1, -1, processor);
+ }
+
+ existingStems =
+ stemCounts.keySet().stream()
+ .filter(stem -> dictionary.lookupEntries(stem) != null)
+ .collect(Collectors.toSet());
+ }
+
+ EntrySuggestion compress() {
+ Comparator<String> stemSorter =
+ Comparator.comparing((String s) -> existingStems.contains(s))
+ .thenComparing(stemCounts::get)
+ .reversed();
+ List<String> sortedStems =
stemCounts.keySet().stream().sorted(stemSorter).toList();
+ PriorityQueue<State> queue = new PriorityQueue<>();
+ queue.offer(new State(Map.of(), wordSet.size(), 0, 0));
+ State result = null;
+ while (!queue.isEmpty()) {
+ State state = queue.poll();
+ if (state.underGenerated == 0) {
+ if (result == null || state.compareTo(result) < 0) result = state;
+ if (state.forbidden == 0) break;
+ continue;
+ }
+
+ for (String stem : sortedStems) {
+ if (!state.stemToFlags.containsKey(stem)) {
+ queue.offer(addStem(state, stem));
+ }
+ }
+
+ for (Map.Entry<String, Set<FlagSet>> entry :
state.stemToFlags.entrySet()) {
+ for (FlagSet flags : stemToPossibleFlags.get(entry.getKey())) {
+ if (!entry.getValue().contains(flags)) {
+ queue.offer(addFlags(state, entry.getKey(), flags));
+ }
+ }
+ }
+ }
+ return result == null ? null : toSuggestion(result);
+ }
+
+ EntrySuggestion toSuggestion(State state) {
+ List<DictEntry> toEdit = new ArrayList<>();
+ List<DictEntry> toAdd = new ArrayList<>();
+ for (Map.Entry<String, Set<FlagSet>> entry :
state.stemToFlags.entrySet()) {
+ addEntry(toEdit, toAdd, entry.getKey(),
FlagSet.flatten(entry.getValue()));
+ }
+
+ List<String> extraGenerated = new ArrayList<>();
+ for (String extra :
allGenerated(state.stemToFlags).distinct().sorted().toList()) {
+ if (wordSet.contains(extra)) continue;
+
+ if (forbidden.contains(extra) && dictionary.forbiddenword !=
FLAG_UNSET) {
+ addEntry(toEdit, toAdd, extra, Set.of(dictionary.forbiddenword));
+ } else {
+ extraGenerated.add(extra);
+ }
+ }
+
+ return new EntrySuggestion(toEdit, toAdd, extraGenerated);
+ }
+
+ private void addEntry(
+ List<DictEntry> toEdit, List<DictEntry> toAdd, String stem,
Set<Character> flags) {
+ String flagString = toFlagString(flags);
+ (existingStems.contains(stem) ? toEdit :
toAdd).add(DictEntry.create(stem, flagString));
+ }
+
+ private State addStem(State state, String stem) {
+ LinkedHashMap<String, Set<FlagSet>> stemToFlags = new
LinkedHashMap<>(state.stemToFlags);
+ stemToFlags.put(stem, Set.of());
+ return newState(stemToFlags);
+ }
+
+ private State addFlags(State state, String stem, FlagSet flags) {
+ LinkedHashMap<String, Set<FlagSet>> stemToFlags = new
LinkedHashMap<>(state.stemToFlags);
+ Set<FlagSet> flagSets = new LinkedHashSet<>(stemToFlags.get(stem));
+ flagSets.add(flags);
+ stemToFlags.put(stem, flagSets);
+ return newState(stemToFlags);
+ }
+
+ private State newState(Map<String, Set<FlagSet>> stemToFlags) {
+ Set<String> allGenerated =
allGenerated(stemToFlags).collect(Collectors.toSet());
+ return new State(
+ stemToFlags,
+ (int) wordSet.stream().filter(s ->
!allGenerated.contains(s)).count(),
+ (int) allGenerated.stream().filter(s ->
!wordSet.contains(s)).count(),
+ (int) allGenerated.stream().filter(s ->
forbidden.contains(s)).count());
+ }
+
+ private final Map<StemWithFlags, List<String>> expansionCache = new
HashMap<>();
+
+ private record StemWithFlags(String stem, Set<FlagSet> flags) {}
+
+ private Stream<String> allGenerated(Map<String, Set<FlagSet>> stemToFlags)
{
+ Function<StemWithFlags, List<String>> expandToWords =
+ e -> expand(e.stem, FlagSet.flatten(e.flags)).stream().map(w ->
w.getWord()).toList();
+ return stemToFlags.entrySet().stream()
+ .map(e -> new StemWithFlags(e.getKey(), e.getValue()))
+ .flatMap(swc -> expansionCache.computeIfAbsent(swc,
expandToWords).stream());
+ }
+
+ private List<AffixedWord> expand(String stem, Set<Character> flagSet) {
+ return expandRoot(stem, toFlagString(flagSet), checkCanceled);
+ }
+
+ private String toFlagString(Set<Character> flagSet) {
+ return
dictionary.flagParsingStrategy.printFlags(Dictionary.toSortedCharArray(flagSet));
+ }
+ }
+
+ private record FlagSet(Set<Character> flags, Dictionary dictionary) {
+ static Set<Character> flatten(Set<FlagSet> flagSets) {
+ return flagSets.stream().flatMap(f ->
f.flags.stream()).collect(Collectors.toSet());
+ }
+
+ @Override
+ public String toString() {
+ return
dictionary.flagParsingStrategy.printFlags(Dictionary.toSortedCharArray(flags));
+ }
+ }
+
+ private record State(
Review Comment:
Uh, fancy. I'm a bit hesitant about implementing comparable that's not
entirely consistent with equals here... Maybe it'd be better to have a final
static (explicit) comparator that would be used instead? Then the name/ docs on
that comparator can explain what the sort order is.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]