be/src/exprs/function/function_levenshtein.cpp

Source
// 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 <algorithm>
#include <array>
#include <limits>
#include <string_view>
#include <unordered_map>
#include <vector>

#include "common/status.h"
#include "core/custom_allocator.h"
#include "core/data_type/data_type_number.h"
#include "core/pod_array.h"
#include "core/string_ref.h"
#include "exprs/function/function_totype.h"
#include "exprs/function/simple_function_factory.h"
#include "util/simd/vstring_function.h"

namespace doris {

struct NameLevenshtein {
    static constexpr auto name = "levenshtein";
};

struct NameDamerauLevenshteinDistance {
    static constexpr auto name = "damerau_levenshtein_distance";
};

// 64MB limit for the distance matrix.
static constexpr size_t MAX_DAMERAU_LEVENSHTEIN_MATRIX_CELLS = 16 * 1024 * 1024;

using Utf8Offsets = DorisVector<size_t>;

static StringRef string_ref_at(const ColumnString::Chars& data,
                               const ColumnString::Offsets& offsets, size_t i) {
    DCHECK_LT(i, offsets.size());
    const auto previous_offset = i == 0 ? 0 : offsets[i - 1];
    return StringRef(data.data() + previous_offset, offsets[i] - previous_offset);
}

static void get_utf8_char_offsets(const StringRef& ref, Utf8Offsets& offsets) {
    offsets.clear();
    offsets.reserve(ref.size);
    for (size_t i = 0, char_size = 0; i < ref.size; i += char_size) {
        char_size = UTF8_BYTE_LENGTH[static_cast<unsigned char>(ref.data[i])];
        offsets.push_back(i);
    }
}

struct LevenshteinDistance {
    static Status ascii(const StringRef& left, const StringRef& right, Int32& result) {
        const StringRef* left_ref = &left;
        const StringRef* right_ref = &right;
        size_t m = left.size;
        size_t n = right.size;

        if (n > m) {
            std::swap(left_ref, right_ref);
            std::swap(m, n);
        }

        std::vector<Int32> prev(n + 1);
        std::vector<Int32> curr(n + 1);
        for (size_t j = 0; j <= n; ++j) {
            prev[j] = static_cast<Int32>(j);
        }

        for (size_t i = 1; i <= m; ++i) {
            curr[0] = static_cast<Int32>(i);
            const char left_char = left_ref->data[i - 1];

            for (size_t j = 1; j <= n; ++j) {
                const Int32 cost = left_char == right_ref->data[j - 1] ? 0 : 1;
                const Int32 insert_cost = curr[j - 1] + 1;
                const Int32 delete_cost = prev[j] + 1;
                const Int32 replace_cost = prev[j - 1] + cost;
                curr[j] = std::min(std::min(insert_cost, delete_cost), replace_cost);
            }
            std::swap(prev, curr);
        }

        result = prev[n];
        return Status::OK();
    }

    static Status utf8(const StringRef& left, const Utf8Offsets& left_offsets,
                       const StringRef& right, const Utf8Offsets& right_offsets, Int32& result) {
        const StringRef* left_ref = &left;
        const StringRef* right_ref = &right;
        const Utf8Offsets* left_offsets_ref = &left_offsets;
        const Utf8Offsets* right_offsets_ref = &right_offsets;
        if (right_offsets_ref->size() > left_offsets_ref->size()) {
            std::swap(left_offsets_ref, right_offsets_ref);
            std::swap(left_ref, right_ref);
        }

        const size_t m = left_offsets_ref->size();
        const size_t n = right_offsets_ref->size();

        std::vector<Int32> prev(n + 1);
        std::vector<Int32> curr(n + 1);
        for (size_t j = 0; j <= n; ++j) {
            prev[j] = static_cast<Int32>(j);
        }

        for (size_t i = 1; i <= m; ++i) {
            curr[0] = static_cast<Int32>(i);
            const size_t left_off = (*left_offsets_ref)[i - 1];
            const size_t left_next = i < m ? (*left_offsets_ref)[i] : left_ref->size;

            for (size_t j = 1; j <= n; ++j) {
                const size_t right_off = (*right_offsets_ref)[j - 1];
                const size_t right_next = j < n ? (*right_offsets_ref)[j] : right_ref->size;

                const Int32 cost =
                        simd::VStringFunctions::utf8_char_equal(*left_ref, left_off, left_next,
                                                                *right_ref, right_off, right_next)
                                ? 0
                                : 1;

                const Int32 insert_cost = curr[j - 1] + 1;
                const Int32 delete_cost = prev[j] + 1;
                const Int32 replace_cost = prev[j - 1] + cost;
                curr[j] = std::min(std::min(insert_cost, delete_cost), replace_cost);
            }
            std::swap(prev, curr);
        }

        result = prev[n];
        return Status::OK();
    }
};

struct DamerauLevenshteinDistance {
    using SymbolId = Int32;
    using SymbolVector = DorisVector<SymbolId>;
    using SymbolMap =
            std::unordered_map<std::string_view, SymbolId, std::hash<std::string_view>,
                               std::equal_to<std::string_view>,
                               CustomStdAllocator<std::pair<const std::string_view, SymbolId>>>;

