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 3ce137626116f1b67eeb83e9795adbf39041abb8 Author: Kristian Rickert <[email protected]> AuthorDate: Wed Jul 15 13:30:41 2026 -0400 OPENNLP-1894: Lattice segmentation over user-supplied mecab-format dictionaries A Viterbi decoder over word and connection costs segments languages written without spaces; the same engine serves Japanese and Korean because the language lives entirely in the dictionary. Unknown text is handled through the dictionary's character categories, and every span stays in original text coordinates. An installer fetches and unpacks a user-chosen dictionary archive at install time: nothing is bundled, no location is built in, and entry names are flattened so no archive path escapes the target directory. (cherry picked from commit a699c8aeaffd107a21e4ba8ed281582366d92bb8) --- .../tools/tokenize/lattice/LatticeTokenizer.java | 266 ++++++++++++++++ .../tools/tokenize/lattice/MecabDictionary.java | 346 +++++++++++++++++++++ .../tokenize/lattice/MecabDictionaryInstaller.java | 226 ++++++++++++++ .../opennlp/tools/tokenize/lattice/Morpheme.java | 64 ++++ .../tokenize/lattice/LatticeTokenizerTest.java | 153 +++++++++ .../lattice/MecabDictionaryInstallerTest.java | 133 ++++++++ 6 files changed, 1188 insertions(+) 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 new file mode 100644 index 000000000..c022374a5 --- /dev/null +++ b/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/LatticeTokenizer.java @@ -0,0 +1,266 @@ +/* + * 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.util.ArrayList; +import java.util.List; + +import opennlp.tools.tokenize.Tokenizer; +import opennlp.tools.tokenize.lattice.MecabDictionary.Category; +import opennlp.tools.tokenize.lattice.MecabDictionary.WordEntry; +import opennlp.tools.util.Span; +import opennlp.tools.util.StringUtil; + +/** + * Dictionary-driven segmentation for languages written without spaces: a Viterbi + * search over the word lattice of a {@link MecabDictionary}, minimizing the sum of + * word costs and connection costs. This is the segmentation approach behind Japanese + * and Korean morphological analysis; the same decoder serves both, since the language + * lives entirely in the user-supplied dictionary. + * + * <p>Unknown text is handled through the dictionary's character categories: where the + * lexicon has no entry, or a category always invokes them, unknown-word candidates are + * generated per category template, grouping runs of same-category characters when the + * category says so. Whitespace never joins a morpheme and is never reported as one. + * Every reported span is in original text coordinates.</p> + * + * <p>{@link #analyze(String)} returns full morphemes with their dictionary features; + * the {@link Tokenizer} view reports just the surfaces and spans.</p> + * + * <p>The tokenizer reads only immutable dictionary state and is safe to share between + * threads.</p> + * + * @since 3.0.0 + */ +public class LatticeTokenizer implements Tokenizer { + + /** The context id of the beginning and end of text. */ + private static final int BOUNDARY_CONTEXT = 0; + + private final MecabDictionary dictionary; + + /** + * Initializes the tokenizer. + * + * @param dictionary The dictionary to segment with. Must not be {@code null}. + * @throws IllegalArgumentException Thrown if {@code dictionary} is {@code null}. + */ + public LatticeTokenizer(MecabDictionary dictionary) { + if (dictionary == null) { + throw new IllegalArgumentException("dictionary must not be null"); + } + this.dictionary = dictionary; + } + + /** One lattice node: a candidate morpheme with its best path cost so far. */ + private static final class Node { + private final int start; + private final int end; + private final WordEntry entry; + private final boolean unknown; + private long pathCost = Long.MAX_VALUE; + private Node previous; + + private Node(int start, int end, WordEntry entry, boolean unknown) { + this.start = start; + this.end = end; + this.entry = entry; + this.unknown = unknown; + } + } + + /** + * Segments a text into morphemes with their dictionary features. + * + * @param text The text to segment. Must not be {@code null}. + * @return The morphemes in text order, spans in original coordinates, whitespace + * omitted. Never {@code null}; empty for empty or all-whitespace input. + * @throws IllegalArgumentException Thrown if {@code text} is {@code null}. + */ + public List<Morpheme> analyze(String text) { + if (text == null) { + throw new IllegalArgumentException("text must not be null"); + } + final List<Morpheme> morphemes = new ArrayList<>(); + int start = 0; + while (start < text.length()) { + if (StringUtil.isWhitespace(text.charAt(start))) { + start++; + continue; + } + int end = start; + while (end < text.length() && !StringUtil.isWhitespace(text.charAt(end))) { + end++; + } + decode(text, start, end, morphemes); + start = end; + } + return morphemes; + } + + @Override + public String[] tokenize(String s) { + final List<Morpheme> morphemes = analyze(s); + final String[] tokens = new String[morphemes.size()]; + for (int i = 0; i < tokens.length; i++) { + tokens[i] = morphemes.get(i).surface(); + } + return tokens; + } + + @Override + public Span[] tokenizePos(String s) { + final List<Morpheme> morphemes = analyze(s); + final Span[] spans = new Span[morphemes.size()]; + for (int i = 0; i < spans.length; i++) { + spans[i] = morphemes.get(i).span(); + } + return spans; + } + + /** Runs the Viterbi search over one whitespace-free stretch of text. */ + private void decode(String text, int from, int to, List<Morpheme> morphemes) { + final int length = to - from; + final List<List<Node>> endingAt = new ArrayList<>(length + 1); + for (int i = 0; i <= length; i++) { + endingAt.add(new ArrayList<>()); + } + final boolean[] reachable = new boolean[length + 1]; + reachable[0] = true; + + for (int i = 0; i < length; i++) { + if (!reachable[i]) { + continue; + } + final List<Node> candidates = candidates(text, from, to, i); + for (final Node candidate : candidates) { + relax(candidate, i == 0 ? null : endingAt.get(i)); + if (candidate.pathCost < Long.MAX_VALUE) { + endingAt.get(candidate.end - from).add(candidate); + reachable[candidate.end - from] = true; + } + } + } + + Node best = null; + for (final Node node : endingAt.get(length)) { + final long total = node.pathCost + + dictionary.connectionCost(node.entry.rightId(), BOUNDARY_CONTEXT); + if (best == null || total < best.pathCost + + dictionary.connectionCost(best.entry.rightId(), BOUNDARY_CONTEXT)) { + best = node; + } + } + if (best == null) { + throw new IllegalStateException( + "no segmentation path for \"" + text.subSequence(from, to) + "\""); + } + + final List<Morpheme> reversed = new ArrayList<>(); + for (Node node = best; node != null; node = node.previous) { + reversed.add(new Morpheme(new Span(node.start, node.end), + text.substring(node.start, node.end), node.entry.features(), node.unknown)); + } + for (int i = reversed.size() - 1; i >= 0; i--) { + morphemes.add(reversed.get(i)); + } + } + + /** Connects a candidate to the cheapest predecessor ending where it starts. */ + private void relax(Node candidate, List<Node> predecessors) { + if (predecessors == null) { + candidate.pathCost = candidate.entry.cost() + + dictionary.connectionCost(BOUNDARY_CONTEXT, candidate.entry.leftId()); + return; + } + for (final Node predecessor : predecessors) { + final long total = predecessor.pathCost + + dictionary.connectionCost(predecessor.entry.rightId(), candidate.entry.leftId()) + + candidate.entry.cost(); + if (total < candidate.pathCost) { + candidate.pathCost = total; + candidate.previous = predecessor; + } + } + } + + /** Gathers lexicon matches and unknown-word candidates starting at one position. */ + 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; + for (final WordEntry entry : entries) { + candidates.add(new Node(position, position + length, entry, false)); + } + } + + final Category category = dictionary.categoryOf(text.charAt(position)); + if (!lexiconMatch || category.invoke()) { + int run = position + 1; + while (run < to + && dictionary.categoryOf(text.charAt(run)).name().equals(category.name())) { + run++; + } + final List<WordEntry> templates = dictionary.unknownEntries(category.name()); + if (templates != null) { + addUnknown(candidates, position, run, to, category, templates); + } + } + if (candidates.isEmpty()) { + // no entry and no template: a single-character fallback keeps the lattice alive + final List<WordEntry> fallback = dictionary.unknownEntries("DEFAULT"); + if (fallback != null) { + for (final WordEntry entry : fallback) { + candidates.add(new Node(position, position + 1, entry, true)); + } + } + } + if (candidates.isEmpty()) { + throw new IllegalStateException("dictionary provides no candidate at position " + + position + "; unk.def lacks a DEFAULT template"); + } + return candidates; + } + + /** Emits unknown-word candidates per the category's grouping and length settings. */ + private static void addUnknown(List<Node> candidates, int position, int runEnd, + int to, Category category, List<WordEntry> templates) { + if (category.group()) { + for (final WordEntry entry : templates) { + candidates.add(new Node(position, runEnd, entry, true)); + } + } + final int lengths = category.length(); + for (int length = 1; length <= lengths && position + length <= to; length++) { + if (category.group() && position + length == runEnd) { + continue; // already emitted as the grouped run + } + for (final WordEntry entry : templates) { + candidates.add(new Node(position, position + length, entry, true)); + } + } + } +} 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 new file mode 100644 index 000000000..5e1c60f1a --- /dev/null +++ b/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/MecabDictionary.java @@ -0,0 +1,346 @@ +/* + * 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.nio.charset.Charset; +import java.nio.charset.StandardCharsets; +import java.nio.file.DirectoryStream; +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.util.StringUtil; + +/** + * An immutable, in-memory dictionary in the mecab directory format: lexicon entries + * from the {@code *.csv} files, connection costs from {@code matrix.def}, character + * categories from {@code char.def}, and unknown-word templates from {@code unk.def}, + * loaded from a user-supplied dictionary directory. The reader is a clean-room + * implementation of the documented format; no dictionary data is bundled or downloaded + * by this class, so the dictionaries' own licenses never attach to this library. + * + * <p>The same format serves multiple languages: the Japanese IPADIC and UniDic + * distributions and the Korean mecab-ko-dic all load through this one reader, with the + * feature columns passed through untouched because their schemas differ.</p> + * + * <p>Instances are immutable and safe to share between threads.</p> + * + * @see LatticeTokenizer + * @since 3.0.0 + */ +public final class MecabDictionary { + + /** One lexicon or unknown-word entry. */ + record WordEntry(int leftId, int rightId, int cost, List<String> features) { + } + + /** One character category's unknown-word behavior from {@code char.def}. */ + record Category(String name, boolean invoke, boolean group, int length) { + } + + private final Map<String, List<WordEntry>> lexicon; + private final int maxSurfaceLength; + private final short[] connectionCosts; + private final int rightSize; + private final Map<String, Category> categories; + private final String[] categoryOfChar; + private final Map<String, List<WordEntry>> unknownEntries; + + private MecabDictionary(Map<String, List<WordEntry>> lexicon, int maxSurfaceLength, + short[] connectionCosts, int rightSize, Map<String, Category> categories, + String[] categoryOfChar, Map<String, List<WordEntry>> unknownEntries) { + this.lexicon = lexicon; + this.maxSurfaceLength = maxSurfaceLength; + this.connectionCosts = connectionCosts; + this.rightSize = rightSize; + this.categories = categories; + this.categoryOfChar = categoryOfChar; + this.unknownEntries = unknownEntries; + } + + /** + * Loads a dictionary directory encoded in UTF-8. + * + * @param directory The unpacked dictionary directory. Must not be {@code null}. + * @return The loaded dictionary. Never {@code null}. + * @throws IOException Thrown if reading fails or a file is malformed. + * @throws IllegalArgumentException Thrown if {@code directory} is {@code null}. + */ + public static MecabDictionary load(Path directory) throws IOException { + return load(directory, StandardCharsets.UTF_8); + } + + /** + * Loads a dictionary directory. + * + * @param directory The unpacked dictionary directory holding the {@code *.csv} + * lexicon files, {@code matrix.def}, {@code char.def}, and + * {@code unk.def}. Must not be {@code null}. + * @param charset The encoding the distribution uses, for example UTF-8 or EUC-JP. + * Must not be {@code null}. + * @return The loaded dictionary. Never {@code null}. + * @throws IOException Thrown if reading fails, a required file is missing, or a file + * is malformed. + * @throws IllegalArgumentException Thrown if a parameter is {@code null}. + */ + public static MecabDictionary load(Path directory, Charset charset) throws IOException { + if (directory == null || charset == null) { + throw new IllegalArgumentException("directory and charset must not be null"); + } + final Map<String, List<WordEntry>> lexicon = new HashMap<>(); + int maxSurface = 0; + try (DirectoryStream<Path> csvFiles = Files.newDirectoryStream(directory, "*.csv")) { + for (final Path csv : csvFiles) { + maxSurface = Math.max(maxSurface, readLexicon(csv, charset, lexicon)); + } + } + if (lexicon.isEmpty()) { + throw new IOException("no lexicon entries found under " + directory); + } + + final List<String> matrixLines = readLines(directory.resolve("matrix.def"), charset); + if (matrixLines.isEmpty()) { + throw new IOException("empty matrix.def under " + directory); + } + final String[] header = splitWhitespace(matrixLines.get(0)); + if (header.length != 2) { + throw new IOException("malformed matrix.def header: " + matrixLines.get(0)); + } + final int leftSize = parseInt(header[0], "matrix.def", 1); + final int rightSize = parseInt(header[1], "matrix.def", 1); + final short[] costs = new short[leftSize * rightSize]; + for (int i = 1; i < matrixLines.size(); i++) { + final String line = matrixLines.get(i).trim(); + if (line.isEmpty()) { + continue; + } + final String[] fields = splitWhitespace(line); + if (fields.length != 3) { + throw new IOException("malformed matrix.def line " + (i + 1)); + } + final int right = parseInt(fields[0], "matrix.def", i + 1); + final int left = parseInt(fields[1], "matrix.def", i + 1); + costs[right * rightSize + left] = (short) parseInt(fields[2], "matrix.def", i + 1); + } + + final Map<String, Category> categories = new HashMap<>(); + final String[] categoryOfChar = new String[Character.MAX_VALUE + 1]; + readCharacterDefinition(directory.resolve("char.def"), charset, categories, + categoryOfChar); + + 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); + } + + /** Reads one lexicon-format CSV file; returns the longest surface seen. */ + private static int readLexicon(Path file, Charset charset, + Map<String, List<WordEntry>> target) throws IOException { + int maxSurface = 0; + int lineNumber = 0; + for (final String line : readLines(file, charset)) { + lineNumber++; + if (line.isEmpty()) { + continue; + } + final List<String> fields = splitCsv(line); + if (fields.size() < 4) { + throw new IOException("malformed entry at " + file + " line " + lineNumber); + } + final String surface = fields.get(0); + if (surface.isEmpty()) { + continue; + } + final WordEntry entry = new WordEntry( + parseInt(fields.get(1), file.toString(), lineNumber), + parseInt(fields.get(2), file.toString(), lineNumber), + parseInt(fields.get(3), file.toString(), lineNumber), + List.copyOf(fields.subList(4, fields.size()))); + target.computeIfAbsent(surface, key -> new ArrayList<>(1)).add(entry); + maxSurface = Math.max(maxSurface, surface.length()); + } + return maxSurface; + } + + /** Reads char.def: category behavior lines and code point mapping lines. */ + private static void readCharacterDefinition(Path file, Charset charset, + Map<String, Category> categories, String[] categoryOfChar) throws IOException { + int lineNumber = 0; + for (final String raw : readLines(file, charset)) { + lineNumber++; + final String line = stripComment(raw).trim(); + if (line.isEmpty()) { + continue; + } + final String[] fields = splitWhitespace(line); + if (fields[0].startsWith("0x") || fields[0].startsWith("0X")) { + final int rangeSeparator = fields[0].indexOf(".."); + final int from; + final int to; + if (rangeSeparator >= 0) { + from = parseCodePoint(fields[0].substring(0, rangeSeparator), file, lineNumber); + to = parseCodePoint(fields[0].substring(rangeSeparator + 2), file, lineNumber); + } else { + from = parseCodePoint(fields[0], file, lineNumber); + to = from; + } + if (fields.length < 2) { + throw new IOException("mapping without category at " + file + " line " + lineNumber); + } + for (int c = from; c <= to && c <= Character.MAX_VALUE; c++) { + categoryOfChar[c] = fields[1]; + } + } else { + if (fields.length < 4) { + throw new IOException("malformed category at " + file + " line " + lineNumber); + } + categories.put(fields[0], new Category(fields[0], + "1".equals(fields[1]), "1".equals(fields[2]), + parseInt(fields[3], file.toString(), lineNumber))); + } + } + if (!categories.containsKey("DEFAULT")) { + throw new IOException("char.def defines no DEFAULT category: " + file); + } + } + + /** + * Looks up the lexicon entries for an exact surface form. + * + * @param surface The surface form. + * @return The entries, or {@code null} when the surface is not listed. + */ + List<WordEntry> lookup(String surface) { + return lexicon.get(surface); + } + + /** @return The longest surface form in the lexicon, bounding prefix enumeration. */ + int maxSurfaceLength() { + return maxSurfaceLength; + } + + /** + * Reads the connection cost between two adjacent nodes. + * + * @param rightId The right context id of the earlier node. + * @param leftId The left context id of the later node. + * @return The connection cost. + */ + int connectionCost(int rightId, int leftId) { + return connectionCosts[rightId * rightSize + leftId]; + } + + /** + * Classifies a character. + * + * @param c The character. + * @return Its category, falling back to {@code DEFAULT}. Never {@code null}. + */ + Category categoryOf(char c) { + final String name = categoryOfChar[c]; + final Category category = name == null ? null : categories.get(name); + return category != null ? category : categories.get("DEFAULT"); + } + + /** + * Looks up the unknown-word templates of a category. + * + * @param category The category name. + * @return The templates, or {@code null} when the category has none. + */ + List<WordEntry> unknownEntries(String category) { + return unknownEntries.get(category); + } + + private static List<String> readLines(Path file, Charset charset) throws IOException { + if (!Files.exists(file)) { + throw new IOException("required dictionary file is missing: " + file); + } + final String content = new String(Files.readAllBytes(file), charset); + final List<String> lines = new ArrayList<>(); + int start = 0; + for (int i = 0; i <= content.length(); i++) { + if (i == content.length() || content.charAt(i) == '\n') { + int end = i; + if (end > start && content.charAt(end - 1) == '\r') { + end--; + } + lines.add(content.substring(start, end)); + start = i + 1; + } + } + return lines; + } + + private static String stripComment(String line) { + final int hash = line.indexOf('#'); + return hash < 0 ? line : line.substring(0, hash); + } + + private static List<String> splitCsv(String line) { + final List<String> fields = new ArrayList<>(); + int start = 0; + for (int i = 0; i <= line.length(); i++) { + if (i == line.length() || line.charAt(i) == ',') { + fields.add(line.substring(start, i)); + start = i + 1; + } + } + return fields; + } + + private static String[] splitWhitespace(String line) { + final List<String> parts = new ArrayList<>(); + int start = -1; + for (int i = 0; i <= line.length(); i++) { + if (i == line.length() || StringUtil.isWhitespace(line.charAt(i))) { + if (start >= 0) { + parts.add(line.substring(start, i)); + start = -1; + } + } else if (start < 0) { + start = i; + } + } + return parts.toArray(new String[0]); + } + + private static int parseInt(String text, String file, int lineNumber) + throws IOException { + try { + return Integer.parseInt(text.trim()); + } catch (NumberFormatException e) { + throw new IOException("malformed number in " + file + " line " + lineNumber, e); + } + } + + private static int parseCodePoint(String text, Path file, int lineNumber) + throws IOException { + try { + return Integer.parseInt(text.trim().substring(2), 16); + } catch (RuntimeException e) { + throw new IOException("malformed code point in " + file + " line " + lineNumber, e); + } + } +} diff --git a/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/MecabDictionaryInstaller.java b/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/MecabDictionaryInstaller.java new file mode 100644 index 000000000..33f3ef58d --- /dev/null +++ b/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/MecabDictionaryInstaller.java @@ -0,0 +1,226 @@ +/* + * 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.net.URI; +import java.nio.charset.StandardCharsets; +import java.nio.file.Files; +import java.nio.file.Path; +import java.nio.file.StandardCopyOption; +import java.util.zip.GZIPInputStream; + +/** + * Fetches and unpacks a mecab-format dictionary archive into a local directory, so the + * dictionary is acquired by the user at install time and never ships with this library. + * The user supplies the archive location from the dictionary project of their choice + * and thereby accepts that dictionary's license; nothing is bundled and no location is + * built in. + * + * <p>The installer reads gzip-compressed tar archives, the format the common + * distributions use, and extracts only the files a {@link MecabDictionary} reads: + * {@code *.csv}, {@code *.def}, and {@code dicrc}. Entries are flattened to their base + * names, which also means no archive path can escape the target directory.</p> + * + * @since 3.0.0 + */ +public final class MecabDictionaryInstaller { + + private static final int TAR_BLOCK = 512; + private static final int TAR_NAME_LENGTH = 100; + private static final int TAR_SIZE_OFFSET = 124; + private static final int TAR_SIZE_LENGTH = 12; + private static final int TAR_TYPE_OFFSET = 156; + + private MecabDictionaryInstaller() { + // static installer only + } + + /** + * Downloads a dictionary archive and unpacks it. + * + * @param archive The archive location, a gzip-compressed tar. Must not be + * {@code null}. + * @param targetDirectory The directory to unpack into; created when absent. Must not + * be {@code null}. + * @return The number of dictionary files extracted. + * @throws IOException Thrown if fetching, reading, or writing fails, or the archive + * contains no dictionary file. + * @throws IllegalArgumentException Thrown if a parameter is {@code null}. + */ + public static int install(URI archive, Path targetDirectory) throws IOException { + if (archive == null || targetDirectory == null) { + throw new IllegalArgumentException("archive and targetDirectory must not be null"); + } + try (InputStream in = archive.toURL().openStream()) { + return extract(in, targetDirectory); + } + } + + /** + * Unpacks a dictionary archive stream. + * + * @param archiveStream The gzip-compressed tar content. Must not be {@code null}. + * Not closed. + * @param targetDirectory The directory to unpack into; created when absent. Must not + * be {@code null}. + * @return The number of dictionary files extracted. + * @throws IOException Thrown if reading or writing fails, or the archive contains no + * dictionary file. + * @throws IllegalArgumentException Thrown if a parameter is {@code null}. + */ + public static int extract(InputStream archiveStream, Path targetDirectory) + throws IOException { + if (archiveStream == null || targetDirectory == null) { + throw new IllegalArgumentException("stream and targetDirectory must not be null"); + } + Files.createDirectories(targetDirectory); + final InputStream tar = new GZIPInputStream(archiveStream); + final byte[] header = new byte[TAR_BLOCK]; + int extracted = 0; + while (readBlock(tar, header)) { + if (isEndBlock(header)) { + break; + } + final String name = headerName(header); + final long size = headerSize(header); + final char type = (char) header[TAR_TYPE_OFFSET]; + final String baseName = baseName(name); + final boolean wanted = (type == '0' || type == 0) + && (baseName.endsWith(".csv") || baseName.endsWith(".def") + || "dicrc".equals(baseName)); + if (wanted) { + final Path file = targetDirectory.resolve(baseName); + try (InputStream entry = boundedStream(tar, size)) { + Files.copy(entry, file, StandardCopyOption.REPLACE_EXISTING); + } + extracted++; + skip(tar, padding(size)); + } else { + skip(tar, size + padding(size)); + } + } + if (extracted == 0) { + throw new IOException("the archive contains no dictionary file"); + } + return extracted; + } + + private static boolean readBlock(InputStream in, byte[] block) throws IOException { + int filled = 0; + while (filled < block.length) { + final int read = in.read(block, filled, block.length - filled); + if (read < 0) { + if (filled == 0) { + return false; + } + throw new IOException("truncated tar header"); + } + filled += read; + } + return true; + } + + private static boolean isEndBlock(byte[] block) { + for (final byte b : block) { + if (b != 0) { + return false; + } + } + return true; + } + + private static String headerName(byte[] header) { + int end = 0; + while (end < TAR_NAME_LENGTH && header[end] != 0) { + end++; + } + return new String(header, 0, end, StandardCharsets.UTF_8); + } + + private static long headerSize(byte[] header) throws IOException { + long size = 0; + for (int i = TAR_SIZE_OFFSET; i < TAR_SIZE_OFFSET + TAR_SIZE_LENGTH; i++) { + final byte b = header[i]; + if (b == 0 || b == ' ') { + continue; + } + if (b < '0' || b > '7') { + throw new IOException("malformed tar size field"); + } + size = size * 8 + (b - '0'); + } + return size; + } + + private static String baseName(String name) { + final int slash = name.lastIndexOf('/'); + return slash < 0 ? name : name.substring(slash + 1); + } + + private static long padding(long size) { + final long remainder = size % TAR_BLOCK; + return remainder == 0 ? 0 : TAR_BLOCK - remainder; + } + + private static void skip(InputStream in, long bytes) throws IOException { + long remaining = bytes; + final byte[] buffer = new byte[8192]; + while (remaining > 0) { + final int read = in.read(buffer, 0, (int) Math.min(buffer.length, remaining)); + if (read < 0) { + throw new IOException("truncated tar entry"); + } + remaining -= read; + } + } + + /** Wraps the tar stream so exactly one entry's bytes are readable. */ + private static InputStream boundedStream(InputStream in, long size) { + return new InputStream() { + private long remaining = size; + + @Override + public int read() throws IOException { + if (remaining <= 0) { + return -1; + } + final int b = in.read(); + if (b < 0) { + throw new IOException("truncated tar entry"); + } + remaining--; + return b; + } + + @Override + public int read(byte[] buffer, int offset, int length) throws IOException { + if (remaining <= 0) { + return -1; + } + final int read = in.read(buffer, offset, (int) Math.min(length, remaining)); + if (read < 0) { + throw new IOException("truncated tar entry"); + } + remaining -= read; + return read; + } + }; + } +} diff --git a/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/Morpheme.java b/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/Morpheme.java new file mode 100644 index 000000000..a6694ddc5 --- /dev/null +++ b/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/tokenize/lattice/Morpheme.java @@ -0,0 +1,64 @@ +/* + * 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.util.List; + +import opennlp.tools.util.Span; + +/** + * One morpheme from lattice segmentation: the {@link Span} it covers in the original + * text, its surface form, and the feature columns its dictionary entry carries. + * + * <p>The features are the entry's columns exactly as listed in the dictionary, since + * different dictionaries carry different schemas: part of speech first by convention, + * then dictionary-specific columns such as conjugation, base form, or reading. A + * morpheme produced by unknown-word handling has the unknown entry's features and is + * marked as such.</p> + * + * @param span The location of the morpheme in the original text. Must not be + * {@code null}. + * @param surface The covered text. Must not be {@code null} or empty. + * @param features The dictionary feature columns. Must not be {@code null}. + * @param unknown Whether the morpheme came from unknown-word handling rather than a + * lexicon entry. + * + * @since 3.0.0 + */ +public record Morpheme(Span span, String surface, List<String> features, + boolean unknown) { + + /** + * Validates the morpheme. + * + * @throws IllegalArgumentException Thrown if {@code span}, {@code surface}, or + * {@code features} is {@code null}, or {@code surface} is empty. + */ + public Morpheme { + if (span == null) { + throw new IllegalArgumentException("span must not be null"); + } + if (surface == null || surface.isEmpty()) { + throw new IllegalArgumentException("surface must not be null or empty"); + } + if (features == null) { + throw new IllegalArgumentException("features must not be null"); + } + features = List.copyOf(features); + } +} diff --git a/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/tokenize/lattice/LatticeTokenizerTest.java b/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/tokenize/lattice/LatticeTokenizerTest.java new file mode 100644 index 000000000..1c3f40a8d --- /dev/null +++ b/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/tokenize/lattice/LatticeTokenizerTest.java @@ -0,0 +1,153 @@ +/* + * 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.nio.charset.StandardCharsets; +import java.nio.file.Files; +import java.nio.file.Path; +import java.util.List; + +import org.junit.jupiter.api.Assertions; +import org.junit.jupiter.api.BeforeAll; +import org.junit.jupiter.api.Test; +import org.junit.jupiter.api.io.TempDir; + +import opennlp.tools.util.Span; + +/** + * Tests the lattice segmenter against a project-authored miniature dictionary; no + * external dictionary data is involved. + */ +public class LatticeTokenizerTest { + + @TempDir + static Path directory; + + private static LatticeTokenizer tokenizer; + + @BeforeAll + static void loadDictionary() throws IOException { + write("lexicon.csv", String.join("\n", + "東京,0,0,3000,noun,proper", + "京都,0,0,3000,noun,proper", + "東,0,0,6000,noun,common", + "都,0,0,4000,noun,suffix", + "に,0,0,1000,particle,case", + "行く,0,0,3000,verb,base", + "")); + write("matrix.def", "1 1\n0 0 0\n"); + write("char.def", String.join("\n", + "DEFAULT 0 1 0", + "KANJI 0 0 2", + "HIRAGANA 0 1 0", + "LATIN 1 1 0", + "", + "0x3041..0x3096 HIRAGANA", + "0x4E00..0x9FFF KANJI", + "0x0041..0x005A LATIN", + "0x0061..0x007A LATIN", + "")); + write("unk.def", String.join("\n", + "DEFAULT,0,0,10000,symbol,unknown", + "LATIN,0,0,4000,noun,foreign", + "KANJI,0,0,8000,noun,unknown", + "HIRAGANA,0,0,9000,particle,unknown", + "")); + tokenizer = new LatticeTokenizer(MecabDictionary.load(directory)); + } + + private static void write(String name, String content) throws IOException { + Files.write(directory.resolve(name), content.getBytes(StandardCharsets.UTF_8)); + } + + @Test + void testLatticePrefersTheCheaperSegmentation() { + // the famous case: Tokyo+Metro must win over East+Kyoto + final String text = "東京都に行く"; + Assertions.assertArrayEquals( + new String[] {"東京", "都", "に", "行く"}, + tokenizer.tokenize(text)); + Assertions.assertArrayEquals(new Span[] { + new Span(0, 2), new Span(2, 3), new Span(3, 4), new Span(4, 6)}, + tokenizer.tokenizePos(text)); + } + + @Test + void testMorphemesCarryDictionaryFeatures() { + final List<Morpheme> morphemes = + tokenizer.analyze("東京都に行く"); + Assertions.assertEquals(4, morphemes.size()); + Assertions.assertEquals(List.of("noun", "proper"), morphemes.get(0).features()); + Assertions.assertEquals(List.of("particle", "case"), morphemes.get(2).features()); + Assertions.assertEquals(false, morphemes.get(0).unknown()); + } + + @Test + void testUnknownLatinRunGroupsIntoOneMorpheme() { + final List<Morpheme> morphemes = tokenizer.analyze("ABCに行く"); + Assertions.assertEquals(3, morphemes.size()); + Assertions.assertEquals("ABC", morphemes.get(0).surface()); + Assertions.assertEquals(true, morphemes.get(0).unknown()); + Assertions.assertEquals(List.of("noun", "foreign"), morphemes.get(0).features()); + } + + @Test + void testUnknownKanjiPreferOneMorphemeOverTwo() { + final List<Morpheme> morphemes = tokenizer.analyze("峠道に行く"); + Assertions.assertEquals(3, morphemes.size()); + Assertions.assertEquals("峠道", morphemes.get(0).surface()); + Assertions.assertEquals(true, morphemes.get(0).unknown()); + } + + @Test + void testWhitespaceSeparatesAndIsNeverAMorpheme() { + final String text = "東京 に 行く"; + Assertions.assertArrayEquals( + new String[] {"東京", "に", "行く"}, + tokenizer.tokenize(text)); + Assertions.assertArrayEquals(new Span[] { + new Span(0, 2), new Span(3, 4), new Span(5, 7)}, + tokenizer.tokenizePos(text)); + Assertions.assertEquals(0, tokenizer.analyze(" ").size()); + Assertions.assertEquals(0, tokenizer.analyze("").size()); + } + + @Test + void testMalformedDictionariesFailLoud(@TempDir Path broken) throws IOException { + Files.write(broken.resolve("lexicon.csv"), + "東,0,0,3000,noun\n".getBytes(StandardCharsets.UTF_8)); + Assertions.assertThrows(IOException.class, () -> MecabDictionary.load(broken)); + + Files.write(broken.resolve("matrix.def"), "1 1\n0 0 0\n".getBytes(StandardCharsets.UTF_8)); + Files.write(broken.resolve("char.def"), + "KANJI 0 0 2\n0x4E00..0x9FFF KANJI\n".getBytes(StandardCharsets.UTF_8)); + Files.write(broken.resolve("unk.def"), + "KANJI,0,0,8000,noun\n".getBytes(StandardCharsets.UTF_8)); + Assertions.assertThrows(IOException.class, () -> MecabDictionary.load(broken)); + } + + @Test + void testInvalidArguments() { + Assertions.assertThrows(IllegalArgumentException.class, + () -> new LatticeTokenizer(null)); + Assertions.assertThrows(IllegalArgumentException.class, + () -> MecabDictionary.load(null)); + Assertions.assertThrows(IllegalArgumentException.class, () -> tokenizer.analyze(null)); + } +} diff --git a/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/tokenize/lattice/MecabDictionaryInstallerTest.java b/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/tokenize/lattice/MecabDictionaryInstallerTest.java new file mode 100644 index 000000000..fe999e460 --- /dev/null +++ b/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/tokenize/lattice/MecabDictionaryInstallerTest.java @@ -0,0 +1,133 @@ +/* + * 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.ByteArrayOutputStream; +import java.io.IOException; +import java.nio.charset.StandardCharsets; +import java.nio.file.Files; +import java.nio.file.Path; +import java.util.zip.GZIPOutputStream; + +import org.junit.jupiter.api.Assertions; +import org.junit.jupiter.api.Test; +import org.junit.jupiter.api.io.TempDir; + +public class MecabDictionaryInstallerTest { + + /** Writes one ustar entry: a 512-byte header block and padded content. */ + private static void tarEntry(ByteArrayOutputStream tar, String name, byte[] content) + throws IOException { + final byte[] header = new byte[512]; + final byte[] nameBytes = name.getBytes(StandardCharsets.UTF_8); + System.arraycopy(nameBytes, 0, header, 0, nameBytes.length); + final byte[] mode = "0000644".getBytes(StandardCharsets.US_ASCII); + System.arraycopy(mode, 0, header, 100, mode.length); + final String size = String.format("%011o", content.length); + System.arraycopy(size.getBytes(StandardCharsets.US_ASCII), 0, header, 124, 11); + header[156] = '0'; + for (int i = 148; i < 156; i++) { + header[i] = ' '; + } + int checksum = 0; + for (final byte b : header) { + checksum += b & 0xFF; + } + final String checksumText = String.format("%06o", checksum); + System.arraycopy(checksumText.getBytes(StandardCharsets.US_ASCII), 0, header, 148, 6); + header[154] = 0; + header[155] = ' '; + tar.write(header); + tar.write(content); + final int padding = (512 - content.length % 512) % 512; + tar.write(new byte[padding]); + } + + private static byte[] archive(String[][] entries) throws IOException { + final ByteArrayOutputStream tar = new ByteArrayOutputStream(); + for (final String[] entry : entries) { + tarEntry(tar, entry[0], entry[1].getBytes(StandardCharsets.UTF_8)); + } + tar.write(new byte[1024]); + final ByteArrayOutputStream compressed = new ByteArrayOutputStream(); + try (GZIPOutputStream gzip = new GZIPOutputStream(compressed)) { + gzip.write(tar.toByteArray()); + } + return compressed.toByteArray(); + } + + @Test + void testExtractsDictionaryFilesAndFlattensPaths(@TempDir Path target) + throws IOException { + final byte[] archive = archive(new String[][] { + {"dict-1.0/lexicon.csv", "cat,0,0,100,noun\n"}, + {"dict-1.0/matrix.def", "1 1\n0 0 0\n"}, + {"dict-1.0/char.def", "DEFAULT 0 1 0\n"}, + {"dict-1.0/unk.def", "DEFAULT,0,0,10000,unknown\n"}, + {"dict-1.0/README", "not a dictionary file"}, + {"dict-1.0/dicrc", "config"}}); + + final int extracted = MecabDictionaryInstaller.extract( + new ByteArrayInputStream(archive), target); + + Assertions.assertEquals(5, extracted); + Assertions.assertTrue(Files.exists(target.resolve("lexicon.csv"))); + Assertions.assertTrue(Files.exists(target.resolve("matrix.def"))); + Assertions.assertTrue(Files.exists(target.resolve("char.def"))); + Assertions.assertTrue(Files.exists(target.resolve("unk.def"))); + Assertions.assertTrue(Files.exists(target.resolve("dicrc"))); + Assertions.assertTrue(Files.notExists(target.resolve("README"))); + Assertions.assertEquals("cat,0,0,100,noun\n", + Files.readString(target.resolve("lexicon.csv"))); + } + + @Test + void testInstallReadsAFileUri(@TempDir Path source, @TempDir Path target) + throws IOException { + final Path archiveFile = source.resolve("dict.tar.gz"); + Files.write(archiveFile, archive(new String[][] { + {"d/words.csv", "cat,0,0,100,noun\n"}, + {"d/matrix.def", "1 1\n0 0 0\n"}})); + + final int extracted = + MecabDictionaryInstaller.install(archiveFile.toUri(), target); + + Assertions.assertEquals(2, extracted); + Assertions.assertTrue(Files.exists(target.resolve("words.csv"))); + } + + @Test + void testArchivesWithoutDictionaryFilesFailLoud(@TempDir Path target) + throws IOException { + final byte[] archive = archive(new String[][] {{"readme.txt", "nothing here"}}); + Assertions.assertThrows(IOException.class, () -> MecabDictionaryInstaller.extract( + new ByteArrayInputStream(archive), target)); + } + + @Test + void testInvalidArguments(@TempDir Path target) { + Assertions.assertThrows(IllegalArgumentException.class, + () -> MecabDictionaryInstaller.install(null, target)); + Assertions.assertThrows(IllegalArgumentException.class, + () -> MecabDictionaryInstaller.extract(null, target)); + Assertions.assertThrows(IllegalArgumentException.class, + () -> MecabDictionaryInstaller.extract( + new ByteArrayInputStream(new byte[0]), null)); + } +}
