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 e29862206ae1e8de6af6e5f82c1429ab917bfe51 Author: Kristian Rickert <[email protected]> AuthorDate: Wed Jul 15 13:58:23 2026 -0400 OPENNLP-1894: Frequency-driven segmentation over user-supplied lexicons A Viterbi search maximizing summed word log-probabilities segments Chinese and similar scripts from a plain word-count lexicon, with unlisted characters falling back to single-character words. The user supplies the lexicon and thereby accepts its license; nothing is bundled. (cherry picked from commit bff3f23d4858562171940d09ba2c2321f5005ab0) --- .../tools/tokenize/lattice/UnigramSegmenter.java | 258 +++++++++++++++++++++ .../tokenize/lattice/UnigramSegmenterTest.java | 108 +++++++++ 2 files changed, 366 insertions(+) diff --git a/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/UnigramSegmenter.java b/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/UnigramSegmenter.java new file mode 100644 index 000000000..3d1ca9884 --- /dev/null +++ b/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/UnigramSegmenter.java @@ -0,0 +1,258 @@ +/* + * 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 opennlp.tools.tokenize.lattice; + +import java.io.IOException; +import java.io.InputStream; +import java.nio.charset.Charset; +import java.nio.charset.StandardCharsets; +import java.nio.file.Files; +import java.nio.file.Path; +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +import opennlp.tools.tokenize.Tokenizer; +import opennlp.tools.util.Span; +import opennlp.tools.util.StringUtil; + +/** + * Frequency-driven segmentation for Chinese and similar scripts: a Viterbi search that + * maximizes the summed log-probability of the words in a user-supplied frequency + * lexicon, with unlisted characters falling back to single-character words. This is the + * unigram model behind common Chinese segmenters; it carries no connection costs, so it + * is lighter than the {@link LatticeTokenizer} and fits lexicons that list only words + * and counts. + * + * <p>The lexicon format is one entry per line: the word, its count, and optionally a + * tag, separated by whitespace. The user supplies the lexicon file and thereby accepts + * its license; nothing is bundled. Every reported span is in original text + * coordinates.</p> + * + * <p>Instances are immutable and safe to share between threads.</p> + * + * @since 3.0.0 + */ +public class UnigramSegmenter implements Tokenizer { + + /** The log-probability charged to a character the lexicon does not know. */ + private final double unknownLogProbability; + + private final WordTrie trie; + + /** A minimal trie over words with their log-probabilities. */ + private static final class WordTrie { + private final Map<Character, WordTrie> children = new HashMap<>(); + private double logProbability = Double.NaN; + } + + private UnigramSegmenter(WordTrie trie, double unknownLogProbability) { + this.trie = trie; + this.unknownLogProbability = unknownLogProbability; + } + + /** + * Loads a frequency lexicon encoded in UTF-8. + * + * @param lexicon The lexicon file. Must not be {@code null}. + * @return The segmenter. Never {@code null}. + * @throws IOException Thrown if reading fails or the lexicon is empty or malformed. + * @throws IllegalArgumentException Thrown if {@code lexicon} is {@code null}. + */ + public static UnigramSegmenter load(Path lexicon) throws IOException { + return load(lexicon, StandardCharsets.UTF_8); + } + + /** + * Loads a frequency lexicon. + * + * @param lexicon The lexicon file: one word, its count, and an optional tag per + * line. Must not be {@code null}. + * @param charset The lexicon encoding. Must not be {@code null}. + * @return The segmenter. Never {@code null}. + * @throws IOException Thrown if reading fails or the lexicon is empty or malformed. + * @throws IllegalArgumentException Thrown if a parameter is {@code null}. + */ + public static UnigramSegmenter load(Path lexicon, Charset charset) throws IOException { + if (lexicon == null || charset == null) { + throw new IllegalArgumentException("lexicon and charset must not be null"); + } + try (InputStream in = Files.newInputStream(lexicon)) { + return load(in, charset); + } + } + + /** + * Loads a frequency lexicon from a stream. + * + * @param lexiconStream The lexicon content. Must not be {@code null}. Not closed. + * @param charset The lexicon encoding. Must not be {@code null}. + * @return The segmenter. Never {@code null}. + * @throws IOException Thrown if reading fails or the lexicon is empty or malformed. + * @throws IllegalArgumentException Thrown if a parameter is {@code null}. + */ + public static UnigramSegmenter load(InputStream lexiconStream, Charset charset) + throws IOException { + if (lexiconStream == null || charset == null) { + throw new IllegalArgumentException("stream and charset must not be null"); + } + final Map<String, Long> counts = new HashMap<>(); + long total = 0; + final String content = new String(lexiconStream.readAllBytes(), charset); + int lineStart = 0; + int lineNumber = 0; + for (int i = 0; i <= content.length(); i++) { + if (i < content.length() && content.charAt(i) != '\n') { + continue; + } + lineNumber++; + final String line = content.substring(lineStart, i).trim(); + lineStart = i + 1; + if (line.isEmpty()) { + continue; + } + final int wordEnd = whitespaceIndex(line); + if (wordEnd < 0) { + throw new IOException("lexicon line " + lineNumber + " has no count"); + } + final String word = line.substring(0, wordEnd); + int countStart = wordEnd; + while (countStart < line.length() && StringUtil.isWhitespace(line.charAt(countStart))) { + countStart++; + } + int countEnd = countStart; + while (countEnd < line.length() && !StringUtil.isWhitespace(line.charAt(countEnd))) { + countEnd++; + } + final long count; + try { + count = Long.parseLong(line.substring(countStart, countEnd)); + } catch (NumberFormatException e) { + throw new IOException("malformed count at lexicon line " + lineNumber, e); + } + if (count <= 0) { + throw new IOException("count must be positive at lexicon line " + lineNumber); + } + counts.merge(word, count, Long::sum); + total += count; + } + if (counts.isEmpty()) { + throw new IOException("the lexicon lists no words"); + } + + final WordTrie root = new WordTrie(); + final double logTotal = Math.log(total); + for (final Map.Entry<String, Long> entry : counts.entrySet()) { + WordTrie node = root; + final String word = entry.getKey(); + for (int c = 0; c < word.length(); c++) { + node = node.children.computeIfAbsent(word.charAt(c), + key -> new WordTrie()); + } + node.logProbability = Math.log(entry.getValue()) - logTotal; + } + // rarer than any listed word: a fraction of a single count + final double unknown = Math.log(0.5) - logTotal; + return new UnigramSegmenter(root, unknown); + } + + @Override + public String[] tokenize(String s) { + final Span[] spans = tokenizePos(s); + final String[] tokens = new String[spans.length]; + for (int i = 0; i < tokens.length; i++) { + tokens[i] = s.substring(spans[i].getStart(), spans[i].getEnd()); + } + return tokens; + } + + @Override + public Span[] tokenizePos(String s) { + if (s == null) { + throw new IllegalArgumentException("text must not be null"); + } + final List<Span> spans = new ArrayList<>(); + int start = 0; + while (start < s.length()) { + if (StringUtil.isWhitespace(s.charAt(start))) { + start++; + continue; + } + int end = start; + while (end < s.length() && !StringUtil.isWhitespace(s.charAt(end))) { + end++; + } + decode(s, start, end, spans); + start = end; + } + return spans.toArray(new Span[0]); + } + + /** Viterbi over word log-probabilities within one whitespace-free stretch. */ + private void decode(String text, int from, int to, List<Span> spans) { + final int length = to - from; + final double[] best = new double[length + 1]; + final int[] previous = new int[length + 1]; + for (int i = 1; i <= length; i++) { + best[i] = Double.NEGATIVE_INFINITY; + } + for (int i = 0; i < length; i++) { + if (best[i] == Double.NEGATIVE_INFINITY) { + continue; + } + // the single-character fallback keeps every position reachable + final double fallback = best[i] + unknownLogProbability; + if (fallback > best[i + 1]) { + best[i + 1] = fallback; + previous[i + 1] = i; + } + WordTrie node = trie; + for (int j = from + i; j < to; j++) { + node = node.children.get(text.charAt(j)); + if (node == null) { + break; + } + if (!Double.isNaN(node.logProbability)) { + final int end = j - from + 1; + final double score = best[i] + node.logProbability; + if (score > best[end]) { + best[end] = score; + previous[end] = i; + } + } + } + } + final List<Span> reversed = new ArrayList<>(); + for (int end = length; end > 0; end = previous[end]) { + reversed.add(new Span(from + previous[end], from + end)); + } + for (int i = reversed.size() - 1; i >= 0; i--) { + spans.add(reversed.get(i)); + } + } + + private static int whitespaceIndex(String text) { + for (int i = 0; i < text.length(); i++) { + if (StringUtil.isWhitespace(text.charAt(i))) { + return i; + } + } + return -1; + } +} diff --git a/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/tokenize/lattice/UnigramSegmenterTest.java b/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/tokenize/lattice/UnigramSegmenterTest.java new file mode 100644 index 000000000..a6104c195 --- /dev/null +++ b/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/tokenize/lattice/UnigramSegmenterTest.java @@ -0,0 +1,108 @@ +/* + * 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 opennlp.tools.tokenize.lattice; + +import java.io.ByteArrayInputStream; +import java.io.IOException; +import java.nio.charset.StandardCharsets; + +import org.junit.jupiter.api.Assertions; +import org.junit.jupiter.api.BeforeAll; +import org.junit.jupiter.api.Test; + +import opennlp.tools.util.Span; + +/** + * Tests the frequency-driven segmenter against a project-authored miniature lexicon; + * no external lexicon data is involved. + */ +public class UnigramSegmenterTest { + + private static final String LEXICON = String.join("\n", + "我 5000 r", + "来到 2000 v", + "北京 3000 ns", + "清华大学 800 nt", + "清华 400 ns", + "华大 100 ns", + "大学 1500 n", + "的 9000 uj", + ""); + + private static UnigramSegmenter segmenter; + + @BeforeAll + static void loadLexicon() throws IOException { + segmenter = UnigramSegmenter.load( + new ByteArrayInputStream(LEXICON.getBytes(StandardCharsets.UTF_8)), + StandardCharsets.UTF_8); + } + + @Test + void testPrefersWholeWordsOverFragments() { + Assertions.assertArrayEquals( + new String[] {"我", "来到", "北京", "清华大学"}, + segmenter.tokenize("我来到北京清华大学")); + } + + @Test + void testSpansStayInOriginalCoordinates() { + Assertions.assertArrayEquals(new Span[] { + new Span(0, 1), new Span(1, 3), new Span(3, 5), new Span(5, 9)}, + segmenter.tokenizePos("我来到北京清华大学")); + } + + @Test + void testUnknownCharactersFallBackToSingles() { + Assertions.assertArrayEquals( + new String[] {"我", "爱", "北京"}, + segmenter.tokenize("我爱北京")); + } + + @Test + void testWhitespaceSeparates() { + Assertions.assertArrayEquals( + new String[] {"北京", "大学"}, + segmenter.tokenize("北京 大学")); + Assertions.assertEquals(0, segmenter.tokenizePos(" ").length); + } + + @Test + void testMalformedLexiconsFailLoud() { + Assertions.assertThrows(IOException.class, () -> UnigramSegmenter.load( + new ByteArrayInputStream("word\n".getBytes(StandardCharsets.UTF_8)), + StandardCharsets.UTF_8)); + Assertions.assertThrows(IOException.class, () -> UnigramSegmenter.load( + new ByteArrayInputStream("word abc\n".getBytes(StandardCharsets.UTF_8)), + StandardCharsets.UTF_8)); + Assertions.assertThrows(IOException.class, () -> UnigramSegmenter.load( + new ByteArrayInputStream("word 0\n".getBytes(StandardCharsets.UTF_8)), + StandardCharsets.UTF_8)); + Assertions.assertThrows(IOException.class, () -> UnigramSegmenter.load( + new ByteArrayInputStream("\n\n".getBytes(StandardCharsets.UTF_8)), + StandardCharsets.UTF_8)); + } + + @Test + void testInvalidArguments() { + Assertions.assertThrows(IllegalArgumentException.class, + () -> UnigramSegmenter.load((java.nio.file.Path) null)); + Assertions.assertThrows(IllegalArgumentException.class, + () -> segmenter.tokenizePos(null)); + } +}