    // Do not use absl::strings_internal::CappedDamerauLevenshteinDistance here:
    // 1. It is capped: distances greater than cutoff return cutoff + 1, not exact distance.
    // 2. It returns uint8_t and is intended for short strings.
    // 3. It implements the restricted/OSA variant, not full Damerau-Levenshtein.
    // 4. It works on bytes, cannot handle UTF-8 characters.
    static Status ascii(const StringRef& left, const StringRef& right, Int32& result) {
        const size_t m = left.size;
        const size_t n = right.size;
        if (m == 0) {
            result = static_cast<Int32>(n);
            return Status::OK();
        }
        if (n == 0) {
            result = static_cast<Int32>(m);
            return Status::OK();
        }

        size_t matrix_cells = 0;
        RETURN_IF_ERROR(get_matrix_cell_count(m, n, matrix_cells));

        const Int32 max_distance = static_cast<Int32>(m + n);
        std::array<Int32, 256> last_row {};
        PaddedPODArray<Int32> dist;
        dist.resize_fill(matrix_cells, 0);
        auto at = [&](size_t i, size_t j) -> Int32& { return dist[i * (n + 2) + j]; };

        at(0, 0) = max_distance;
        for (size_t i = 0; i <= m; ++i) {
            at(i + 1, 0) = max_distance;
            at(i + 1, 1) = static_cast<Int32>(i);
        }
        for (size_t j = 0; j <= n; ++j) {
            at(0, j + 1) = max_distance;
            at(1, j + 1) = static_cast<Int32>(j);
        }

        for (size_t i = 1; i <= m; ++i) {
            Int32 last_match_col = 0;
            const auto left_symbol = static_cast<unsigned char>(left.data[i - 1]);
            for (size_t j = 1; j <= n; ++j) {
                const auto right_symbol = static_cast<unsigned char>(right.data[j - 1]);
                const Int32 last_match_row = last_row[right_symbol];
                const Int32 transposition_col = last_match_col;
                Int32 cost = 1;
                if (left_symbol == right_symbol) {
                    cost = 0;
                    last_match_col = static_cast<Int32>(j);
                }

                const Int32 replace_cost = at(i, j) + cost;
                const Int32 insert_cost = at(i + 1, j) + 1;
                const Int32 delete_cost = at(i, j + 1) + 1;
                const Int32 transpose_cost = at(last_match_row, transposition_col) +
                                             static_cast<Int32>(i - last_match_row - 1) + 1 +
                                             static_cast<Int32>(j - transposition_col - 1);
                at(i + 1, j + 1) = std::min(std::min(replace_cost, insert_cost),
                                            std::min(delete_cost, transpose_cost));
            }
            last_row[left_symbol] = static_cast<Int32>(i);
        }

        result = at(m + 1, n + 1);
        return Status::OK();
    }

    /*
    * Keep the UTF-8 symbol mapping path. The benchmark below shows that mapping each UTF-8
    * character to an integer symbol first is faster than comparing UTF-8 slices inside the
    * dp loop, because the hot loop only needs integer equality and indexed last-row lookup.
    *
    * --------------------------------------------------------------------------
    * Benchmark                                             Time             CPU
    * --------------------------------------------------------------------------
    * BM_DamerauLevenshtein_UTF8/SymbolMapped_16         1.85 us         1.82 us
    * BM_DamerauLevenshtein_UTF8/DirectCompare_16        6.48 us         6.43 us
    * BM_DamerauLevenshtein_UTF8/SymbolMapped_64         12.6 us         12.6 us
    * BM_DamerauLevenshtein_UTF8/DirectCompare_64         119 us          118 us
    * BM_DamerauLevenshtein_UTF8/SymbolMapped_128        43.4 us         43.1 us
    * BM_DamerauLevenshtein_UTF8/DirectCompare_128        478 us          475 us
    * BM_DamerauLevenshtein_UTF8/SymbolMapped_256         160 us          159 us
    * BM_DamerauLevenshtein_UTF8/DirectCompare_256       1892 us         1882 us
    */
    static Status utf8(const StringRef& left, const Utf8Offsets& left_offsets,
                       const StringRef& right, const Utf8Offsets& right_offsets, Int32& result) {
        SymbolVector left_symbols;
        SymbolVector right_symbols;
        SymbolMap symbol_ids;
        symbol_ids.reserve(left_offsets.size() + right_offsets.size());
        SymbolId next_symbol = 0;
        append_utf8_symbols(left, left_offsets, left_symbols, symbol_ids, next_symbol);
        append_utf8_symbols(right, right_offsets, right_symbols, symbol_ids, next_symbol);
        return by_symbols(left_symbols, right_symbols, next_symbol, result);
    }

private:
    static Status by_symbols(const SymbolVector& left, const SymbolVector& right,
                             size_t alphabet_size, Int32& result) {
        const size_t m = left.size();
        const size_t n = right.size();
        if (m == 0) {
            result = static_cast<Int32>(n);
            return Status::OK();
        }
        if (n == 0) {
            result = static_cast<Int32>(m);
            return Status::OK();
        }

        size_t matrix_cells = 0;
        RETURN_IF_ERROR(get_matrix_cell_count(m, n, matrix_cells));

        const Int32 max_distance = static_cast<Int32>(m + n);
        DorisVector<Int32> last_row(alphabet_size, 0);
        PaddedPODArray<Int32> dist;
        dist.resize_fill(matrix_cells, 0);
        auto at = [&](size_t i, size_t j) -> Int32& { return dist[i * (n + 2) + j]; };

        at(0, 0) = max_distance;
        for (size_t i = 0; i <= m; ++i) {
            at(i + 1, 0) = max_distance;
            at(i + 1, 1) = static_cast<Int32>(i);
        }
        for (size_t j = 0; j <= n; ++j) {
            at(0, j + 1) = max_distance;
            at(1, j + 1) = static_cast<Int32>(j);
        }

        for (size_t i = 1; i <= m; ++i) {
            Int32 last_match_col = 0;
            for (size_t j = 1; j <= n; ++j) {
                const Int32 last_match_row = last_row[right[j - 1]];
                const Int32 transposition_col = last_match_col;
                Int32 cost = 1;
                if (left[i - 1] == right[j - 1]) {
                    cost = 0;
                    last_match_col = static_cast<Int32>(j);
                }

                const Int32 replace_cost = at(i, j) + cost;
                const Int32 insert_cost = at(i + 1, j) + 1;
                const Int32 delete_cost = at(i, j + 1) + 1;
                const Int32 transpose_cost = at(last_match_row, transposition_col) +
                                             static_cast<Int32>(i - last_match_row - 1) + 1 +
                                             static_cast<Int32>(j - transposition_col - 1);
                at(i + 1, j + 1) = std::min(std::min(replace_cost, insert_cost),
                                            std::min(delete_cost, transpose_cost));
            }
            last_row[left[i - 1]] = static_cast<Int32>(i);
        }

        result = at(m + 1, n + 1);
        return Status::OK();
    }

