Как эффективный способ измерить сходство между двумя строками? (Расстояние Левенштейна делает стек слишком глубоким) - PullRequest
Новая
       43

Как эффективный способ измерить сходство между двумя строками? (Расстояние Левенштейна делает стек слишком глубоким)

3 голосов
/ 23 декабря 2011

Итак, я начал с этого: http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Ruby

, который прекрасно работает для действительно маленьких струн.Но мои строки могут быть длиной более 10 000 символов - и поскольку расстояние Левенштейна является рекурсивным, это приводит к слишком глубокой ошибке стека в моем приложении Ruby on Rails.

Итак, есть ли другой, возможно, меньший стекинтенсивный метод нахождения сходства между двумя большими строками?

В качестве альтернативы, мне нужен способ, чтобы стек имел гораздо больший размер.(Хотя я не думаю, что это правильный способ решить проблему)

1 Ответ

7 голосов
/ 23 декабря 2011

Рассмотрим нерекурсивную версию, чтобы избежать чрезмерных затрат стека вызовов. Сет Шредер имеет итерационную реализацию в Ruby , которая вместо этого использует многомерные массивы;похоже, это связано с подходом динамического программирования расстояния Левенштейна (как описано в псевдокоде для статьи Википедии ).Рубиновый код Сета воспроизводится ниже: 

def levenshtein(s1, s2)
  d = {}
  (0..s1.size).each do |row|
    d[[row, 0]] = row
  end
  (0..s2.size).each do |col|
    d[[0, col]] = col
    end
  (1..s1.size).each do |i|
    (1..s2.size).each do |j|
      cost = 0
      if (s1[i-1] != s2[j-1])
        cost = 1
      end
      d[[i, j]] = [d[[i - 1, j]] + 1,
                   d[[i, j - 1]] + 1,
                   d[[i - 1, j - 1]] + cost
                  ].min
      next unless @@damerau
      if (i > 1 and j > 1 and s1[i-1] == s2[j-2] and s1[i-2] == s2[j-1])
        d[[i, j]] = [d[[i,j]],
                     d[[i-2, j-2]] + cost
                    ].min
      end
    end
  end
  return d[[s1.size, s2.size]]
end
...