annotate common/EditDistance.cpp @ 12:dc55b0940f15 classical-rdf

...

#include "EditDistance.h"

namespace ClassicalData
{

int
EditDistance::calculate(QString a, QString b)
{
    // Note: restricted Damerau-Levenshtein edit distance, or
    // Levenshtein if NoTransposition

    int al = a.length() + 1;
    int bl = b.length() + 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 * m_editPenalty;
    }

    for (int j = 1; j < al; ++j) {
	currRow[0] = j * m_editPenalty;
	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] + m_editPenalty;
		diagonal   = prevRow[i-1] + m_editPenalty;
		if (i+1 == bl) vertical = prevRow[i] + m_suffixPenalty;
		else vertical = prevRow[i] + m_editPenalty;
		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] + m_editPenalty);
		}
	    }
	}
	tmp = ppreRow;
	ppreRow = prevRow;
	prevRow = currRow;
	currRow = tmp;
    }

    int result = prevRow[bl-1];
    if (m_normalise) {
	result = result / m_editPenalty;
	if (result % m_editPenalty) ++result;
    }
    return result;
}

}