Матрица подобия для взвешенного расстояния редактирования

Question

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

К примеру, стоимость замещения s по будет меньше, чем подставляя s, скажем, р.

Алгоритм для этого с помощью 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 для всех пар букв. Я имею в виду, что я хочу, чтобы затраты основывались на расстоянии между буквами на клавиатуре. Разве никто так явно не определил такую ​​матрицу?

Answer 1

Я написал 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] содержит расстояние между клавишами.