You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@doris.apache.org by "kzh1458003655-web (via GitHub)" <gi...@apache.org> on 2025/12/13 14:56:30 UTC
[PR] Feat levenshtein final [doris]
kzh1458003655-web opened a new pull request, #59016:
URL: https://github.com/apache/doris/pull/59016
### What changes were made in this pull request?
Implement the Levenshtein distance function (`levenshtein(string_a, string_b)`) in the Vectorized Engine.
This function computes the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other.
### Why are these changes needed?
To provide users with a common string function used for fuzzy string matching, data cleaning, and calculating string similarity.
### Detailed implementation details
1. **UTF-8 Support:** The implementation converts the input strings (which may contain multi-byte UTF-8 characters) into Unicode Code Points (UTF-32 integers) before performing the dynamic programming (DP) calculation. This ensures that the distance is calculated based on the number of *characters*, not the number of *bytes*.
2. **Vectorized Integration:**
* Implemented the logic within `LevenshteinImpl` in `function_string.h`.
* Used `std::string_view` as the input type for `execute` to align with modern Doris versions.
* Registered the function using the `FunctionBinaryToType` alias (`FunctionStringLevenshtein`) along with the `LevenshteinWrapper` adapter in `function_string.cpp`.
3. **Tests:** Added a comprehensive regression test case (`test_string_function_levenshtein.groovy`) covering standard, boundary (empty string), NULL, and critical UTF-8 (Chinese characters) scenarios.
### Note for Reviewers
* The function returns the distance as `INT`.
* The implementation leverages `std::vector<int32_t>` for DP row storage and uses `thread_local` optimization for memory reuse.
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] Feat levenshtein final [doris]
Posted by "zclllyybb (via GitHub)" <gi...@apache.org>.
zclllyybb commented on code in PR #59016:
URL: https://github.com/apache/doris/pull/59016#discussion_r2616353581
##########
be/src/vec/functions/function_string.h:
##########
@@ -5261,6 +5261,96 @@ class FunctionCrc32Internal : public IFunction {
}
};
+class NameLevenshtein {
+public:
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinImpl {
+ static constexpr auto name = "levenshtein";
+
+ // 必需的类型定义
Review Comment:
dont use chinese
##########
regression-test/data/query_p0/sql_functions/string_functions/test_string_function_levenshtein.out:
##########
Review Comment:
doesn't match with your testcase
##########
be/src/vec/functions/function_string.h:
##########
@@ -5261,6 +5261,96 @@ class FunctionCrc32Internal : public IFunction {
}
};
+class NameLevenshtein {
+public:
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinImpl {
+ static constexpr auto name = "levenshtein";
+
+ // 必需的类型定义
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = ColumnInt32::Container;
+
+ static DataTypePtr get_return_type_impl(const DataTypes& arguments) {
+ return std::make_shared<ResultDataType>();
+ }
+
+ // Helper: Get UTF-8 byte length
+ static size_t get_utf8_byte_length(unsigned char byte) {
+ if (byte < 0x80) return 1;
+ if ((byte & 0xE0) == 0xC0) return 2;
+ if ((byte & 0xF0) == 0xE0) return 3;
+ if ((byte & 0xF8) == 0xF0) return 4;
+ return 1;
+ }
+
+ // Helper: Convert UTF-8 byte stream to Unicode code points
+ static void to_utf32(const char* data, size_t size, std::vector<int32_t>& out) {
+ out.clear();
+ size_t i = 0;
+ while (i < size) {
+ size_t char_len = get_utf8_byte_length(static_cast<unsigned char>(data[i]));
+ if (i + char_len > size) char_len = 1;
+
+ int32_t code_point = 0;
+ for (size_t j = 0; j < char_len; ++j) {
+ code_point = (code_point << 8) | static_cast<unsigned char>(data[i + j]);
+ }
+ out.push_back(code_point);
+ i += char_len;
+ }
+ }
+
+ // 核心执行函数: 修正参数类型为 std::string_view
+ static void execute(std::string_view l, std::string_view r, int32_t& res) {
+ // Use thread_local for memory reuse
+ static thread_local std::vector<int32_t> a_code_points;
+ static thread_local std::vector<int32_t> b_code_points;
+
+ // ADMIN REQUIREMENT: Renaming or adding clear comments for these two DP arrays
+ static thread_local std::vector<int32_t> prev_row; // Previous row distances (i-1)
+ static thread_local std::vector<int32_t> curr_row; // Current row distances (i)
+
+ // 注意：std::string_view 使用 .data() 和 .size() 方法
+ to_utf32(l.data(), l.size(), a_code_points);
+ to_utf32(r.data(), r.size(), b_code_points);
+
+ const auto& source = a_code_points;
+ const auto& target = b_code_points;
+
+ size_t n = source.size();
+ size_t m = target.size();
+
+ if (n == 0) {
Review Comment:
add `unlikely` here
##########
be/src/vec/functions/function_string.h:
##########
@@ -5261,6 +5261,96 @@ class FunctionCrc32Internal : public IFunction {
}
};
+class NameLevenshtein {
+public:
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinImpl {
+ static constexpr auto name = "levenshtein";
+
+ // 必需的类型定义
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = ColumnInt32::Container;
+
+ static DataTypePtr get_return_type_impl(const DataTypes& arguments) {
+ return std::make_shared<ResultDataType>();
+ }
+
+ // Helper: Get UTF-8 byte length
+ static size_t get_utf8_byte_length(unsigned char byte) {
+ if (byte < 0x80) return 1;
+ if ((byte & 0xE0) == 0xC0) return 2;
+ if ((byte & 0xF0) == 0xE0) return 3;
+ if ((byte & 0xF8) == 0xF0) return 4;
+ return 1;
+ }
+
+ // Helper: Convert UTF-8 byte stream to Unicode code points
+ static void to_utf32(const char* data, size_t size, std::vector<int32_t>& out) {
+ out.clear();
+ size_t i = 0;
+ while (i < size) {
+ size_t char_len = get_utf8_byte_length(static_cast<unsigned char>(data[i]));
+ if (i + char_len > size) char_len = 1;
+
+ int32_t code_point = 0;
+ for (size_t j = 0; j < char_len; ++j) {
+ code_point = (code_point << 8) | static_cast<unsigned char>(data[i + j]);
+ }
+ out.push_back(code_point);
+ i += char_len;
+ }
+ }
+
+ // 核心执行函数: 修正参数类型为 std::string_view
+ static void execute(std::string_view l, std::string_view r, int32_t& res) {
+ // Use thread_local for memory reuse
+ static thread_local std::vector<int32_t> a_code_points;
+ static thread_local std::vector<int32_t> b_code_points;
+
+ // ADMIN REQUIREMENT: Renaming or adding clear comments for these two DP arrays
+ static thread_local std::vector<int32_t> prev_row; // Previous row distances (i-1)
Review Comment:
why make it `static thread_local`? it's wrong.
##########
be/src/vec/functions/function_string.h:
##########
@@ -5261,6 +5261,96 @@ class FunctionCrc32Internal : public IFunction {
}
};
+class NameLevenshtein {
+public:
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinImpl {
+ static constexpr auto name = "levenshtein";
+
+ // 必需的类型定义
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = ColumnInt32::Container;
+
+ static DataTypePtr get_return_type_impl(const DataTypes& arguments) {
+ return std::make_shared<ResultDataType>();
+ }
+
+ // Helper: Get UTF-8 byte length
+ static size_t get_utf8_byte_length(unsigned char byte) {
+ if (byte < 0x80) return 1;
+ if ((byte & 0xE0) == 0xC0) return 2;
+ if ((byte & 0xF0) == 0xE0) return 3;
+ if ((byte & 0xF8) == 0xF0) return 4;
+ return 1;
+ }
+
+ // Helper: Convert UTF-8 byte stream to Unicode code points
+ static void to_utf32(const char* data, size_t size, std::vector<int32_t>& out) {
+ out.clear();
+ size_t i = 0;
+ while (i < size) {
+ size_t char_len = get_utf8_byte_length(static_cast<unsigned char>(data[i]));
+ if (i + char_len > size) char_len = 1;
+
+ int32_t code_point = 0;
+ for (size_t j = 0; j < char_len; ++j) {
+ code_point = (code_point << 8) | static_cast<unsigned char>(data[i + j]);
+ }
+ out.push_back(code_point);
+ i += char_len;
+ }
+ }
+
+ // 核心执行函数: 修正参数类型为 std::string_view
+ static void execute(std::string_view l, std::string_view r, int32_t& res) {
+ // Use thread_local for memory reuse
+ static thread_local std::vector<int32_t> a_code_points;
+ static thread_local std::vector<int32_t> b_code_points;
+
+ // ADMIN REQUIREMENT: Renaming or adding clear comments for these two DP arrays
+ static thread_local std::vector<int32_t> prev_row; // Previous row distances (i-1)
+ static thread_local std::vector<int32_t> curr_row; // Current row distances (i)
+
+ // 注意：std::string_view 使用 .data() 和 .size() 方法
+ to_utf32(l.data(), l.size(), a_code_points);
Review Comment:
see other funcitons how deal with utf8. like `SubstringUtil`.
##########
regression-test/suites/query_p0/sql_functions/string_functions/test_string_function_levenshtein.groovy:
##########
@@ -0,0 +1,68 @@
+// 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.
+
+suite("test_string_function_levenshtein") {
+ // 1. Constant Value Tests (Sanity Check)
+ qt_select_const "SELECT levenshtein('kitten', 'sitting')"
+ qt_select_const "SELECT levenshtein('hello', 'hello')"
+ qt_select_const "SELECT levenshtein('abc', '')"
+ qt_select_const "SELECT levenshtein('', 'def')"
+ // UTF-8 fix check: '中国' (2 chars) vs '中' (1 char) -> Distance 1
+ qt_select_const "SELECT levenshtein('中国', '中')"
+ // UTF-8 fix check: '测试' (2 chars) vs '测验' (2 chars) -> Distance 1
+ qt_select_const "SELECT levenshtein('测试', '测验')"
+ qt_select_const "SELECT levenshtein(NULL, 'abc')"
+
+ // 2. Prepare Table Data for Column Tests
+ def tableName = "test_levenshtein_tbl"
+ sql "DROP TABLE IF EXISTS ${tableName}"
+ sql """
+ CREATE TABLE ${tableName} (
+ `id` int,
+ `s1` string,
+ `s2` string
+ ) DISTRIBUTED BY HASH(id) BUCKETS 1
+ PROPERTIES (
+ "replication_num" = "1"
+ )
+ """
+
+ // Insert data covering boundary and UTF-8 cases
+ sql """
+ INSERT INTO ${tableName} VALUES
+ (1, 'kitten', 'sitting'),
+ (2, 'rosettacode', 'raisethysword'),
+ (3, 'abc', 'abc'),
+ (4, '', 'abc'),
+ (5, 'abc', ''),
+ (6, '中国', '中'),
+ (7, '测试', '测验'),
+ (8, NULL, 'abc'),
+ (9, 'abc', NULL)
+ """
+
+ // 3. Column vs Column Test
+ qt_select_col_col "SELECT id, levenshtein(s1, s2) FROM ${tableName} ORDER BY id"
Review Comment:
？
##########
be/src/vec/functions/function_string.h:
##########
@@ -5261,6 +5261,96 @@ class FunctionCrc32Internal : public IFunction {
}
};
+class NameLevenshtein {
+public:
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinImpl {
+ static constexpr auto name = "levenshtein";
+
+ // 必需的类型定义
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = ColumnInt32::Container;
+
+ static DataTypePtr get_return_type_impl(const DataTypes& arguments) {
+ return std::make_shared<ResultDataType>();
+ }
+
+ // Helper: Get UTF-8 byte length
+ static size_t get_utf8_byte_length(unsigned char byte) {
+ if (byte < 0x80) return 1;
+ if ((byte & 0xE0) == 0xC0) return 2;
+ if ((byte & 0xF0) == 0xE0) return 3;
+ if ((byte & 0xF8) == 0xF0) return 4;
+ return 1;
+ }
+
+ // Helper: Convert UTF-8 byte stream to Unicode code points
+ static void to_utf32(const char* data, size_t size, std::vector<int32_t>& out) {
+ out.clear();
+ size_t i = 0;
+ while (i < size) {
+ size_t char_len = get_utf8_byte_length(static_cast<unsigned char>(data[i]));
+ if (i + char_len > size) char_len = 1;
+
+ int32_t code_point = 0;
+ for (size_t j = 0; j < char_len; ++j) {
+ code_point = (code_point << 8) | static_cast<unsigned char>(data[i + j]);
+ }
+ out.push_back(code_point);
+ i += char_len;
+ }
+ }
+
+ // 核心执行函数: 修正参数类型为 std::string_view
+ static void execute(std::string_view l, std::string_view r, int32_t& res) {
+ // Use thread_local for memory reuse
+ static thread_local std::vector<int32_t> a_code_points;
+ static thread_local std::vector<int32_t> b_code_points;
+
+ // ADMIN REQUIREMENT: Renaming or adding clear comments for these two DP arrays
Review Comment:
?
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] Feat levenshtein final [doris]
Posted by "kzh1458003655-web (via GitHub)" <gi...@apache.org>.
kzh1458003655-web commented on code in PR #59016:
URL: https://github.com/apache/doris/pull/59016#discussion_r2617779084
##########
be/src/vec/functions/function_string.h:
##########
@@ -5261,6 +5261,96 @@ class FunctionCrc32Internal : public IFunction {
}
};
+class NameLevenshtein {
+public:
+ static constexpr auto name = "levenshtein";
+};
+
+struct LevenshteinImpl {
+ static constexpr auto name = "levenshtein";
+
+ // 必需的类型定义
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = ColumnInt32::Container;
+
+ static DataTypePtr get_return_type_impl(const DataTypes& arguments) {
+ return std::make_shared<ResultDataType>();
+ }
+
+ // Helper: Get UTF-8 byte length
+ static size_t get_utf8_byte_length(unsigned char byte) {
+ if (byte < 0x80) return 1;
+ if ((byte & 0xE0) == 0xC0) return 2;
+ if ((byte & 0xF0) == 0xE0) return 3;
+ if ((byte & 0xF8) == 0xF0) return 4;
+ return 1;
+ }
+
+ // Helper: Convert UTF-8 byte stream to Unicode code points
+ static void to_utf32(const char* data, size_t size, std::vector<int32_t>& out) {
+ out.clear();
+ size_t i = 0;
+ while (i < size) {
+ size_t char_len = get_utf8_byte_length(static_cast<unsigned char>(data[i]));
+ if (i + char_len > size) char_len = 1;
+
+ int32_t code_point = 0;
+ for (size_t j = 0; j < char_len; ++j) {
+ code_point = (code_point << 8) | static_cast<unsigned char>(data[i + j]);
+ }
+ out.push_back(code_point);
+ i += char_len;
+ }
+ }
+
+ // 核心执行函数: 修正参数类型为 std::string_view
+ static void execute(std::string_view l, std::string_view r, int32_t& res) {
+ // Use thread_local for memory reuse
+ static thread_local std::vector<int32_t> a_code_points;
+ static thread_local std::vector<int32_t> b_code_points;
+
+ // ADMIN REQUIREMENT: Renaming or adding clear comments for these two DP arrays
+ static thread_local std::vector<int32_t> prev_row; // Previous row distances (i-1)
Review Comment:
> 为什么要这么做`static thread_local`？这是错误的。
im sorry.i want to reuse the vector , reducing repeated heap allocation
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] Feat levenshtein final [doris]
Posted by "zclllyybb (via GitHub)" <gi...@apache.org>.
zclllyybb closed pull request #59016: Feat levenshtein final
URL: https://github.com/apache/doris/pull/59016
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] Feat levenshtein final [doris]
Posted by "Thearas (via GitHub)" <gi...@apache.org>.
Thearas commented on PR #59016:
URL: https://github.com/apache/doris/pull/59016#issuecomment-3649508298
Thank you for your contribution to Apache Doris.
Don't know what should be done next? See [How to process your PR](https://cwiki.apache.org/confluence/display/DORIS/How+to+process+your+PR).
Please clearly describe your PR:
1. What problem was fixed (it's best to include specific error reporting information). How it was fixed.
2. Which behaviors were modified. What was the previous behavior, what is it now, why was it modified, and what possible impacts might there be.
3. What features were added. Why was this function added?
4. Which code was refactored and why was this part of the code refactored?
5. Which functions were optimized and what is the difference before and after the optimization?
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] Feat levenshtein final [doris]
Posted by "zclllyybb (via GitHub)" <gi...@apache.org>.
zclllyybb commented on code in PR #59016:
URL: https://github.com/apache/doris/pull/59016#discussion_r2623621903
##########
be/src/vec/functions/function_string.cpp:
##########
@@ -1446,6 +1447,7 @@ void register_function_string(SimpleFunctionFactory& factory) {
factory.register_function<FunctionMakeSet>();
factory.register_function<FunctionExportSet>();
factory.register_function<FunctionUnicodeNormalize>();
+ factory.register_function<FunctionStringLevenshtein>();
Review Comment:
duplicated
##########
be/src/vec/functions/function_string.h:
##########
@@ -5401,8 +5402,137 @@ class FunctionUnicodeNormalize : public IFunction {
output.clear();
result16.toUTF8String(output);
+=======
+// Implementation of Levenshtein algorithm
+struct LevenshteinImpl {
+ static constexpr auto name = "levenshtein";
+
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = ColumnInt32::Container;
+
+ static DataTypePtr get_return_type_impl(const DataTypes& arguments) {
+ return std::make_shared<ResultDataType>();
+ }
+
+ // Get UTF-8 byte length
+ static size_t get_utf8_byte_length(unsigned char byte) {
+ if (byte < 0x80) return 1;
+ if ((byte & 0xE0) == 0xC0) return 2;
+ if ((byte & 0xF0) == 0xE0) return 3;
+ if ((byte & 0xF8) == 0xF0) return 4;
+ return 1;
+ }
+
+ // Convert string to UTF-8 code points
+ static void to_utf32(const char* data, size_t size, std::vector<int32_t>& out) {
+ out.clear();
+ size_t i = 0;
+ while (i < size) {
+ size_t char_len = get_utf8_byte_length(static_cast<unsigned char>(data[i]));
+ if (i + char_len > size) {
+ char_len = 1;
+ }
+
+ int32_t code_point = 0;
+ for (size_t j = 0; j < char_len; ++j) {
+ code_point = (code_point << 8) | static_cast<unsigned char>(data[i + j]);
+ }
+ out.push_back(code_point);
+ i += char_len;
+ }
+ }
+
+ static void execute(std::string_view l, std::string_view r, int32_t& res) {
+ // Optimization for empty strings
+ if (UNLIKELY(l.empty())) {
+ // Need to count chars in r, not bytes
+ std::vector<int32_t> tmp;
+ to_utf32(r.data(), r.size(), tmp);
+ res = static_cast<int32_t>(tmp.size());
+ return;
+ }
+ if (UNLIKELY(r.empty())) {
+ std::vector<int32_t> tmp;
+ to_utf32(l.data(), l.size(), tmp);
+ res = static_cast<int32_t>(tmp.size());
+ return;
+ }
+
+ std::vector<int32_t> l_code_points;
+ std::vector<int32_t> r_code_points;
+
+ l_code_points.reserve(l.size());
+ r_code_points.reserve(r.size());
+
+ to_utf32(l.data(), l.size(), l_code_points);
+ to_utf32(r.data(), r.size(), r_code_points);
+
+ const auto& source = l_code_points;
+ const auto& target = r_code_points;
+
+ size_t n = source.size();
+ size_t m = target.size();
+
+ // DP arrays: prev_dist (previous row), curr_dist (current row)
+ std::vector<int32_t> prev_dist(m + 1);
+ std::vector<int32_t> curr_dist(m + 1);
+
+ for (size_t j = 0; j <= m; ++j) {
+ prev_dist[j] = static_cast<int32_t>(j);
+ }
+
+ for (size_t i = 1; i <= n; ++i) {
+ curr_dist[0] = static_cast<int32_t>(i);
+ for (size_t j = 1; j <= m; ++j) {
+ int32_t cost = (source[i - 1] == target[j - 1]) ? 0 : 1;
+ curr_dist[j] =
+ std::min({prev_dist[j] + 1, curr_dist[j - 1] + 1, prev_dist[j - 1] + cost});
+ }
+ prev_dist.swap(curr_dist);
+ }
+
+ res = prev_dist[m];
+>>>>>>> f5b07c9f4e (feat(vec): implement string function levenshtein with UTF-8 support)
}
};
+class FunctionStringLevenshtein : public IFunction {
+public:
+ static constexpr auto name = "levenshtein";
+ static FunctionPtr create() { return std::make_shared<FunctionStringLevenshtein>(); }
+ String get_name() const override { return name; }
+ size_t get_number_of_arguments() const override { return 2; }
+ DataTypePtr get_return_type_impl(const DataTypes& arguments) const override {
+ return std::make_shared<DataTypeInt32>();
+ }
+ bool use_default_implementation_for_nulls() const override { return true; }
+
+ Status execute_impl(FunctionContext* context, Block& block, const ColumnNumbers& arguments,
+ uint32_t result, size_t input_rows_count) const override {
+ auto col_left =
+ block.get_by_position(arguments[0]).column->convert_to_full_column_if_const();
+ auto col_right =
+ block.get_by_position(arguments[1]).column->convert_to_full_column_if_const();
+
+ const auto* col_left_str = check_and_get_column<ColumnString>(col_left.get());
+ const auto* col_right_str = check_and_get_column<ColumnString>(col_right.get());
+
+ if (!col_left_str || !col_right_str) {
+ return Status::InternalError("Levenshtein arguments must be String");
+ }
+
+ auto col_res = ColumnInt32::create(input_rows_count);
+ auto& res_data = col_res->get_data();
+
+ for (size_t i = 0; i < input_rows_count; ++i) {
+ auto l_view = col_left_str->get_data_at(i).to_string_view();
Review Comment:
why need convert to `string_view`? seems keep `StringRef` is ok
##########
be/src/vec/functions/function_string.h:
##########
@@ -5261,6 +5261,7 @@ class FunctionCrc32Internal : public IFunction {
}
};
+<<<<<<< HEAD
Review Comment:
git conflict
##########
be/src/vec/functions/function_string.h:
##########
@@ -5401,8 +5402,137 @@ class FunctionUnicodeNormalize : public IFunction {
output.clear();
result16.toUTF8String(output);
+=======
+// Implementation of Levenshtein algorithm
+struct LevenshteinImpl {
+ static constexpr auto name = "levenshtein";
+
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = ColumnInt32::Container;
+
+ static DataTypePtr get_return_type_impl(const DataTypes& arguments) {
+ return std::make_shared<ResultDataType>();
+ }
+
+ // Get UTF-8 byte length
+ static size_t get_utf8_byte_length(unsigned char byte) {
+ if (byte < 0x80) return 1;
+ if ((byte & 0xE0) == 0xC0) return 2;
+ if ((byte & 0xF0) == 0xE0) return 3;
+ if ((byte & 0xF8) == 0xF0) return 4;
+ return 1;
+ }
+
+ // Convert string to UTF-8 code points
+ static void to_utf32(const char* data, size_t size, std::vector<int32_t>& out) {
+ out.clear();
+ size_t i = 0;
+ while (i < size) {
+ size_t char_len = get_utf8_byte_length(static_cast<unsigned char>(data[i]));
+ if (i + char_len > size) {
+ char_len = 1;
+ }
+
+ int32_t code_point = 0;
+ for (size_t j = 0; j < char_len; ++j) {
+ code_point = (code_point << 8) | static_cast<unsigned char>(data[i + j]);
+ }
+ out.push_back(code_point);
+ i += char_len;
+ }
+ }
+
+ static void execute(std::string_view l, std::string_view r, int32_t& res) {
+ // Optimization for empty strings
+ if (UNLIKELY(l.empty())) {
+ // Need to count chars in r, not bytes
+ std::vector<int32_t> tmp;
+ to_utf32(r.data(), r.size(), tmp);
+ res = static_cast<int32_t>(tmp.size());
+ return;
+ }
+ if (UNLIKELY(r.empty())) {
+ std::vector<int32_t> tmp;
+ to_utf32(l.data(), l.size(), tmp);
+ res = static_cast<int32_t>(tmp.size());
+ return;
+ }
+
+ std::vector<int32_t> l_code_points;
+ std::vector<int32_t> r_code_points;
+
+ l_code_points.reserve(l.size());
+ r_code_points.reserve(r.size());
+
+ to_utf32(l.data(), l.size(), l_code_points);
+ to_utf32(r.data(), r.size(), r_code_points);
+
+ const auto& source = l_code_points;
+ const auto& target = r_code_points;
+
+ size_t n = source.size();
Review Comment:
make their name more meaningful
##########
be/src/vec/functions/function_string.h:
##########
@@ -5401,8 +5402,137 @@ class FunctionUnicodeNormalize : public IFunction {
output.clear();
result16.toUTF8String(output);
+=======
+// Implementation of Levenshtein algorithm
+struct LevenshteinImpl {
+ static constexpr auto name = "levenshtein";
+
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = ColumnInt32::Container;
+
+ static DataTypePtr get_return_type_impl(const DataTypes& arguments) {
+ return std::make_shared<ResultDataType>();
+ }
+
+ // Get UTF-8 byte length
+ static size_t get_utf8_byte_length(unsigned char byte) {
+ if (byte < 0x80) return 1;
+ if ((byte & 0xE0) == 0xC0) return 2;
+ if ((byte & 0xF0) == 0xE0) return 3;
+ if ((byte & 0xF8) == 0xF0) return 4;
+ return 1;
+ }
+
+ // Convert string to UTF-8 code points
+ static void to_utf32(const char* data, size_t size, std::vector<int32_t>& out) {
+ out.clear();
+ size_t i = 0;
+ while (i < size) {
+ size_t char_len = get_utf8_byte_length(static_cast<unsigned char>(data[i]));
+ if (i + char_len > size) {
+ char_len = 1;
+ }
+
+ int32_t code_point = 0;
+ for (size_t j = 0; j < char_len; ++j) {
+ code_point = (code_point << 8) | static_cast<unsigned char>(data[i + j]);
+ }
+ out.push_back(code_point);
+ i += char_len;
+ }
+ }
+
+ static void execute(std::string_view l, std::string_view r, int32_t& res) {
+ // Optimization for empty strings
+ if (UNLIKELY(l.empty())) {
+ // Need to count chars in r, not bytes
+ std::vector<int32_t> tmp;
+ to_utf32(r.data(), r.size(), tmp);
+ res = static_cast<int32_t>(tmp.size());
+ return;
+ }
+ if (UNLIKELY(r.empty())) {
+ std::vector<int32_t> tmp;
+ to_utf32(l.data(), l.size(), tmp);
+ res = static_cast<int32_t>(tmp.size());
+ return;
+ }
+
+ std::vector<int32_t> l_code_points;
+ std::vector<int32_t> r_code_points;
+
+ l_code_points.reserve(l.size());
+ r_code_points.reserve(r.size());
+
+ to_utf32(l.data(), l.size(), l_code_points);
+ to_utf32(r.data(), r.size(), r_code_points);
+
+ const auto& source = l_code_points;
+ const auto& target = r_code_points;
+
+ size_t n = source.size();
+ size_t m = target.size();
+
+ // DP arrays: prev_dist (previous row), curr_dist (current row)
+ std::vector<int32_t> prev_dist(m + 1);
+ std::vector<int32_t> curr_dist(m + 1);
+
+ for (size_t j = 0; j <= m; ++j) {
+ prev_dist[j] = static_cast<int32_t>(j);
+ }
+
+ for (size_t i = 1; i <= n; ++i) {
+ curr_dist[0] = static_cast<int32_t>(i);
+ for (size_t j = 1; j <= m; ++j) {
+ int32_t cost = (source[i - 1] == target[j - 1]) ? 0 : 1;
+ curr_dist[j] =
+ std::min({prev_dist[j] + 1, curr_dist[j - 1] + 1, prev_dist[j - 1] + cost});
+ }
+ prev_dist.swap(curr_dist);
+ }
+
+ res = prev_dist[m];
+>>>>>>> f5b07c9f4e (feat(vec): implement string function levenshtein with UTF-8 support)
}
};
+class FunctionStringLevenshtein : public IFunction {
+public:
+ static constexpr auto name = "levenshtein";
+ static FunctionPtr create() { return std::make_shared<FunctionStringLevenshtein>(); }
+ String get_name() const override { return name; }
+ size_t get_number_of_arguments() const override { return 2; }
+ DataTypePtr get_return_type_impl(const DataTypes& arguments) const override {
+ return std::make_shared<DataTypeInt32>();
+ }
+ bool use_default_implementation_for_nulls() const override { return true; }
+
+ Status execute_impl(FunctionContext* context, Block& block, const ColumnNumbers& arguments,
+ uint32_t result, size_t input_rows_count) const override {
+ auto col_left =
+ block.get_by_position(arguments[0]).column->convert_to_full_column_if_const();
+ auto col_right =
+ block.get_by_position(arguments[1]).column->convert_to_full_column_if_const();
+
+ const auto* col_left_str = check_and_get_column<ColumnString>(col_left.get());
+ const auto* col_right_str = check_and_get_column<ColumnString>(col_right.get());
+
+ if (!col_left_str || !col_right_str) {
+ return Status::InternalError("Levenshtein arguments must be String");
+ }
+
+ auto col_res = ColumnInt32::create(input_rows_count);
+ auto& res_data = col_res->get_data();
+
+ for (size_t i = 0; i < input_rows_count; ++i) {
+ auto l_view = col_left_str->get_data_at(i).to_string_view();
+ auto r_view = col_right_str->get_data_at(i).to_string_view();
+ LevenshteinImpl::execute(l_view, r_view, res_data[i]);
Review Comment:
`FunctionStringLevenshtein` could totally be replaced by other existing base template. or, if you insist to write all by yourself, it's also ok. but then don't need to split to `LevenshteinImpl`. just make `execute` a member function.
##########
be/src/vec/functions/function_string.h:
##########
@@ -5401,8 +5402,137 @@ class FunctionUnicodeNormalize : public IFunction {
output.clear();
result16.toUTF8String(output);
+=======
+// Implementation of Levenshtein algorithm
+struct LevenshteinImpl {
+ static constexpr auto name = "levenshtein";
+
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = ColumnInt32::Container;
+
+ static DataTypePtr get_return_type_impl(const DataTypes& arguments) {
+ return std::make_shared<ResultDataType>();
+ }
+
+ // Get UTF-8 byte length
+ static size_t get_utf8_byte_length(unsigned char byte) {
+ if (byte < 0x80) return 1;
+ if ((byte & 0xE0) == 0xC0) return 2;
+ if ((byte & 0xF0) == 0xE0) return 3;
+ if ((byte & 0xF8) == 0xF0) return 4;
+ return 1;
+ }
+
+ // Convert string to UTF-8 code points
+ static void to_utf32(const char* data, size_t size, std::vector<int32_t>& out) {
+ out.clear();
+ size_t i = 0;
+ while (i < size) {
+ size_t char_len = get_utf8_byte_length(static_cast<unsigned char>(data[i]));
+ if (i + char_len > size) {
+ char_len = 1;
+ }
+
+ int32_t code_point = 0;
+ for (size_t j = 0; j < char_len; ++j) {
+ code_point = (code_point << 8) | static_cast<unsigned char>(data[i + j]);
+ }
+ out.push_back(code_point);
+ i += char_len;
+ }
+ }
+
+ static void execute(std::string_view l, std::string_view r, int32_t& res) {
+ // Optimization for empty strings
+ if (UNLIKELY(l.empty())) {
+ // Need to count chars in r, not bytes
+ std::vector<int32_t> tmp;
+ to_utf32(r.data(), r.size(), tmp);
+ res = static_cast<int32_t>(tmp.size());
+ return;
+ }
+ if (UNLIKELY(r.empty())) {
+ std::vector<int32_t> tmp;
+ to_utf32(l.data(), l.size(), tmp);
Review Comment:
1. directly convert to utf8 will lead to performance loss. check it firstly.
2. your implementation seems weird.
look `SubReplaceImpl` and learn how to process it.
##########
be/src/vec/functions/function_string.h:
##########
@@ -5401,8 +5402,137 @@ class FunctionUnicodeNormalize : public IFunction {
output.clear();
result16.toUTF8String(output);
+=======
+// Implementation of Levenshtein algorithm
+struct LevenshteinImpl {
+ static constexpr auto name = "levenshtein";
+
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = ColumnInt32::Container;
+
+ static DataTypePtr get_return_type_impl(const DataTypes& arguments) {
+ return std::make_shared<ResultDataType>();
+ }
+
+ // Get UTF-8 byte length
+ static size_t get_utf8_byte_length(unsigned char byte) {
+ if (byte < 0x80) return 1;
+ if ((byte & 0xE0) == 0xC0) return 2;
+ if ((byte & 0xF0) == 0xE0) return 3;
+ if ((byte & 0xF8) == 0xF0) return 4;
+ return 1;
+ }
+
+ // Convert string to UTF-8 code points
+ static void to_utf32(const char* data, size_t size, std::vector<int32_t>& out) {
+ out.clear();
+ size_t i = 0;
+ while (i < size) {
+ size_t char_len = get_utf8_byte_length(static_cast<unsigned char>(data[i]));
+ if (i + char_len > size) {
+ char_len = 1;
+ }
+
+ int32_t code_point = 0;
+ for (size_t j = 0; j < char_len; ++j) {
+ code_point = (code_point << 8) | static_cast<unsigned char>(data[i + j]);
+ }
+ out.push_back(code_point);
+ i += char_len;
+ }
+ }
+
+ static void execute(std::string_view l, std::string_view r, int32_t& res) {
+ // Optimization for empty strings
+ if (UNLIKELY(l.empty())) {
+ // Need to count chars in r, not bytes
+ std::vector<int32_t> tmp;
+ to_utf32(r.data(), r.size(), tmp);
+ res = static_cast<int32_t>(tmp.size());
+ return;
+ }
+ if (UNLIKELY(r.empty())) {
+ std::vector<int32_t> tmp;
+ to_utf32(l.data(), l.size(), tmp);
+ res = static_cast<int32_t>(tmp.size());
+ return;
+ }
+
+ std::vector<int32_t> l_code_points;
+ std::vector<int32_t> r_code_points;
+
+ l_code_points.reserve(l.size());
+ r_code_points.reserve(r.size());
+
+ to_utf32(l.data(), l.size(), l_code_points);
+ to_utf32(r.data(), r.size(), r_code_points);
+
+ const auto& source = l_code_points;
+ const auto& target = r_code_points;
+
+ size_t n = source.size();
+ size_t m = target.size();
+
+ // DP arrays: prev_dist (previous row), curr_dist (current row)
+ std::vector<int32_t> prev_dist(m + 1);
Review Comment:
use `DorisVector` to track memory alloc.
##########
be/src/vec/functions/function_string.h:
##########
@@ -5401,8 +5402,137 @@ class FunctionUnicodeNormalize : public IFunction {
output.clear();
result16.toUTF8String(output);
+=======
+// Implementation of Levenshtein algorithm
+struct LevenshteinImpl {
+ static constexpr auto name = "levenshtein";
+
+ using ResultDataType = DataTypeInt32;
+ using ResultPaddedPODArray = ColumnInt32::Container;
+
+ static DataTypePtr get_return_type_impl(const DataTypes& arguments) {
+ return std::make_shared<ResultDataType>();
+ }
+
+ // Get UTF-8 byte length
+ static size_t get_utf8_byte_length(unsigned char byte) {
+ if (byte < 0x80) return 1;
+ if ((byte & 0xE0) == 0xC0) return 2;
+ if ((byte & 0xF0) == 0xE0) return 3;
+ if ((byte & 0xF8) == 0xF0) return 4;
+ return 1;
+ }
+
+ // Convert string to UTF-8 code points
+ static void to_utf32(const char* data, size_t size, std::vector<int32_t>& out) {
+ out.clear();
+ size_t i = 0;
+ while (i < size) {
+ size_t char_len = get_utf8_byte_length(static_cast<unsigned char>(data[i]));
+ if (i + char_len > size) {
+ char_len = 1;
+ }
+
+ int32_t code_point = 0;
+ for (size_t j = 0; j < char_len; ++j) {
+ code_point = (code_point << 8) | static_cast<unsigned char>(data[i + j]);
+ }
+ out.push_back(code_point);
+ i += char_len;
+ }
+ }
+
+ static void execute(std::string_view l, std::string_view r, int32_t& res) {
+ // Optimization for empty strings
+ if (UNLIKELY(l.empty())) {
+ // Need to count chars in r, not bytes
+ std::vector<int32_t> tmp;
+ to_utf32(r.data(), r.size(), tmp);
+ res = static_cast<int32_t>(tmp.size());
+ return;
+ }
+ if (UNLIKELY(r.empty())) {
+ std::vector<int32_t> tmp;
+ to_utf32(l.data(), l.size(), tmp);
+ res = static_cast<int32_t>(tmp.size());
+ return;
+ }
+
+ std::vector<int32_t> l_code_points;
+ std::vector<int32_t> r_code_points;
+
+ l_code_points.reserve(l.size());
+ r_code_points.reserve(r.size());
+
+ to_utf32(l.data(), l.size(), l_code_points);
+ to_utf32(r.data(), r.size(), r_code_points);
+
+ const auto& source = l_code_points;
+ const auto& target = r_code_points;
+
+ size_t n = source.size();
+ size_t m = target.size();
+
+ // DP arrays: prev_dist (previous row), curr_dist (current row)
+ std::vector<int32_t> prev_dist(m + 1);
+ std::vector<int32_t> curr_dist(m + 1);
+
+ for (size_t j = 0; j <= m; ++j) {
+ prev_dist[j] = static_cast<int32_t>(j);
Review Comment:
we make `j` `size_t` and always cast, it seems weird. you should think clear for why and how we do cast here.
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org