levenshpp/levenshtein.hpp

#pragma once

#include <utility>
#include <queue>

unsigned int levenshtein_get(unsigned int * const *map, int px, int py)
{
    if (px == -1 && py == -1)
        return 0;
    if (px == -1)
        return py +1;
    if (py == -1)
        return px +1;
    return map[px][py];
}

template <class T, typename SIZE=unsigned int>
unsigned int levenshtein(const T *a, const T *b, const SIZE aSize, const SIZE bSize)
{
    unsigned int **items = new unsigned int*[aSize]();

    for (SIZE i =0; i < aSize; i++)
    {
        items[i] = new unsigned int[bSize]();
        for (SIZE j =0; j < bSize; j++)
        {
            unsigned int add = levenshtein_get(items, i, j -1) +1;
            unsigned int del = levenshtein_get(items, i -1, j) +1;
            unsigned int mod = levenshtein_get(items, i -1, j -1) +(a[i] == b[j] ? 0 : 1);

            items[i][j] = std::min(std::min(add, del), mod);
        }
    }
    const unsigned int levenshtein = items[aSize -1][bSize -1];
    for (SIZE i =0; i < aSize; i++)
        delete[] items[i];
    delete[] items;
    return levenshtein;
}

template <class T, typename SIZE=unsigned int>
unsigned int levenshtein(const T &a, const T &b, const SIZE aSize, const SIZE bSize)
{
    unsigned int **items = new unsigned int*[aSize]();

    for (SIZE i =0; i < aSize; i++)
    {
        items[i] = new unsigned int[bSize]();
        for (SIZE j =0; j < bSize; j++)
        {
            unsigned int add = levenshtein_get(items, i, j -1) +1;
            unsigned int del = levenshtein_get(items, i -1, j) +1;
            unsigned int mod = levenshtein_get(items, i -1, j -1) +(a[i] == b[j] ? 0 : 1);

            items[i][j] = std::min(std::min(add, del), mod);
        }
    }
    const unsigned int levenshtein = items[aSize -1][bSize -1];
    for (SIZE i =0; i < aSize; i++)
        delete[] items[i];
    delete[] items;
    return levenshtein;
}