I'm working on a writing platform and am using a modified version of the Levenshtein distance algorithm to track a writer's engagement with their writing. It tracks not only words added to their content, but also rewards editing by including words removed and words substituted in the count.
Here's my algorithm in Ruby (which I run between (auto)saves):
def words_changed_since(second)
first = self.split # array of words in first string
second = second.split # array of words in second string
# initialize the matrix
matrix = [(0..first.length).to_a]
(1..second.length).each do |j|
matrix << [j] + [0] * (first.length)
end
# for each word in the second string
(1..second.length).each do |i|
# for each word in the first string
(1..first.length).each do |j|
if first[j-1] == second[i-1]
matrix[i][j] = matrix[i-1][j-1]
else
matrix[i][j] = [
matrix[i-1][j], # word deletion
matrix[i][j-1], # word insertion
matrix[i-1][j-1] # word substitution
].min + 1
end
end
end
return matrix.last.last
end
Is this the most efficient way of tracking these changes?
matrix[i,j]
equals the Levenshtein distance between the first i characters offirst
the first j characters ofsecond
. It would help the reader a lot to just know that. Also, it should be noted that theelse
calculation ofmatrix[i,j]
corresponds to a deletion, insertion and substitution, respectively. You should not have to be asked for such basic and essential information. \$\endgroup\$ – Cary Swoveland Oct 10 '13 at 2:40diff-lcs
algorithm instead ? see Diff::LCS \$\endgroup\$ – m_x Oct 18 '13 at 11:38