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

Question

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?

Answer 1

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.