nishant94 commented on code in PR #64667: URL: https://github.com/apache/doris/pull/64667#discussion_r3595287613
########## be/src/storage/index/inverted/analyzer/kuromoji/kuromoji_viterbi.cpp: ########## @@ -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. + +#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]. Invalid/truncated -> single byte. +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}; + } + if ((b0 >> 5) == 0x6 && avail >= 2) { + auto b1 = static_cast<unsigned char>(text[pos + 1]); + return {static_cast<char32_t>(((b0 & 0x1FU) << 6) | (b1 & 0x3FU)), 2}; + } + if ((b0 >> 4) == 0xE && avail >= 3) { + auto b1 = static_cast<unsigned char>(text[pos + 1]); + auto b2 = static_cast<unsigned char>(text[pos + 2]); + return {static_cast<char32_t>(((b0 & 0x0FU) << 12) | ((b1 & 0x3FU) << 6) | (b2 & 0x3FU)), + 3}; + } + if ((b0 >> 3) == 0x1E && avail >= 4) { + 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]); + return {static_cast<char32_t>(((b0 & 0x07U) << 18) | ((b1 & 0x3FU) << 12) | + ((b2 & 0x3FU) << 6) | (b3 & 0x3FU)), + 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; + + // 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 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; + } + // Search/Extended mode penalizes long compounds so shorter parts win. Review Comment: Search mode here is intentionally decompound-only, matching JapaneseTokenizer's original SEARCH semantics. -- 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]
