Algorithm to calculate percent difference between two blobs of text [closed]

Closed. This que开发者_Go百科stion does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

We don’t allow questions seeking recommendations for books, tools, software libraries, and more. You can edit the question so it can be answered with facts and citations.

Closed 2 years ago.

Improve this 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?

---

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).

---

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 ).

---

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

---

Another area of interest might be the Levenshtein distance described here.