單詞之間的詳細距離

Question

我將如何去顯示單詞之間的詳細距離。 例如，程序的輸出可能是：

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

的Levenshtein距離不符合我的需要（我認爲）。

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這裏，然而，是從在維基百科如果算法給出的事實，不同的矩陣，每個單元不僅包括Levenshtein距離，而且（非）操作（開始 ，無爲，缺失，插入，或取代），其用於獲取對來自相鄰（左，上，或左上）單元該單元格。它還可能包括描述操作參數的字符串。即，每個單元格的格式是：

[Levenshtein距離，操作（字符串）]

這裏是主程序。它在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'