    static Status get_matrix_cell_count(size_t m, size_t n, size_t& matrix_cells) {
        const auto max_size = std::numeric_limits<size_t>::max();
        if (m > max_size - 2 || n > max_size - 2) {
            return Status::InvalidArgument(
                    "damerau_levenshtein_distance input is too large to allocate distance matrix");
        }

        const size_t rows = m + 2;
        const size_t cols = n + 2;
        if (rows > max_size / cols) {
            return Status::InvalidArgument(
                    "damerau_levenshtein_distance distance matrix size overflows");
        }

        matrix_cells = rows * cols;
        if (matrix_cells > MAX_DAMERAU_LEVENSHTEIN_MATRIX_CELLS) {
            return Status::InvalidArgument(
                    "damerau_levenshtein_distance distance matrix is too large: {} cells exceeds "
                    "limit {}",
                    matrix_cells, MAX_DAMERAU_LEVENSHTEIN_MATRIX_CELLS);
        }
        return Status::OK();
    }

    static void append_utf8_symbols(const StringRef& str, const Utf8Offsets& offsets,
                                    SymbolVector& symbols, SymbolMap& symbol_ids,
                                    SymbolId& next_symbol) {
        symbols.reserve(symbols.size() + offsets.size());
        for (size_t i = 0; i < offsets.size(); ++i) {
            const size_t offset = offsets[i];
            const size_t next_offset = i + 1 < offsets.size() ? offsets[i + 1] : str.size;
            const std::string_view symbol(str.data + offset, next_offset - offset);
            auto [it, inserted] = symbol_ids.emplace(symbol, next_symbol);
            if (inserted) {
                ++next_symbol;
            }
            symbols.push_back(it->second);
        }
    }
};

template <typename Distance>
struct StringDistanceImplBase {
    using ResultDataType = DataTypeInt32;
    using ResultPaddedPODArray = PaddedPODArray<Int32>;

    static Status vector_vector(const ColumnString::Chars& ldata,
                                const ColumnString::Offsets& loffsets,
                                const ColumnString::Chars& rdata,
                                const ColumnString::Offsets& roffsets, ResultPaddedPODArray& res) {
        DCHECK_EQ(loffsets.size(), roffsets.size());

        const size_t size = loffsets.size();
        res.resize(size);
        Utf8Offsets left_offsets;
        Utf8Offsets right_offsets;
        for (size_t i = 0; i < size; ++i) {
            RETURN_IF_ERROR(distance(string_ref_at(ldata, loffsets, i),
                                     string_ref_at(rdata, roffsets, i), left_offsets, right_offsets,
                                     res[i]));
        }
        return Status::OK();
    }

    static Status vector_scalar(const ColumnString::Chars& data,
                                const ColumnString::Offsets& offsets, const StringRef& constant,
                                ResultPaddedPODArray& res) {
        return vector_const(data, offsets, constant, res);
    }

    static Status scalar_vector(const StringRef& constant, const ColumnString::Chars& data,
                                const ColumnString::Offsets& offsets, ResultPaddedPODArray& res) {
        return vector_const(data, offsets, constant, res);
    }

private:
    static Status vector_const(const ColumnString::Chars& data,
                               const ColumnString::Offsets& offsets, const StringRef& constant,
                               ResultPaddedPODArray& res) {
        const size_t size = offsets.size();
        res.resize(size);
        const bool constant_ascii = simd::VStringFunctions::is_ascii(constant);
        Utf8Offsets constant_offsets;
        get_utf8_char_offsets(constant, constant_offsets);
        Utf8Offsets value_offsets;
        for (size_t i = 0; i < size; ++i) {
            RETURN_IF_ERROR(distance_with_const_offsets(string_ref_at(data, offsets, i),
                                                        value_offsets, constant, constant_offsets,
                                                        constant_ascii, res[i]));
        }
        return Status::OK();
    }

    static Status distance(const StringRef& left, const StringRef& right, Utf8Offsets& left_offsets,
                           Utf8Offsets& right_offsets, Int32& result) {
        const bool left_ascii = simd::VStringFunctions::is_ascii(left);
        const bool right_ascii = simd::VStringFunctions::is_ascii(right);
        if (left_ascii && right_ascii) {
            return Distance::ascii(left, right, result);
        }

        if (left.size == 0) {
            result = static_cast<Int32>(
                    simd::VStringFunctions::get_char_len(right.data, right.size));
            return Status::OK();
        }
        if (right.size == 0) {
            result = static_cast<Int32>(simd::VStringFunctions::get_char_len(left.data, left.size));
            return Status::OK();
        }

        get_utf8_char_offsets(left, left_offsets);
        get_utf8_char_offsets(right, right_offsets);
        return Distance::utf8(left, left_offsets, right, right_offsets, result);
    }

