github-actions[bot] commented on code in PR #64667: URL: https://github.com/apache/doris/pull/64667#discussion_r3893352000
########## NOTICE.txt: ########## @@ -73,6 +73,9 @@ This software includes third party software subject to the following copyrights: - Netty Reactive Streams - https://github.com/playframework/netty-reactive-streams - Jackson-core - https://github.com/FasterXML/jackson-core - Jackson-dataformat-cbor - https://github.com/FasterXML/jackson-dataformats-binary +- Darts-clone (double-array trie) - Copyright 2008-2014 Susumu Yata - https://github.com/s-yata/darts-clone (BSD 2-clause; see dist/licenses/LICENSE-darts-clone.txt) Review Comment: [Major] Make this third-party metadata match each distribution artifact. BE compiles Darts into the runtime dictionary and ships the generated IPADIC data, but `dist/LICENSE-dist.txt` registers neither; `copy_common_files` also copies this same NOTICE into FE even though FE contains neither payload. In both packages the license directory is `licenses/...`, so these `dist/licenses/...` pointers do not resolve, and the source `LICENSE.txt` has no Darts pointer either. Please put the license details/pointers in the applicable source and binary LICENSE manifests and keep each packaged NOTICE consistent with its actual contents. ########## be/src/storage/index/inverted/analyzer/kuromoji/kuromoji_viterbi.cpp: ########## @@ -0,0 +1,300 @@ +// 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. + +#include "storage/index/inverted/analyzer/kuromoji/kuromoji_viterbi.h" + +#include <algorithm> +#include <cstddef> +#include <limits> + +namespace doris::segment_v2::inverted_index::kuromoji { + +namespace { + +constexpr int64_t KMJ_INF = std::numeric_limits<int64_t>::max() / 4; +constexpr uint32_t MAX_UNKNOWN_GROUP_CHARS = 1024; + +// Search/Extended-mode compound-decomposition penalties, matching Lucene's +// JapaneseTokenizer. Lengths are counted in code points. A token longer than the +// length threshold is penalized so the minimum-cost path prefers its shorter +// parts: all-kanji runs over KANJI_LENGTH chars, other runs over OTHER_LENGTH. +constexpr uint32_t SEARCH_MODE_KANJI_LENGTH = 2; +constexpr int64_t SEARCH_MODE_KANJI_PENALTY = 3000; +constexpr uint32_t SEARCH_MODE_OTHER_LENGTH = 7; +constexpr int64_t SEARCH_MODE_OTHER_PENALTY = 1700; + +struct DecodedCp { + char32_t cp; + uint32_t len; +}; + +// Decode one UTF-8 code point at text[pos]. +DecodedCp decode_utf8(std::string_view text, std::size_t pos) { + auto b0 = static_cast<unsigned char>(text[pos]); + const std::size_t avail = text.size() - pos; + if (b0 < 0x80) { + return {b0, 1}; + } + auto cont = [&](std::size_t i) { + return (static_cast<unsigned char>(text[pos + i]) & 0xC0U) == 0x80U; + }; + if ((b0 >> 5) == 0x6 && avail >= 2 && cont(1)) { + auto b1 = static_cast<unsigned char>(text[pos + 1]); + const auto cp = static_cast<char32_t>(((b0 & 0x1FU) << 6) | (b1 & 0x3FU)); + if (cp >= 0x80) { // reject overlong + return {cp, 2}; + } + } else if ((b0 >> 4) == 0xE && avail >= 3 && cont(1) && cont(2)) { + auto b1 = static_cast<unsigned char>(text[pos + 1]); + auto b2 = static_cast<unsigned char>(text[pos + 2]); + const auto cp = + static_cast<char32_t>(((b0 & 0x0FU) << 12) | ((b1 & 0x3FU) << 6) | (b2 & 0x3FU)); + if (cp >= 0x800 && (cp < 0xD800 || cp > 0xDFFF)) { // reject overlong + surrogates + return {cp, 3}; + } + } else if ((b0 >> 3) == 0x1E && avail >= 4 && cont(1) && cont(2) && cont(3)) { + auto b1 = static_cast<unsigned char>(text[pos + 1]); + auto b2 = static_cast<unsigned char>(text[pos + 2]); + auto b3 = static_cast<unsigned char>(text[pos + 3]); + const auto cp = static_cast<char32_t>(((b0 & 0x07U) << 18) | ((b1 & 0x3FU) << 12) | + ((b2 & 0x3FU) << 6) | (b3 & 0x3FU)); + if (cp >= 0x10000 && cp <= 0x10FFFF) { // reject overlong + out of range + return {cp, 4}; + } + } + return {b0, 1}; +} + +// Lucene JapaneseTokenizer's search-mode penalty for the token covering +// [start, end) bytes: penalize long compounds so the Viterbi prefers their +// shorter parts. Returns 0 for tokens at or under the length thresholds. +int64_t compute_penalty(const KuromojiDictionary& dict, std::string_view text, uint32_t start, + uint32_t end) { + uint32_t length = 0; + bool all_kanji = true; + for (uint32_t p = start; p < end;) { + const DecodedCp d = decode_utf8(text, p); + if (dict.char_category(d.cp) != CAT_KANJI) { + all_kanji = false; + } + p += d.len; + ++length; + } + if (length > SEARCH_MODE_KANJI_LENGTH) { + if (all_kanji) { + return static_cast<int64_t>(length - SEARCH_MODE_KANJI_LENGTH) * + SEARCH_MODE_KANJI_PENALTY; + } + if (length > SEARCH_MODE_OTHER_LENGTH) { + return static_cast<int64_t>(length - SEARCH_MODE_OTHER_LENGTH) * + SEARCH_MODE_OTHER_PENALTY; + } + } + return 0; +} + +// A lattice node spanning [start, end) bytes of the input. +struct VNode { + uint32_t start; + uint32_t end; + int16_t left_id; + int16_t right_id; + int16_t word_cost; + bool known; + uint32_t word_id; + int64_t total_cost; + int back; // previous node index, -1 if none +}; + +} // namespace + +void KuromojiViterbi::segment(std::string_view text, std::vector<KuromojiMorpheme>* out) const { + out->clear(); + const auto n = static_cast<uint32_t>(text.size()); + if (n == 0) { + return; + } + + std::vector<VNode> nodes; + std::vector<int32_t> end_head(n + 1, -1); + std::vector<int32_t> end_next; + + // BOS (index 0): ends at position 0, context id 0, zero cost. + nodes.push_back(VNode {0, 0, 0, 0, 0, false, 0, 0, -1}); + end_next.push_back(-1); + end_head[0] = 0; + + auto penalty_for = [&](uint32_t s, uint32_t e) -> int64_t { + return _mode == KuromojiMode::Normal ? 0 : compute_penalty(_dict, text, s, e); + }; + + // Add a node and relax it against all nodes ending at its start position. + auto add_node = [&](uint32_t s, uint32_t e, int16_t lid, int16_t rid, int16_t wcost, bool known, + uint32_t wid, int64_t penalty) { + int64_t best = KMJ_INF; + int best_prev = -1; + for (int pe = end_head[s]; pe >= 0; pe = end_next[pe]) { + const VNode& pv = nodes[static_cast<std::size_t>(pe)]; + if (pv.total_cost >= KMJ_INF) { + continue; + } + const int64_t c = + pv.total_cost + _dict.connection_cost(static_cast<uint32_t>(pv.right_id), + static_cast<uint32_t>(lid)); + if (c <= best) { + best = c; + best_prev = pe; + } + } + if (best_prev < 0) { + return; + } + const auto idx = static_cast<int>(nodes.size()); + nodes.push_back( + VNode {s, e, lid, rid, wcost, known, wid, best + wcost + penalty, best_prev}); + end_next.push_back(end_head[e]); + end_head[e] = idx; + }; + + // Cache of the current same-category run's byte end, so grouped unknown words are not rescanned at every position inside one run. + uint32_t cat_run_end = 0; + uint8_t cat_run_cat = 0; + bool cat_run_valid = false; + + uint32_t pos = 0; + std::vector<KuromojiDictionary::PrefixMatch> matches; + while (pos < n) { + if (end_head[pos] < 0) { + pos += decode_utf8(text, pos).len; // unreachable boundary; skip + continue; + } + const DecodedCp d0 = decode_utf8(text, pos); + const auto before = nodes.size(); + + // System-dictionary words (common-prefix search). + _dict.common_prefix_search(text.data() + pos, n - pos, &matches); + bool any_known = false; + for (const auto& mt : matches) { + const int64_t pen = penalty_for(pos, pos + mt.length); + const WordIdRun run = _dict.run_for_value(mt.trie_value); + for (uint32_t k = 0; k < run.count; ++k) { + const uint32_t wid = run.entry_start + k; + const WordEntry& e = _dict.word(wid); + add_node(pos, pos + mt.length, e.left_id, e.right_id, e.word_cost, true, wid, pen); + any_known = true; + } + } + + // Unknown words: when no known word starts here, or the category forces it. + if (!any_known || _dict.is_invoke(d0.cp)) { Review Comment: [Major] Preserve an alternate route for search-mode decomposition. This gate suppresses unknown arcs whenever any known word starts here, regardless of mode. With a supported dictionary containing only a three-kanji system entry and no shorter entries, the interior boundaries stay unreachable, so adding the search penalty cannot produce an alternate path and Search/Extended still return the whole compound. The current test masks this by seeding every single-kanji entry, while the referenced Lucene search flow explicitly explores alternate segmentations. Make the gate mode-aware (or otherwise construct that route) and add a long-only compound fixture. ########## be/src/storage/index/inverted/analyzer/kuromoji/kuromoji_viterbi.cpp: ########## @@ -0,0 +1,300 @@ +// 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. + +#include "storage/index/inverted/analyzer/kuromoji/kuromoji_viterbi.h" + +#include <algorithm> +#include <cstddef> +#include <limits> + +namespace doris::segment_v2::inverted_index::kuromoji { + +namespace { + +constexpr int64_t KMJ_INF = std::numeric_limits<int64_t>::max() / 4; +constexpr uint32_t MAX_UNKNOWN_GROUP_CHARS = 1024; + +// Search/Extended-mode compound-decomposition penalties, matching Lucene's +// JapaneseTokenizer. Lengths are counted in code points. A token longer than the +// length threshold is penalized so the minimum-cost path prefers its shorter +// parts: all-kanji runs over KANJI_LENGTH chars, other runs over OTHER_LENGTH. +constexpr uint32_t SEARCH_MODE_KANJI_LENGTH = 2; +constexpr int64_t SEARCH_MODE_KANJI_PENALTY = 3000; +constexpr uint32_t SEARCH_MODE_OTHER_LENGTH = 7; +constexpr int64_t SEARCH_MODE_OTHER_PENALTY = 1700; + +struct DecodedCp { + char32_t cp; + uint32_t len; +}; + +// Decode one UTF-8 code point at text[pos]. +DecodedCp decode_utf8(std::string_view text, std::size_t pos) { + auto b0 = static_cast<unsigned char>(text[pos]); + const std::size_t avail = text.size() - pos; + if (b0 < 0x80) { + return {b0, 1}; + } + auto cont = [&](std::size_t i) { + return (static_cast<unsigned char>(text[pos + i]) & 0xC0U) == 0x80U; + }; + if ((b0 >> 5) == 0x6 && avail >= 2 && cont(1)) { + auto b1 = static_cast<unsigned char>(text[pos + 1]); + const auto cp = static_cast<char32_t>(((b0 & 0x1FU) << 6) | (b1 & 0x3FU)); + if (cp >= 0x80) { // reject overlong + return {cp, 2}; + } + } else if ((b0 >> 4) == 0xE && avail >= 3 && cont(1) && cont(2)) { + auto b1 = static_cast<unsigned char>(text[pos + 1]); + auto b2 = static_cast<unsigned char>(text[pos + 2]); + const auto cp = + static_cast<char32_t>(((b0 & 0x0FU) << 12) | ((b1 & 0x3FU) << 6) | (b2 & 0x3FU)); + if (cp >= 0x800 && (cp < 0xD800 || cp > 0xDFFF)) { // reject overlong + surrogates + return {cp, 3}; + } + } else if ((b0 >> 3) == 0x1E && avail >= 4 && cont(1) && cont(2) && cont(3)) { + auto b1 = static_cast<unsigned char>(text[pos + 1]); + auto b2 = static_cast<unsigned char>(text[pos + 2]); + auto b3 = static_cast<unsigned char>(text[pos + 3]); + const auto cp = static_cast<char32_t>(((b0 & 0x07U) << 18) | ((b1 & 0x3FU) << 12) | + ((b2 & 0x3FU) << 6) | (b3 & 0x3FU)); + if (cp >= 0x10000 && cp <= 0x10FFFF) { // reject overlong + out of range + return {cp, 4}; + } + } + return {b0, 1}; +} + +// Lucene JapaneseTokenizer's search-mode penalty for the token covering +// [start, end) bytes: penalize long compounds so the Viterbi prefers their +// shorter parts. Returns 0 for tokens at or under the length thresholds. +int64_t compute_penalty(const KuromojiDictionary& dict, std::string_view text, uint32_t start, + uint32_t end) { + uint32_t length = 0; + bool all_kanji = true; + for (uint32_t p = start; p < end;) { + const DecodedCp d = decode_utf8(text, p); + if (dict.char_category(d.cp) != CAT_KANJI) { Review Comment: [Major] Treat KANJINUMERIC as kanji for the search penalty. IPADIC assigns numeric ideographs such as `δΈ€` to this separate category, but this check marks them non-kanji; a three-to-seven-character numeric compound therefore receives neither the kanji penalty nor the longer non-kanji penalty and can remain whole in Search/Extended even when a cheaper decomposed path should win. Lucene's corresponding `isKanji` includes both KANJI and KANJINUMERIC. Share that predicate here and add a numeric-kanji variant of the compound test. ########## be/test/storage/index/inverted/analyzer/kuromoji/kuromoji_real_dict_test.cpp: ########## @@ -0,0 +1,173 @@ +// 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. + +#include <gtest/gtest.h> +#include <sys/stat.h> + +#include <algorithm> +#include <cstdlib> +#include <iostream> +#include <memory> +#include <string> +#include <vector> + +#include "CLucene.h" +#include "common/config.h" +#include "storage/index/inverted/analyzer/analyzer.h" +#include "storage/index/inverted/analyzer/kuromoji/dict/kuromoji_dictionary.h" +#include "storage/index/inverted/analyzer/kuromoji/kuromoji_viterbi.h" +#include "storage/index/inverted/inverted_index_parser.h" + +// End-to-end against the REAL IPADIC dictionary generated under be/dict/kuromoji. +// Skips if the dictionary has not been generated on this host (e.g. plain CI), +// so it is safe to keep in the suite. +namespace doris::segment_v2::inverted_index::kuromoji { + +static std::string real_dict_dir() { + const char* home = std::getenv("DORIS_HOME"); + return std::string(home != nullptr ? home : ".") + "/be/dict/kuromoji"; Review Comment: [Major] Resolve the real dictionary from a path the BE test runner actually stages. `run-be-ut.sh` resets `DORIS_HOME` to `${DORIS_TEST_BINARY_DIR}/` immediately before launching `doris_be_test`, so this becomes `${ut_build}/test/be/dict/kuromoji`; the documented generator writes repository `be/dict/kuromoji`, and neither the runner nor test CMake copies it here because `MAKE_TEST=ON` excludes the normal install rule. Consequently all three real-dictionary tests skip even after the documented generation step. Pass/stage the repository dictionary explicitly and verify that generating it makes these tests execute. ########## be/src/storage/index/inverted/inverted_index_parser.cpp: ########## @@ -62,6 +64,8 @@ InvertedIndexParserType get_inverted_index_parser_type_from_string(const std::st return InvertedIndexParserType::PARSER_BASIC; } else if (parser_str_lower == INVERTED_INDEX_PARSER_IK) { return InvertedIndexParserType::PARSER_IK; + } else if (parser_str_lower == INVERTED_INDEX_PARSER_KUROMOJI) { Review Comment: [Minor] Keep TOKENIZE's supported-parser error in sync with this new mapping. Kuromoji is now accepted here, but an invalid parser still reports that only english, chinese, unicode, ICU, basic, and IK are supported, so the public diagnostic omits the parser added by this PR. Update or derive that list from the shared registry and cover the invalid-parser message. -- 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]
