ngmarchant / comparator Goto Github PK

These measures are currently implemented in R. Porting to C++ is challenging, as it may be necessary to call an R function (the inner measure) from C++.

@ngmarchant the Levenshtein distance can be implemented using only two rows for dmat, instead of using a square matrix. That could significantly reduce memory usage when comparing long sequences (400 Mb to 80 Kb when comparing strings of length 10,000).

Would it be worth it to implement this? I could propose the changes.

Example Python implementation:

import numpy as np
dmat = np.zeros((100,2))

def levenshtein(s, t, dmat):
    m = len(s)
    n = len(t)
    dmat[:, 0] = np.arange(dmat.shape[0])

    for j in range(1, n+1):
        dmat[0, (j-1) % 2] = j-1
        dmat[0, j % 2] = j
        for i in range(1, m+1):
            cost = 0
            if s[i-1] != t[j-1]:
                cost = 1
            dmat[i, j % 2] = min(dmat[i-1, j % 2] + 1, dmat[i, (j-1) % 2] +
                                 1, dmat[i-1, (j-1) % 2] + cost)
    return dmat[m, n % 2]

levenshtein("test", "testt", dmat)

The following example emits warning messages about the vectors being of different lengths.

known_names <- c("Roberto", "Umberto", "Alberto")
comparator <- InVocabulary(known_names)
x <- "Roberto"
y <- c("Roberto", "Enberto", "Norberto")
elementwise(comparator, x, y)

StringMeasures currently only support comparisons between strings. It would be desirable to support comparisons between more general sequences---e.g. vectors of integers.

Consider adding support for token-based comparators. After mapping strings to token sets, the similarity of the sets can be measured using:

• Cosine similarity
• Sørensen–Dice coefficient
• Jaccard index
• Tversky index