    static Status distance_with_const_offsets(const StringRef& value, Utf8Offsets& value_offsets,
                                              const StringRef& constant,
                                              const Utf8Offsets& constant_offsets,
                                              bool constant_ascii, Int32& result) {
        const bool value_ascii = simd::VStringFunctions::is_ascii(value);
        if (value_ascii && constant_ascii) {
            return Distance::ascii(value, constant, result);
        }

        if (value.size == 0) {
            result = static_cast<Int32>(constant_offsets.size());
            return Status::OK();
        }
        if (constant.size == 0) {
            result = value_ascii ? static_cast<Int32>(value.size)
                                 : static_cast<Int32>(simd::VStringFunctions::get_char_len(
                                           value.data, value.size));
            return Status::OK();
        }

        get_utf8_char_offsets(value, value_offsets);
        return Distance::utf8(value, value_offsets, constant, constant_offsets, result);
    }
};

template <typename LeftDataType, typename RightDataType>
struct LevenshteinImpl : public StringDistanceImplBase<LevenshteinDistance> {};

template <typename LeftDataType, typename RightDataType>
struct DamerauLevenshteinDistanceImpl : public StringDistanceImplBase<DamerauLevenshteinDistance> {
};

using FunctionLevenshtein =
        FunctionBinaryToType<DataTypeString, DataTypeString, LevenshteinImpl, NameLevenshtein>;
using FunctionDamerauLevenshteinDistance =
        FunctionBinaryToType<DataTypeString, DataTypeString, DamerauLevenshteinDistanceImpl,
                             NameDamerauLevenshteinDistance>;

void register_function_levenshtein(SimpleFunctionFactory& factory) {
    factory.register_function<FunctionLevenshtein>();
    factory.register_alias(FunctionLevenshtein::name, "levenshtein_distance");
    factory.register_alias(FunctionLevenshtein::name, "edit_distance");
    factory.register_function<FunctionDamerauLevenshteinDistance>();
}

} // namespace doris

Coverage Report

Created: 2026-08-07 21:30

