2
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Cary Swoveland Oct 10 '13 at 2:40
  • \$\begingroup\$ Thanks for the feedback! I added some comments to hopefully make it more clear. \$\endgroup\$ – Chris Fritz Oct 11 '13 at 13:49
  • \$\begingroup\$ why not use diff-lcs algorithm instead ? see Diff::LCS \$\endgroup\$ – m_x Oct 18 '13 at 11:38
  • \$\begingroup\$ 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. \$\endgroup\$ – Chris Fritz Oct 23 '13 at 15:01
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Chris Fritz Oct 11 '13 at 14:28
  • \$\begingroup\$ 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. \$\endgroup\$ – Chris Fritz Oct 11 '13 at 14:33
  • \$\begingroup\$ @ChrisFritz, I didn't benchmark, but your way looks faster. But it is more iterative, than functional -- it is just not Ruby style. \$\endgroup\$ – Nakilon Oct 13 '13 at 1:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.