levenshtein.cpp

Go to the documentation of this file.

#include "./levenshtein.h"
 
#include "./math.h"
#include "./multiarray.h"
 
#include <limits>
 
using namespace std;
 
namespace CppUtilities {


using DistanceArray = MultiArray<size_t, NoneOwningMultiArray, size_t, size_t>;

void initDistanceArray(DistanceArray &distanceArray, const size_t size1, const size_t size2)
{
    const auto maxDistance(size1 + size2);
    // ignore warning about null pointer dereference for now (which is *likely* not correct)
    CPP_UTILITIES_WARNING_PUSH
    CPP_UTILITIES_WARNING_DISABLE("-Wnull-dereference")
    distanceArray.at(0, 0) = maxDistance;
    CPP_UTILITIES_WARNING_POP
    for (size_t i = 0; i <= size1; ++i) {
        distanceArray.at(i + 1, 1) = i;
        distanceArray.at(i + 1, 0) = maxDistance;
    }
    for (size_t i = 0; i <= size2; ++i) {
        distanceArray.at(1, i + 1) = i;
        distanceArray.at(0, i + 1) = maxDistance;
    }
}

size_t performDamerauLevenshteinAlgorithm(
    DistanceArray &distanceArray, const char *const str1, const size_t size1, const char *const str2, const size_t size2)
{
    size_t dist1[std::numeric_limits<unsigned char>::max() + 1] = { 0 };
    for (size_t index1 = 1; index1 <= size1; ++index1) {
        size_t dist2 = 0;
        for (size_t index2 = 1; index2 <= size2; ++index2) {
            const size_t substitution((str1[index1 - 1] == str2[index2 - 1]) ? 0 : 1);
            const size_t transposition1(dist1[static_cast<unsigned char>(str2[index2 - 1])]);
            const size_t transposition2(dist2);
            if (!substitution) {
                dist2 = index2;
            }
            // clang-format off
            distanceArray.at(index1 + 1, index2 + 1) = CppUtilities::min(
                distanceArray.at(index1, index2) + substitution,                                                                     // substitution
                distanceArray.at(index1 + 1, index2) + 1,                                                                            // insertion
                distanceArray.at(index1, index2 + 1) + 1,                                                                            // deletion
                distanceArray.at(transposition1, transposition2) + (index1 - transposition1 - 1) + 1 + (index2 - transposition2 - 1) // transposition
            );
            // clang-format on
        }
        dist1[static_cast<int>(str1[index1 - 1])] = index1;
    }
    return distanceArray.at(size1 + 1, size2 + 1);
}

template <typename DistanceArray>
size_t performDamerauLevenshteinAlgorithmAllocatingOnHeap(
    DistanceArray &distanceArray, const char *const str1, const size_t size1, const char *const str2, const size_t size2)
{
    std::vector<size_t> buffer(distanceArray.totalSize());
    distanceArray.buffer() = buffer.data();
    initDistanceArray(distanceArray, size1, size2);
    return performDamerauLevenshteinAlgorithm(distanceArray, str1, size1, str2, size2);
}

template <typename DistanceArray>
size_t performDamerauLevenshteinAlgorithmAllocatingOnStack(
    DistanceArray &distanceArray, const char *const str1, const size_t size1, const char *const str2, const size_t size2)
{
    size_t buffer[128] = { 0 };
    distanceArray.buffer() = buffer;
    initDistanceArray(distanceArray, size1, size2);
    return performDamerauLevenshteinAlgorithm(distanceArray, str1, size1, str2, size2);
}


std::size_t computeDamerauLevenshteinDistance(const char *const str1, const size_t size1, const char *const str2, const size_t size2)
{
    // allocate distance array
    auto distanceArray(makeNoneOwningMultiArray<std::size_t>(size1 + 2, size2 + 2));
    if (distanceArray.totalSize() <= 128) {
        return performDamerauLevenshteinAlgorithmAllocatingOnStack(distanceArray, str1, size1, str2, size2);
    } else {
        return performDamerauLevenshteinAlgorithmAllocatingOnHeap(distanceArray, str1, size1, str2, size2);
    }
}
 
} // namespace CppUtilities