Algorithm to calculate percent difference betweem two blobs of text.

Question

I've been researching on finding an efficient solution to this. I've looked into diffing engines (google's diff-match-patch, python's diff) and some some longest common chain algorithms.

I was hoping on getting you guys suggestions on how to solve this issue. Any algorithm or library in particular you would like to recommend?

Thanks.

Answer 1

Longest common chain? Perhaps this will help then: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Answer 2

In addition to difflib and other common subsequence libraries, if it's natural language text, you might look into stemming, which normalizes words to their root form. You can find several implementations in the Natural Language Toolkit ( http://www.nltk.org/ ) library. You can also compare blobs of natural language text more semantically by using N-Grams ( http://en.wikipedia.org/wiki/N-gram ).

Answer 3

I don't know what "longest common [[chain? substring?]]" has to do with "percent difference", especially after seeing in a comment that you expect a very small % difference between two strings that differ by one character in the middle (so their longest common substring is about one half of the strings' length).

Ignoring the "longest common" strangeness, and defining "percent difference" as the edit distance between the strings divided by the max length (times 100 of course;-), what about:

def levenshtein_distance(first, second):
    """Find the Levenshtein distance between two strings."""
    if len(first) > len(second):
        first, second = second, first
    if len(second) == 0:
        return len(first)
    first_length = len(first) + 1
    second_length = len(second) + 1
    distance_matrix = [[0] * second_length for x in range(first_length)]
    for i in range(first_length):
       distance_matrix[i][0] = i
    for j in range(second_length):
       distance_matrix[0][j]=j
    for i in xrange(1, first_length):
        for j in range(1, second_length):
            deletion = distance_matrix[i-1][j] + 1
            insertion = distance_matrix[i][j-1] + 1
            substitution = distance_matrix[i-1][j-1]
            if first[i-1] != second[j-1]:
                substitution += 1
            distance_matrix[i][j] = min(insertion, deletion, substitution)
    return distance_matrix[first_length-1][second_length-1]

def percent_diff(first, second):
    return 100*levenshtein_distance(a, b) / float(max(len(a), len(b)))

a = "the quick brown fox"
b = "the quick vrown fox"
print '%.2f' % percent_diff(a, b)

The Levenshtein function is from Stavros' blog. The result in this case would be 5.26 (percent difference).

Answer 4

link textAnother area of interest might be the Levenshtein distance described here.