view common/EditDistance.cpp @ 28:7d8a6167febb classical-rdf

* Begin new text entry / search widget & test utility for it
* Improve typing matching methods
* Update code to use ObjectLoader/Storer instead of old-style ObjectMapper

#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;
}

}