Line	Count	Source
1		// Licensed to the Apache Software Foundation (ASF) under one
2		// or more contributor license agreements. See the NOTICE file
3		// distributed with this work for additional information
4		// regarding copyright ownership. The ASF licenses this file
5		// to you under the Apache License, Version 2.0 (the
6		// "License"); you may not use this file except in compliance
7		// with the License. You may obtain a copy of the License at
8		//
9		// http://www.apache.org/licenses/LICENSE-2.0
10		//
11		// Unless required by applicable law or agreed to in writing,
12		// software distributed under the License is distributed on an
13		// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14		// KIND, either express or implied. See the License for the
15		// specific language governing permissions and limitations
16		// under the License.
17
18		#include <algorithm>
19		#include <array>
20		#include <limits>
21		#include <string_view>
22		#include <unordered_map>
23		#include <vector>
24
25		#include "common/status.h"
26		#include "core/custom_allocator.h"
27		#include "core/data_type/data_type_number.h"
28		#include "core/pod_array.h"
29		#include "core/string_ref.h"
30		#include "exprs/function/function_totype.h"
31		#include "exprs/function/simple_function_factory.h"
32		#include "util/simd/vstring_function.h"
33
34		namespace doris {
35
36		struct NameLevenshtein {
37		static constexpr auto name = "levenshtein";
38		};
39
40		struct NameDamerauLevenshteinDistance {
41		static constexpr auto name = "damerau_levenshtein_distance";
42		};
43
44		// 64MB limit for the distance matrix.
45		static constexpr size_t MAX_DAMERAU_LEVENSHTEIN_MATRIX_CELLS = 16 * 1024 * 1024;
46
47		using Utf8Offsets = DorisVector<size_t>;
48
49		static StringRef string_ref_at(const ColumnString::Chars& data,
50	0	const ColumnString::Offsets& offsets, size_t i) {
51	0	DCHECK_LT(i, offsets.size());
52	0	const auto previous_offset = i == 0 ? 0 : offsets[i - 1];
53	0	return StringRef(data.data() + previous_offset, offsets[i] - previous_offset);
54	0	}
55
56	0	static void get_utf8_char_offsets(const StringRef& ref, Utf8Offsets& offsets) {
57	0	offsets.clear();
58	0	offsets.reserve(ref.size);
59	0	for (size_t i = 0, char_size = 0; i < ref.size; i += char_size) {
60	0	char_size = UTF8_BYTE_LENGTH[static_cast<unsigned char>(ref.data[i])];
61	0	offsets.push_back(i);
62	0	}
63	0	}
64
65		struct LevenshteinDistance {
66	0	static Status ascii(const StringRef& left, const StringRef& right, Int32& result) {
67	0	const StringRef* left_ref = &left;
68	0	const StringRef* right_ref = &right;
69	0	size_t m = left.size;
70	0	size_t n = right.size;
71
72	0	if (n > m) {
73	0	std::swap(left_ref, right_ref);
74	0	std::swap(m, n);
75	0	}
76
77	0	std::vector<Int32> prev(n + 1);
78	0	std::vector<Int32> curr(n + 1);
79	0	for (size_t j = 0; j <= n; ++j) {
80	0	prev[j] = static_cast<Int32>(j);
81	0	}
82
83	0	for (size_t i = 1; i <= m; ++i) {
84	0	curr[0] = static_cast<Int32>(i);
85	0	const char left_char = left_ref->data[i - 1];
86
87	0	for (size_t j = 1; j <= n; ++j) {
88	0	const Int32 cost = left_char == right_ref->data[j - 1] ? 0 : 1;
89	0	const Int32 insert_cost = curr[j - 1] + 1;
90	0	const Int32 delete_cost = prev[j] + 1;
91	0	const Int32 replace_cost = prev[j - 1] + cost;
92	0	curr[j] = std::min(std::min(insert_cost, delete_cost), replace_cost);
93	0	}
94	0	std::swap(prev, curr);
95	0	}
96
97	0	result = prev[n];
98	0	return Status::OK();
99	0	}
100
101		static Status utf8(const StringRef& left, const Utf8Offsets& left_offsets,
102	0	const StringRef& right, const Utf8Offsets& right_offsets, Int32& result) {
103	0	const StringRef* left_ref = &left;
104	0	const StringRef* right_ref = &right;
105	0	const Utf8Offsets* left_offsets_ref = &left_offsets;
106	0	const Utf8Offsets* right_offsets_ref = &right_offsets;
107	0	if (right_offsets_ref->size() > left_offsets_ref->size()) {
108	0	std::swap(left_offsets_ref, right_offsets_ref);
109	0	std::swap(left_ref, right_ref);
110	0	}
111
112	0	const size_t m = left_offsets_ref->size();
113	0	const size_t n = right_offsets_ref->size();
114
115	0	std::vector<Int32> prev(n + 1);
116	0	std::vector<Int32> curr(n + 1);
117	0	for (size_t j = 0; j <= n; ++j) {
118	0	prev[j] = static_cast<Int32>(j);
119	0	}
120
121	0	for (size_t i = 1; i <= m; ++i) {
122	0	curr[0] = static_cast<Int32>(i);
123	0	const size_t left_off = (*left_offsets_ref)[i - 1];
124	0	const size_t left_next = i < m ? (*left_offsets_ref)[i] : left_ref->size;
125
126	0	for (size_t j = 1; j <= n; ++j) {
127	0	const size_t right_off = (*right_offsets_ref)[j - 1];
128	0	const size_t right_next = j < n ? (*right_offsets_ref)[j] : right_ref->size;
129
130	0	const Int32 cost =
131	0	simd::VStringFunctions::utf8_char_equal(*left_ref, left_off, left_next,
132	0	*right_ref, right_off, right_next)
133	0	? 0
134	0	: 1;
135
136	0	const Int32 insert_cost = curr[j - 1] + 1;
137	0	const Int32 delete_cost = prev[j] + 1;
138	0	const Int32 replace_cost = prev[j - 1] + cost;
139	0	curr[j] = std::min(std::min(insert_cost, delete_cost), replace_cost);
140	0	}
141	0	std::swap(prev, curr);
142	0	}
143
144	0	result = prev[n];
145	0	return Status::OK();
146	0	}
147		};
148
149		struct DamerauLevenshteinDistance {
150		using SymbolId = Int32;
151		using SymbolVector = DorisVector<SymbolId>;
152		using SymbolMap =
153		std::unordered_map<std::string_view, SymbolId, std::hash<std::string_view>,
154		std::equal_to<std::string_view>,
155		CustomStdAllocator<std::pair<const std::string_view, SymbolId>>>;
156
157		// Do not use absl::strings_internal::CappedDamerauLevenshteinDistance here:
158		// 1. It is capped: distances greater than cutoff return cutoff + 1, not exact distance.
159		// 2. It returns uint8_t and is intended for short strings.
160		// 3. It implements the restricted/OSA variant, not full Damerau-Levenshtein.
161		// 4. It works on bytes, cannot handle UTF-8 characters.
162	0	static Status ascii(const StringRef& left, const StringRef& right, Int32& result) {
163	0	const size_t m = left.size;
164	0	const size_t n = right.size;
165	0	if (m == 0) {
166	0	result = static_cast<Int32>(n);
167	0	return Status::OK();
168	0	}
169	0	if (n == 0) {
170	0	result = static_cast<Int32>(m);
171	0	return Status::OK();
172	0	}
173
174	0	size_t matrix_cells = 0;
175	0	RETURN_IF_ERROR(get_matrix_cell_count(m, n, matrix_cells));
176
177	0	const Int32 max_distance = static_cast<Int32>(m + n);
178	0	std::array<Int32, 256> last_row {};
179	0	PaddedPODArray<Int32> dist;
180	0	dist.resize_fill(matrix_cells, 0);
181	0	auto at = [&](size_t i, size_t j) -> Int32& { return dist[i * (n + 2) + j]; };
182
183	0	at(0, 0) = max_distance;
184	0	for (size_t i = 0; i <= m; ++i) {
185	0	at(i + 1, 0) = max_distance;
186	0	at(i + 1, 1) = static_cast<Int32>(i);
187	0	}
188	0	for (size_t j = 0; j <= n; ++j) {
189	0	at(0, j + 1) = max_distance;
190	0	at(1, j + 1) = static_cast<Int32>(j);
191	0	}
192
193	0	for (size_t i = 1; i <= m; ++i) {
194	0	Int32 last_match_col = 0;
195	0	const auto left_symbol = static_cast<unsigned char>(left.data[i - 1]);
196	0	for (size_t j = 1; j <= n; ++j) {
197	0	const auto right_symbol = static_cast<unsigned char>(right.data[j - 1]);
198	0	const Int32 last_match_row = last_row[right_symbol];
199	0	const Int32 transposition_col = last_match_col;
200	0	Int32 cost = 1;
201	0	if (left_symbol == right_symbol) {
202	0	cost = 0;
203	0	last_match_col = static_cast<Int32>(j);
204	0	}
205
206	0	const Int32 replace_cost = at(i, j) + cost;
207	0	const Int32 insert_cost = at(i + 1, j) + 1;
208	0	const Int32 delete_cost = at(i, j + 1) + 1;
209	0	const Int32 transpose_cost = at(last_match_row, transposition_col) +
210	0	static_cast<Int32>(i - last_match_row - 1) + 1 +
211	0	static_cast<Int32>(j - transposition_col - 1);
212	0	at(i + 1, j + 1) = std::min(std::min(replace_cost, insert_cost),
213	0	std::min(delete_cost, transpose_cost));
214	0	}
215	0	last_row[left_symbol] = static_cast<Int32>(i);
216	0	}
217
218	0	result = at(m + 1, n + 1);
219	0	return Status::OK();
220	0	}
221
222		/*
223		* Keep the UTF-8 symbol mapping path. The benchmark below shows that mapping each UTF-8
224		* character to an integer symbol first is faster than comparing UTF-8 slices inside the
225		* dp loop, because the hot loop only needs integer equality and indexed last-row lookup.
226		*
227		* --------------------------------------------------------------------------
228		* Benchmark Time CPU
229		* --------------------------------------------------------------------------
230		* BM_DamerauLevenshtein_UTF8/SymbolMapped_16 1.85 us 1.82 us
231		* BM_DamerauLevenshtein_UTF8/DirectCompare_16 6.48 us 6.43 us
232		* BM_DamerauLevenshtein_UTF8/SymbolMapped_64 12.6 us 12.6 us
233		* BM_DamerauLevenshtein_UTF8/DirectCompare_64 119 us 118 us
234		* BM_DamerauLevenshtein_UTF8/SymbolMapped_128 43.4 us 43.1 us
235		* BM_DamerauLevenshtein_UTF8/DirectCompare_128 478 us 475 us
236		* BM_DamerauLevenshtein_UTF8/SymbolMapped_256 160 us 159 us
237		* BM_DamerauLevenshtein_UTF8/DirectCompare_256 1892 us 1882 us
238		*/
239		static Status utf8(const StringRef& left, const Utf8Offsets& left_offsets,
240	0	const StringRef& right, const Utf8Offsets& right_offsets, Int32& result) {
241	0	SymbolVector left_symbols;
242	0	SymbolVector right_symbols;
243	0	SymbolMap symbol_ids;
244	0	symbol_ids.reserve(left_offsets.size() + right_offsets.size());
245	0	SymbolId next_symbol = 0;
246	0	append_utf8_symbols(left, left_offsets, left_symbols, symbol_ids, next_symbol);
247	0	append_utf8_symbols(right, right_offsets, right_symbols, symbol_ids, next_symbol);
248	0	return by_symbols(left_symbols, right_symbols, next_symbol, result);
249	0	}
250
251		private:
252		static Status by_symbols(const SymbolVector& left, const SymbolVector& right,
253	0	size_t alphabet_size, Int32& result) {
254	0	const size_t m = left.size();
255	0	const size_t n = right.size();
256	0	if (m == 0) {
257	0	result = static_cast<Int32>(n);
258	0	return Status::OK();
259	0	}
260	0	if (n == 0) {
261	0	result = static_cast<Int32>(m);
262	0	return Status::OK();
263	0	}
264
265	0	size_t matrix_cells = 0;
266	0	RETURN_IF_ERROR(get_matrix_cell_count(m, n, matrix_cells));
267
268	0	const Int32 max_distance = static_cast<Int32>(m + n);
269	0	DorisVector<Int32> last_row(alphabet_size, 0);
270	0	PaddedPODArray<Int32> dist;
271	0	dist.resize_fill(matrix_cells, 0);
272	0	auto at = [&](size_t i, size_t j) -> Int32& { return dist[i * (n + 2) + j]; };
273
274	0	at(0, 0) = max_distance;
275	0	for (size_t i = 0; i <= m; ++i) {
276	0	at(i + 1, 0) = max_distance;
277	0	at(i + 1, 1) = static_cast<Int32>(i);
278	0	}
279	0	for (size_t j = 0; j <= n; ++j) {
280	0	at(0, j + 1) = max_distance;
281	0	at(1, j + 1) = static_cast<Int32>(j);
282	0	}
283
284	0	for (size_t i = 1; i <= m; ++i) {
285	0	Int32 last_match_col = 0;
286	0	for (size_t j = 1; j <= n; ++j) {
287	0	const Int32 last_match_row = last_row[right[j - 1]];
288	0	const Int32 transposition_col = last_match_col;
289	0	Int32 cost = 1;
290	0	if (left[i - 1] == right[j - 1]) {
291	0	cost = 0;
292	0	last_match_col = static_cast<Int32>(j);
293	0	}
294
295	0	const Int32 replace_cost = at(i, j) + cost;
296	0	const Int32 insert_cost = at(i + 1, j) + 1;
297	0	const Int32 delete_cost = at(i, j + 1) + 1;
298	0	const Int32 transpose_cost = at(last_match_row, transposition_col) +
299	0	static_cast<Int32>(i - last_match_row - 1) + 1 +
300	0	static_cast<Int32>(j - transposition_col - 1);
301	0	at(i + 1, j + 1) = std::min(std::min(replace_cost, insert_cost),
302	0	std::min(delete_cost, transpose_cost));
303	0	}
304	0	last_row[left[i - 1]] = static_cast<Int32>(i);
305	0	}
306
307	0	result = at(m + 1, n + 1);
308	0	return Status::OK();
309	0	}
310
311	0	static Status get_matrix_cell_count(size_t m, size_t n, size_t& matrix_cells) {
312	0	const auto max_size = std::numeric_limits<size_t>::max();
313	0	if (m > max_size - 2 \|\| n > max_size - 2) {
314	0	return Status::InvalidArgument(
315	0	"damerau_levenshtein_distance input is too large to allocate distance matrix");
316	0	}
317
318	0	const size_t rows = m + 2;
319	0	const size_t cols = n + 2;
320	0	if (rows > max_size / cols) {
321	0	return Status::InvalidArgument(
322	0	"damerau_levenshtein_distance distance matrix size overflows");
323	0	}
324
325	0	matrix_cells = rows * cols;
326	0	if (matrix_cells > MAX_DAMERAU_LEVENSHTEIN_MATRIX_CELLS) {
327	0	return Status::InvalidArgument(
328	0	"damerau_levenshtein_distance distance matrix is too large: {} cells exceeds "
329	0	"limit {}",
330	0	matrix_cells, MAX_DAMERAU_LEVENSHTEIN_MATRIX_CELLS);
331	0	}
332	0	return Status::OK();
333	0	}
334
335		static void append_utf8_symbols(const StringRef& str, const Utf8Offsets& offsets,
336		SymbolVector& symbols, SymbolMap& symbol_ids,
337	0	SymbolId& next_symbol) {
338	0	symbols.reserve(symbols.size() + offsets.size());
339	0	for (size_t i = 0; i < offsets.size(); ++i) {
340	0	const size_t offset = offsets[i];
341	0	const size_t next_offset = i + 1 < offsets.size() ? offsets[i + 1] : str.size;
342	0	const std::string_view symbol(str.data + offset, next_offset - offset);
343	0	auto [it, inserted] = symbol_ids.emplace(symbol, next_symbol);
344	0	if (inserted) {
345	0	++next_symbol;
346	0	}
347	0	symbols.push_back(it->second);
348	0	}
349	0	}
350		};
351
352		template <typename Distance>
353		struct StringDistanceImplBase {
354		using ResultDataType = DataTypeInt32;
355		using ResultPaddedPODArray = PaddedPODArray<Int32>;
356
357		static Status vector_vector(const ColumnString::Chars& ldata,
358		const ColumnString::Offsets& loffsets,
359		const ColumnString::Chars& rdata,
360	0	const ColumnString::Offsets& roffsets, ResultPaddedPODArray& res) {
361	0	DCHECK_EQ(loffsets.size(), roffsets.size());
362
363	0	const size_t size = loffsets.size();
364	0	res.resize(size);
365	0	Utf8Offsets left_offsets;
366	0	Utf8Offsets right_offsets;
367	0	for (size_t i = 0; i < size; ++i) {
368	0	RETURN_IF_ERROR(distance(string_ref_at(ldata, loffsets, i),
369	0	string_ref_at(rdata, roffsets, i), left_offsets, right_offsets,
370	0	res[i]));
371	0	}
372	0	return Status::OK();
373	0	} Unexecuted instantiation: _ZN5doris22StringDistanceImplBaseINS_19LevenshteinDistanceEE13vector_vectorERKNS_8PODArrayIhLm4096ENS_9AllocatorILb0ELb0ELb0ENS_22DefaultMemoryAllocatorELb1EEELm16ELm15EEERKNS3_IjLm4096ES6_Lm16ELm15EEES9_SC_RNS3_IiLm4096ES6_Lm16ELm15EEE Unexecuted instantiation: _ZN5doris22StringDistanceImplBaseINS_26DamerauLevenshteinDistanceEE13vector_vectorERKNS_8PODArrayIhLm4096ENS_9AllocatorILb0ELb0ELb0ENS_22DefaultMemoryAllocatorELb1EEELm16ELm15EEERKNS3_IjLm4096ES6_Lm16ELm15EEES9_SC_RNS3_IiLm4096ES6_Lm16ELm15EEE
374
375		static Status vector_scalar(const ColumnString::Chars& data,
376		const ColumnString::Offsets& offsets, const StringRef& constant,
377	0	ResultPaddedPODArray& res) {
378	0	return vector_const(data, offsets, constant, res);
379	0	} Unexecuted instantiation: _ZN5doris22StringDistanceImplBaseINS_19LevenshteinDistanceEE13vector_scalarERKNS_8PODArrayIhLm4096ENS_9AllocatorILb0ELb0ELb0ENS_22DefaultMemoryAllocatorELb1EEELm16ELm15EEERKNS3_IjLm4096ES6_Lm16ELm15EEERKNS_9StringRefERNS3_IiLm4096ES6_Lm16ELm15EEE Unexecuted instantiation: _ZN5doris22StringDistanceImplBaseINS_26DamerauLevenshteinDistanceEE13vector_scalarERKNS_8PODArrayIhLm4096ENS_9AllocatorILb0ELb0ELb0ENS_22DefaultMemoryAllocatorELb1EEELm16ELm15EEERKNS3_IjLm4096ES6_Lm16ELm15EEERKNS_9StringRefERNS3_IiLm4096ES6_Lm16ELm15EEE
380
381		static Status scalar_vector(const StringRef& constant, const ColumnString::Chars& data,
382	0	const ColumnString::Offsets& offsets, ResultPaddedPODArray& res) {
383	0	return vector_const(data, offsets, constant, res);
384	0	} Unexecuted instantiation: _ZN5doris22StringDistanceImplBaseINS_19LevenshteinDistanceEE13scalar_vectorERKNS_9StringRefERKNS_8PODArrayIhLm4096ENS_9AllocatorILb0ELb0ELb0ENS_22DefaultMemoryAllocatorELb1EEELm16ELm15EEERKNS6_IjLm4096ES9_Lm16ELm15EEERNS6_IiLm4096ES9_Lm16ELm15EEE Unexecuted instantiation: _ZN5doris22StringDistanceImplBaseINS_26DamerauLevenshteinDistanceEE13scalar_vectorERKNS_9StringRefERKNS_8PODArrayIhLm4096ENS_9AllocatorILb0ELb0ELb0ENS_22DefaultMemoryAllocatorELb1EEELm16ELm15EEERKNS6_IjLm4096ES9_Lm16ELm15EEERNS6_IiLm4096ES9_Lm16ELm15EEE
385
386		private:
387		static Status vector_const(const ColumnString::Chars& data,
388		const ColumnString::Offsets& offsets, const StringRef& constant,
389	0	ResultPaddedPODArray& res) {
390	0	const size_t size = offsets.size();
391	0	res.resize(size);
392	0	const bool constant_ascii = simd::VStringFunctions::is_ascii(constant);
393	0	Utf8Offsets constant_offsets;
394	0	get_utf8_char_offsets(constant, constant_offsets);
395	0	Utf8Offsets value_offsets;
396	0	for (size_t i = 0; i < size; ++i) {
397	0	RETURN_IF_ERROR(distance_with_const_offsets(string_ref_at(data, offsets, i),
398	0	value_offsets, constant, constant_offsets,
399	0	constant_ascii, res[i]));
400	0	}
401	0	return Status::OK();
402	0	} Unexecuted instantiation: _ZN5doris22StringDistanceImplBaseINS_19LevenshteinDistanceEE12vector_constERKNS_8PODArrayIhLm4096ENS_9AllocatorILb0ELb0ELb0ENS_22DefaultMemoryAllocatorELb1EEELm16ELm15EEERKNS3_IjLm4096ES6_Lm16ELm15EEERKNS_9StringRefERNS3_IiLm4096ES6_Lm16ELm15EEE Unexecuted instantiation: _ZN5doris22StringDistanceImplBaseINS_26DamerauLevenshteinDistanceEE12vector_constERKNS_8PODArrayIhLm4096ENS_9AllocatorILb0ELb0ELb0ENS_22DefaultMemoryAllocatorELb1EEELm16ELm15EEERKNS3_IjLm4096ES6_Lm16ELm15EEERKNS_9StringRefERNS3_IiLm4096ES6_Lm16ELm15EEE
403
404		static Status distance(const StringRef& left, const StringRef& right, Utf8Offsets& left_offsets,
405	0	Utf8Offsets& right_offsets, Int32& result) {
406	0	const bool left_ascii = simd::VStringFunctions::is_ascii(left);
407	0	const bool right_ascii = simd::VStringFunctions::is_ascii(right);
408	0	if (left_ascii && right_ascii) {
409	0	return Distance::ascii(left, right, result);
410	0	}
411
412	0	if (left.size == 0) {
413	0	result = static_cast<Int32>(
414	0	simd::VStringFunctions::get_char_len(right.data, right.size));
415	0	return Status::OK();
416	0	}
417	0	if (right.size == 0) {
418	0	result = static_cast<Int32>(simd::VStringFunctions::get_char_len(left.data, left.size));
419	0	return Status::OK();
420	0	}
421
422	0	get_utf8_char_offsets(left, left_offsets);
423	0	get_utf8_char_offsets(right, right_offsets);
424	0	return Distance::utf8(left, left_offsets, right, right_offsets, result);
425	0	} Unexecuted instantiation: _ZN5doris22StringDistanceImplBaseINS_19LevenshteinDistanceEE8distanceERKNS_9StringRefES5_RSt6vectorImNS_18CustomStdAllocatorImNS_9AllocatorILb0ELb0ELb0ENS_22DefaultMemoryAllocatorELb1EEEEEESD_Ri Unexecuted instantiation: _ZN5doris22StringDistanceImplBaseINS_26DamerauLevenshteinDistanceEE8distanceERKNS_9StringRefES5_RSt6vectorImNS_18CustomStdAllocatorImNS_9AllocatorILb0ELb0ELb0ENS_22DefaultMemoryAllocatorELb1EEEEEESD_Ri
426
427		static Status distance_with_const_offsets(const StringRef& value, Utf8Offsets& value_offsets,
428		const StringRef& constant,
429		const Utf8Offsets& constant_offsets,
430	0	bool constant_ascii, Int32& result) {
431	0	const bool value_ascii = simd::VStringFunctions::is_ascii(value);
432	0	if (value_ascii && constant_ascii) {
433	0	return Distance::ascii(value, constant, result);
434	0	}
435
436	0	if (value.size == 0) {
437	0	result = static_cast<Int32>(constant_offsets.size());
438	0	return Status::OK();
439	0	}
440	0	if (constant.size == 0) {
441	0	result = value_ascii ? static_cast<Int32>(value.size)
442	0	: static_cast<Int32>(simd::VStringFunctions::get_char_len(
443	0	value.data, value.size));
444	0	return Status::OK();
445	0	}
446
447	0	get_utf8_char_offsets(value, value_offsets);
448	0	return Distance::utf8(value, value_offsets, constant, constant_offsets, result);
449	0	} Unexecuted instantiation: _ZN5doris22StringDistanceImplBaseINS_19LevenshteinDistanceEE27distance_with_const_offsetsERKNS_9StringRefERSt6vectorImNS_18CustomStdAllocatorImNS_9AllocatorILb0ELb0ELb0ENS_22DefaultMemoryAllocatorELb1EEEEEES5_RKSC_bRi Unexecuted instantiation: _ZN5doris22StringDistanceImplBaseINS_26DamerauLevenshteinDistanceEE27distance_with_const_offsetsERKNS_9StringRefERSt6vectorImNS_18CustomStdAllocatorImNS_9AllocatorILb0ELb0ELb0ENS_22DefaultMemoryAllocatorELb1EEEEEES5_RKSC_bRi
450		};
451
452		template <typename LeftDataType, typename RightDataType>
453		struct LevenshteinImpl : public StringDistanceImplBase<LevenshteinDistance> {};
454
455		template <typename LeftDataType, typename RightDataType>
456		struct DamerauLevenshteinDistanceImpl : public StringDistanceImplBase<DamerauLevenshteinDistance> {
457		};
458
459		using FunctionLevenshtein =
460		FunctionBinaryToType<DataTypeString, DataTypeString, LevenshteinImpl, NameLevenshtein>;
461		using FunctionDamerauLevenshteinDistance =
462		FunctionBinaryToType<DataTypeString, DataTypeString, DamerauLevenshteinDistanceImpl,
463		NameDamerauLevenshteinDistance>;
464
465	1	void register_function_levenshtein(SimpleFunctionFactory& factory) {
466	1	factory.register_function<FunctionLevenshtein>();
467	1	factory.register_alias(FunctionLevenshtein::name, "levenshtein_distance");
468	1	factory.register_alias(FunctionLevenshtein::name, "edit_distance");
469	1	factory.register_function<FunctionDamerauLevenshteinDistance>();
470	1	}
471
472		} // namespace doris