Детальное расстояние между словами

Question

Как бы я мог показывать подробное расстояние между словами. Например, вывод программы может быть:

Words are "car" and "cure": 
Replace "a" with "u". 
Add "e". 

Левенштейн расстояние не удовлетворяет мои потребности (я думаю).

Answer 1

Попробуйте следующее. Алгоритм примерно соответствует Wikipedia (Levenshtein distance). Язык, используемый ниже рубинового

Использование в качестве примера, случай изменения s в t следующим образом:

s = 'Sunday' 
t = 'Saturday' 

Во-первых, s и t превращаются в массивы, а пустая строка вставляется в начале. m в конечном итоге будет матрицей, используемой в алгоритме.

s = ['', *s.split('')] 
t = ['', *t.split('')] 
m = Array.new(s.length){[]} 

m здесь, однако, отличается от матрицы заданного алгоритма, если в википедии тот факт, что каждая ячейка включает в себя не только Левенштейна расстояние, но и (не) операцию (начиная , ничего не делать, удаления, вставки или замену), который было использовано, чтобы добраться до этой ячейки от соседних (слева, вверх или верхних левых) клеток. Он также может содержать строку , описывающую параметры операции. То есть, формат каждой ячейки:

[расстояние Левенштейна, операция (, строка)]

Здесь основная процедура. Он заполняет в клетках m следующих алгоритм:

s.each_with_index{|a, i| t.each_with_index{|b, j| 
    m[i][j] = 
    if i.zero? 
     [j, "started"] 
    elsif j.zero? 
     [i, "started"] 
    elsif a == b 
     [m[i-1][j-1][0], "did nothing"] 
    else 
     del, ins, subs = m[i-1][j][0], m[i][j-1][0], m[i-1][j-1][0] 
     case [del, ins, subs].min 
     when del 
      [del+1, "deleted", "'#{a}' at position #{i-1}"] 
     when ins 
      [ins+1, "inserted", "'#{b}' at position #{j-1}"] 
     when subs 
      [subs+1, "substituted", "'#{a}' at position #{i-1} with '#{b}'"] 
     end 
    end 
}} 

Теперь мы устанавливаем i, j в правом нижнем углу m и следуйте инструкциям в обратном направлении, как мы unshift содержимого ячейки в массив с именем steps, пока мы не достигнем начала.

i, j = s.length-1, t.length-1 
steps = [] 
loop do 
    case m[i][j][1] 
    when "started" 
     break 
    when "did nothing", "substituted" 
     steps.unshift(m[i-=1][j-=1]) 
    when "deleted" 
     steps.unshift(m[i-=1][j]) 
    when "inserted" 
     steps.unshift(m[i][j-=1]) 
    end 
end 

Затем мы печатаем операцию и строку каждого шага, если это не операция.

steps.each do |d, op, str=''| 
    puts "#{op} #{str}" unless op == "did nothing" or op == "started" 
end 

При этом конкретном примере, это будет:

inserted 'a' at position 1 
inserted 't' at position 2 
substituted 'n' at position 2 with 'r'