1 // Copyright 2023 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "base/strings/levenshtein_distance.h"
6
7 #include <stddef.h>
8
9 #include <algorithm>
10 #include <numeric>
11 #include <optional>
12 #include <string_view>
13 #include <vector>
14
15 namespace base {
16
17 namespace {
18
19 template <typename CharT>
LevenshteinDistanceImpl(std::basic_string_view<CharT> a,std::basic_string_view<CharT> b,std::optional<size_t> max_distance)20 size_t LevenshteinDistanceImpl(std::basic_string_view<CharT> a,
21 std::basic_string_view<CharT> b,
22 std::optional<size_t> max_distance) {
23 if (a.size() > b.size()) {
24 a.swap(b);
25 }
26
27 // max(a.size(), b.size()) steps always suffice.
28 const size_t k = max_distance.value_or(b.size());
29 // If the string's lengths differ by more than `k`, so does their
30 // Levenshtein distance.
31 if (a.size() + k < b.size()) {
32 return k + 1;
33 }
34 // The classical Levenshtein distance DP defines dp[i][j] as the minimum
35 // number of insert, remove and replace operation to convert a[:i] to b[:j].
36 // To make this more efficient, one can define dp[i][d] as the distance of
37 // a[:i] and b[:i + d]. Intuitively, d represents the delta between j and i in
38 // the former dp. Since the Levenshtein distance is restricted by `k`, abs(d)
39 // can be bounded by `k`. Since dp[i][d] only depends on values from dp[i-1],
40 // it is not necessary to store the entire 2D table. Instead, this code just
41 // stores the d-dimension, which represents "the distance with the current
42 // prefix of the string, for a given delta d". Since d is between `-k` and
43 // `k`, the implementation shifts the d-index by `k`, bringing it in range
44 // [0, `2*k`].
45
46 // The algorithm only cares if the Levenshtein distance is at most `k`. Thus,
47 // any unreachable states and states in which the distance is certainly larger
48 // than `k` can be set to any value larger than `k`, without affecting the
49 // result.
50 const size_t kInfinity = k + 1;
51 std::vector<size_t> dp(2 * k + 1, kInfinity);
52 // Initially, `dp[d]` represents the Levenshtein distance of the empty prefix
53 // of `a` and the first j = d - k characters of `b`. Their distance is j,
54 // since j removals are required. States with negative d are not reachable,
55 // since that corresponds to a negative index into `b`.
56 std::iota(dp.begin() + static_cast<long>(k), dp.end(), 0);
57 for (size_t i = 0; i < a.size(); i++) {
58 // Right now, `dp` represents the Levenshtein distance when considering the
59 // first `i` characters (up to index `i-1`) of `a`. After the next loop,
60 // `dp` will represent the Levenshtein distance when considering the first
61 // `i+1` characters.
62 for (size_t d = 0; d <= 2 * k; d++) {
63 if (i + d < k || i + d >= b.size() + k) {
64 // `j = i + d - k` is out of range of `b`. Since j == -1 corresponds to
65 // the empty prefix of `b`, the distance is i + 1 in this case.
66 dp[d] = i + d + 1 == k ? i + 1 : kInfinity;
67 continue;
68 }
69 const size_t j = i + d - k;
70 // If `a[i] == `b[j]` the Levenshtein distance for `d` remained the same.
71 if (a[i] != b[j]) {
72 // (i, j) -> (i-1, j-1), `d` stays the same.
73 const size_t replace = dp[d];
74 // (i, j) -> (i-1, j), `d` increases by 1.
75 // If the distance between `i` and `j` becomes larger than `k`, their
76 // distance is at least `k + 1`. Same in the `insert` case.
77 const size_t remove = d != 2 * k ? dp[d + 1] : kInfinity;
78 // (i, j) -> (i, j-1), `d` decreases by 1. Since `i` stays the same,
79 // this is intentionally using the dp value updated in the previous
80 // iteration.
81 const size_t insert = d != 0 ? dp[d - 1] : kInfinity;
82 dp[d] = 1 + std::min({replace, remove, insert});
83 }
84 }
85 }
86 return std::min(dp[b.size() + k - a.size()], k + 1);
87 }
88
89 } // namespace
90
LevenshteinDistance(std::string_view a,std::string_view b,std::optional<size_t> max_distance)91 size_t LevenshteinDistance(std::string_view a,
92 std::string_view b,
93 std::optional<size_t> max_distance) {
94 return LevenshteinDistanceImpl(a, b, max_distance);
95 }
LevenshteinDistance(std::u16string_view a,std::u16string_view b,std::optional<size_t> max_distance)96 size_t LevenshteinDistance(std::u16string_view a,
97 std::u16string_view b,
98 std::optional<size_t> max_distance) {
99 return LevenshteinDistanceImpl(a, b, max_distance);
100 }
101
102 } // namespace base
103