# Is this the most efficient way to track word changes in a string?

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?

• Kindly provide some explanation of what you are doing here. For example, I assume from the Wiki you reference that you are using a dynamic programming approach and matrix[i,j] equals the Levenshtein distance between the first i characters of first the first j characters of second. It would help the reader a lot to just know that. Also, it should be noted that the else calculation of matrix[i,j] corresponds to a deletion, insertion and substitution, respectively. You should not have to be asked for such basic and essential information. Oct 10 '13 at 2:40
• Thanks for the feedback! I added some comments to hopefully make it more clear. Oct 11 '13 at 13:49
• why not use diff-lcs algorithm instead ? see Diff::LCS
– m_x
Oct 18 '13 at 11:38
• Unless I'm misunderstanding, diff-lcs would show me the number of changes made and the changes themselves. I want to track words, specifically, not just substrings, so Levenshteins algorithm seemed more appropriate. Oct 23 '13 at 15:01

Ruby is fundamentally more about simplicity (readability) than about time/memory efficiency. Otherwise you should choose another language. There are such high level languages, that can beat Ruby, like for example Javascript. And even Python handle strings faster than Ruby at the cost of eternal problems with encodings (don't waste your time on crutches, choose tools wisely).
And even inside Ruby single replacements of one method chain with another can either be efficient or not, depending on your platform (jruby? rubinius? etc.) while there are still different ways to measure an algorithmic complexity especially for your unique kind of input data.

So anyway.

1. The matrix creation I would write in one of these two ways:

matrix = (0..second.size).map{ |i|
(0..first.size).map{ |j|
i==0 ? j : j == 0 ? i : 0
}
}

matrix = (0..second.size).map{ |i|
i==0 ? (0..first.size).to_a : [i]+[0]*first.size
}

There is also a solution via transpose, but not functional, and one via zip in which I doubt.

2. You can omit the return keyword at the last line in Ruby functions.

And this is not Ruby-related, but in the main loop try to iterate through 0...second.length instead of 1..second.length (same for first). In that way you'll swap i-1 with i and i with i+1, getting rid of two decrements in total.

• Is the alternative code in (1) actually more efficient, or just fewer characters? Efficiency is the only thing I'm really worried about. As for (2), I know there's that option in Ruby, but for methods that are more than one line, I personally like to include the return, just to be explicit. Oct 11 '13 at 14:28
• As for your first comments, I'm using ruby 2.0.0p247 and am running this on rails, so ruby or javascript are probably my best options. I suppose I could handle this operation client-side with js, so I'll keep that in mind if this turns out to be a bottleneck in production. Oct 11 '13 at 14:33
• @ChrisFritz, I didn't benchmark, but your way looks faster. But it is more iterative, than functional -- it is just not Ruby style. Oct 13 '13 at 1:57