2
\$\begingroup\$

Below is an implementation of Levenshtein Distance algorithm.

I am trying to use modern C++ features as much as I can, i.e. auto, no pointer / raw memory but I feel like it is a constant struggle.

Code:

#include <string_view>
#include <memory>
#include <vector>

namespace utils
{
    auto getLevenshteinDistance(std::string_view string_1, std::string_view string_2)
    {
        const auto size_1{ string_1.size() };
        const auto size_2{ string_2.size() };

        if (size_1 == 0) return size_2;
        if (size_2 == 0) return size_1;

        std::vector<std::size_t> costs(size_2);
        for (std::size_t k{ 0 }; k <= size_2; ++k) costs[k] = k;

        std::size_t i{ 0 };
        for (const auto& itr_1 : string_1)
        {
            ++i;
            costs[0] = i + 1;
            auto corner{ i };

            std::size_t j{ 0 };
            for (const auto& itr_2 : string_2)
            {
                ++j;
                auto upper{ costs[j + 1] };

                if (itr_1 == itr_2)
                {
                    costs[j + 1] = corner;
                }
                else
                {
                    auto t{ upper < corner ? upper : corner };
                    costs[j + 1] = (costs[j] < t ? costs[j] : t) + 1;
                }

                corner = upper;
            }
        }

        return costs[size_2];
    }
}

For instance, I can't use auto when declaring my vector, because there is no std::make_vector (like make_tuple for instance).

Also I'm developing anxiety for implicit conversions; for instance I could have written

auto i{ 0 };

instead of

std::size_t i{ 0 };

But given that the value will be put into an array containing type std::size_t, I'd rather just have it be of the right type immediately. Lots of stuff like that is bothering me.

Even looping through the array by const auto& seems weird when I'm still having a count variable.. Doesn't advantage disappear, and I might as well just for (int i = 0; ..)

Any suggestions for improvements in the way of modern, good practice, and performance is appreciated.

\$\endgroup\$
  • 4
    \$\begingroup\$ The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Mar 9 at 22:57
  • 1
    \$\begingroup\$ Are you somehow obsessed with the “almost always auto” style? I mean, auto is handy when you want the type to be deduced, but I don’t think you need to change std::size_t i = 0; to auto i = std::size_t{0};. \$\endgroup\$ – L. F. Mar 10 at 1:12
  • 1
    \$\begingroup\$ You're accessing out of bounds for several of your array references: costs[k] = k;, costs[j + 1]. \$\endgroup\$ – 1201ProgramAlarm Mar 10 at 1:27
4
\$\begingroup\$

Invalid access

There are several occurrences of out-of-range access as 1201ProgramAlarm's comment pointed out:

for (std::size_t k{ 0 }; k <= size_2; ++k) costs[k] = k;
costs[j + 1]
return costs[size_2];

This problem can be fixed by increasing the size of costs by one.

Usage of the standard library

std::vector<std::size_t> costs(size_2);
for (std::size_t k{ 0 }; k <= size_2; ++k) costs[k] = k;

Use std::iota:

std::vector<std::size_t> costs(size_2 + 1);
std::iota(costs.begin(), costs.end(), std::size_t{0}); // or 0_zu; see below
auto t{ upper < corner ? upper : corner };
costs[j + 1] = (costs[j] < t ? costs[j] : t) + 1;

Use std::min:

costs[j + 1] = std::min({upper, corner, costs[j]}) + 1;

auto

When you want the type of a variable to be deduced, auto is handy, because you don't have to write the type or expression twice. When you want the type of a variable to be fixed, however, auto becomes cumbersome — so feel free to write

std::size_t i = 0;

An alternative is to use a user-defined literal: (there's a proposal P0330 Literal Suffix for (signed) size_t to add builtin literals for std::size_t)

namespace util_literals {
    constexpr std::size_t operator""_zu(unsigned long long number)
    {
        return static_cast<std::size_t>(number);
    }
}

So you can write:

using namespace util_literals;
auto i = 0_zu;

Also, instead of

for (const auto& itr_1 : string_1)

it is more common to access characters by value. Also, itr is a misleading name for characters:

for (char c_1 : string_1)

Simplification

This check is redundant:

if (size_1 == 0) return size_2;
if (size_2 == 0) return size_1;

because the algorithm works well with empty strings.


Here's my version:

#include <algorithm>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <string_view>
#include <vector>

std::size_t Levenshtein_distance(std::string_view string_a, std::string_view string_b)
{
    const auto size_a = string_a.size();
    const auto size_b = string_b.size();

    std::vector<std::size_t> distances(size_b + 1);
    std::iota(distances.begin(), distances.end(), std::size_t{0});

    for (std::size_t i = 0; i < size_a; ++i) {
        std::size_t previous_distance = 0;
        for (std::size_t j = 0; j < size_b; ++j) {
            distances[j + 1] = std::min({
                std::exchange(previous_distance, distances[j + 1]) + (string_a[i] == string_b[j] ? 0 : 1),
                distances[j] + 1,
                distances[j + 1] + 1
            });
        }
    }
    return distances[size_b];
}

int main()
{
    std::string string_a;
    std::string string_b;
    while (std::cin >> std::quoted(string_a) >> std::quoted(string_b)) {
        std::cout << Levenshtein_distance(string_a, string_b) << '\n';
    }
}

Input:

kitten sitting
corporate cooperation
123 ""
"" ""

Output:

3
5
0
0

(live demo)

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.