OMRAS2 Classical Browser

#include "EditDistance.h"

#include <algorithm>

#include <cstdlib> // abs

namespace ClassicalData

{

int

EditDistance::calculate(QString a, QString b, int threshold)

{

    // Note: restricted Damerau-Levenshtein edit distance, or

    // Levenshtein if NoTransposition

    int al = a.length() + 1;

    int bl = b.length() + 1;

    if (threshold > 0 && abs(al - bl) > threshold) return threshold + 1;

    int *currRow = (int *)alloca(sizeof(int) * bl);

    int *prevRow = (int *)alloca(sizeof(int) * bl);

    int *ppreRow = (int *)alloca(sizeof(int) * bl);

    int *tmp = 0;

    for (int i = 0; i < bl; ++i) {

        prevRow[i] = i;

    }

    for (int j = 1; j < al; ++j) {

        currRow[0] = j;

        bool stillAcceptable = (threshold == 0);

        for (int i = 1; i < bl; ++i) {

            if (a[j-1] == b[i-1]) {

                currRow[i] = prevRow[i-1];

            } else {

                int horizontal, vertical, diagonal;

                horizontal = currRow[i-1] + 1;

                diagonal   = prevRow[i-1] + 1;

                if (i+1 == bl) vertical = prevRow[i] + 1;

                else vertical = prevRow[i] + 1;

                currRow[i] =

                    std::min(horizontal, std::min(vertical, diagonal));

            }

            if (m_transpositionMode == RestrictedTransposition) {

                if (i > 1 && j > 1 && a[i-1]==b[j-2] && a[i-2]==b[j-1]) {

                    currRow[i] = std::min(currRow[i], ppreRow[i-2] + 1);

                }

            }

            if (threshold > 0 && currRow[i] <= threshold) {

                stillAcceptable = true;

            }

        }

        if (!stillAcceptable) return threshold + 1;

        tmp = ppreRow;

        ppreRow = prevRow;

        prevRow = currRow;

        currRow = tmp;

    }

    int result = prevRow[bl-1];

    return result;

}

}