This is an automated email from the ASF dual-hosted git repository. krickert pushed a commit to branch OPENNLP-1894-lattice-cjk in repository https://gitbox.apache.org/repos/asf/opennlp.git
commit 1132c127d43c1b658a888c8e0eb7e65d8006f55d Author: Kristian Rickert <[email protected]> AuthorDate: Wed Jul 15 13:56:19 2026 -0400 OPENNLP-1894: Character trie for lattice prefix search Common-prefix lookup walks a trie built at load time instead of probing substrings per length, terminating on the first missing prefix and allocating nothing per position. (cherry picked from commit e10ce4b2b8d47821f4ffffcc1da109dcdb7219ba) --- .../tools/tokenize/lattice/LatticeTokenizer.java | 15 ++--- .../tools/tokenize/lattice/MecabDictionary.java | 68 ++++++++++++++++++++-- 2 files changed, 68 insertions(+), 15 deletions(-) diff --git a/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/LatticeTokenizer.java b/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/LatticeTokenizer.java index c022374a5..c811fd326 100644 --- a/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/LatticeTokenizer.java +++ b/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/LatticeTokenizer.java @@ -203,19 +203,14 @@ public class LatticeTokenizer implements Tokenizer { private List<Node> candidates(String text, int from, int to, int offset) { final int position = from + offset; final List<Node> candidates = new ArrayList<>(); - final int longest = Math.min(dictionary.maxSurfaceLength(), to - position); - boolean lexiconMatch = false; - for (int length = 1; length <= longest; length++) { - final List<WordEntry> entries = - dictionary.lookup(text.substring(position, position + length)); - if (entries == null) { - continue; - } - lexiconMatch = true; + final boolean[] matched = new boolean[1]; + dictionary.prefixMatches(text, position, to, (length, entries) -> { + matched[0] = true; for (final WordEntry entry : entries) { candidates.add(new Node(position, position + length, entry, false)); } - } + }); + final boolean lexiconMatch = matched[0]; final Category category = dictionary.categoryOf(text.charAt(position)); if (!lexiconMatch || category.invoke()) { diff --git a/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/MecabDictionary.java b/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/MecabDictionary.java index 5e1c60f1a..2e20b8c2d 100644 --- a/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/MecabDictionary.java +++ b/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/MecabDictionary.java @@ -57,7 +57,25 @@ public final class MecabDictionary { record Category(String name, boolean invoke, boolean group, int length) { } - private final Map<String, List<WordEntry>> lexicon; + /** One node of the lexicon trie, keyed by the next surface character. */ + private static final class TrieNode { + private final Map<Character, TrieNode> children = new HashMap<>(); + private List<WordEntry> entries; + } + + /** Receives one common-prefix match during {@link #prefixMatches}. */ + interface PrefixMatchConsumer { + + /** + * Accepts one match. + * + * @param length The matched surface length in characters. + * @param entries The lexicon entries for that surface. + */ + void accept(int length, List<WordEntry> entries); + } + + private final TrieNode lexicon; private final int maxSurfaceLength; private final short[] connectionCosts; private final int rightSize; @@ -65,7 +83,7 @@ public final class MecabDictionary { private final String[] categoryOfChar; private final Map<String, List<WordEntry>> unknownEntries; - private MecabDictionary(Map<String, List<WordEntry>> lexicon, int maxSurfaceLength, + private MecabDictionary(TrieNode lexicon, int maxSurfaceLength, short[] connectionCosts, int rightSize, Map<String, Category> categories, String[] categoryOfChar, Map<String, List<WordEntry>> unknownEntries) { this.lexicon = lexicon; @@ -150,8 +168,22 @@ public final class MecabDictionary { final Map<String, List<WordEntry>> unknown = new HashMap<>(); readLexicon(directory.resolve("unk.def"), charset, unknown); - return new MecabDictionary(lexicon, maxSurface, costs, rightSize, categories, - categoryOfChar, unknown); + return new MecabDictionary(buildTrie(lexicon), maxSurface, costs, rightSize, + categories, categoryOfChar, unknown); + } + + /** Folds the surface-keyed lexicon into a character trie for prefix search. */ + private static TrieNode buildTrie(Map<String, List<WordEntry>> lexicon) { + final TrieNode root = new TrieNode(); + for (final Map.Entry<String, List<WordEntry>> entry : lexicon.entrySet()) { + TrieNode node = root; + final String surface = entry.getKey(); + for (int i = 0; i < surface.length(); i++) { + node = node.children.computeIfAbsent(surface.charAt(i), key -> new TrieNode()); + } + node.entries = List.copyOf(entry.getValue()); + } + return root; } /** Reads one lexicon-format CSV file; returns the longest surface seen. */ @@ -232,7 +264,33 @@ public final class MecabDictionary { * @return The entries, or {@code null} when the surface is not listed. */ List<WordEntry> lookup(String surface) { - return lexicon.get(surface); + TrieNode node = lexicon; + for (int i = 0; i < surface.length() && node != null; i++) { + node = node.children.get(surface.charAt(i)); + } + return node == null ? null : node.entries; + } + + /** + * Reports every lexicon surface starting at a text position, walking the trie once + * with no substring allocation. + * + * @param text The text being segmented. + * @param from The position surfaces must start at. + * @param to The exclusive end of the searchable stretch. + * @param consumer Receives each match. + */ + void prefixMatches(String text, int from, int to, PrefixMatchConsumer consumer) { + TrieNode node = lexicon; + for (int i = from; i < to; i++) { + node = node.children.get(text.charAt(i)); + if (node == null) { + return; + } + if (node.entries != null) { + consumer.accept(i - from + 1, node.entries); + } + } } /** @return The longest surface form in the lexicon, bounding prefix enumeration. */
