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

Question

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

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

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

Answer 1

Попробуйте следующее. Алгоритм примерно соответствует Википедии (расстояние Левенштейна) . Используемый ниже язык - ruby ​​

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

s = 'Sunday'
t = 'Saturday'

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

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

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

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

Вот основная рутина. Заполняет ячейки 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 и выполняем шаги в обратном порядке, пока мы не сдвигаем содержимое ячейки в массив с именем 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'