加權編輯距離的相似矩陣

我想實現對基本編輯距離算法的修改。也就是加權編輯距離。（背景：拼寫錯誤，而試圖創建一個搜索引擎）加權編輯距離的相似矩陣

例如，替換小號通過一個會比替換較小的成本小號，比方說，p。

算法此使用DP將需要一個簡單的變化，即

d[i, j] := minimum(d[i-1, j] + 1,       // deletion 
         d[i, j-1] + 1,     // insertion 
         d[i-1, j-1] + substitutionCost) // substitution

我看了，但我不能在任何地方找到這樣的矩陣，這會給我適當substitutionCost將所有對的信件。我的意思是，我想要的成本是基於鍵盤上的字母之間的距離。沒有人明確定義這樣的矩陣嗎？

來源

2016-03-06 Mallika

投票結束，作爲題外話題。問題不在於編程部分，而在於「哪裏可以找到替代成本矩陣？」 – amit

對不起！那麼我在哪裏發佈這個問題呢？ – Mallika

我不知道，也許reddit – amit

我寫了一個C++代碼，應該工作，我也作出了這樣的假設鍵對稱地放置：

#include<bits/stdc++.h> 

using namespace std; 

string s[3]; 
int mat[35][35]; 

int main() { 
    s[0] = "qwertyuiop"; 
    s[1] = "asdfghjkl;"; 
    s[2] = "zxcvbnm,./"; 

    for(int i = 0;i < 10;i++){ 
     for(int j = 0;j < 3;j++){ 
      for(int k = 0;k < 10;k++){ 
       for(int l = 0;l < 3;l++){ 
        if(j == 1 && i > 8) continue;if(l == 1 && k > 8) continue; 
        if(j == 2 && i > 6) continue;if(l == 2 && k > 6) continue; 
        int st1 = s[j][i] - 'a'; 
        int st2 = s[l][k] - 'a'; 
        mat[st1][st2] = abs(j-l) + abs(i-k); 
       } 
      } 
     } 
    } 
    for(int i = 0;i < 26;i++){ 
     for(int j = 0;j < 26;j++){ 
      cout << (char)(i+'a') << " " << (char)(j+'a') << " " << mat[i][j] << endl; 
     } 
    } 

return 0; 
}

鏈接到輸出上Ideone：http://ideone.com/xq7kKp

這裏mat[i][j]包含的距離在鍵之間。

來源

2016-03-06 18:34:42 uSeemSurprised

加權編輯距離的相似矩陣

回答

相關問題