Расстояние Levenshtein с неравномерной стоимостью для вставок и замен:

Question

Я пытаюсь реализовать функцию расстояния levenshtein в C++, которая дает различные веса для подстановок и вставок, на основе которых символы заменяются или вставлены.

Стоимость уточняется по расстоянию клавиш на клавиатуре qwerty. Например, в стандартном алгоритме редактирования расстояния расстояние между google, hoogle и zoogle одинаково; 1. То, что я хочу, это разные расстояния для них. Что-то вроде google -> hoogle = 1, google -> zoogle = 4, hoogle -> zoogle = 5.

Я следовал за Wikipedia algorithm, используя матрицу для memoization и реализовал ее на C++. Вот моя функция.

int levDist(string s, string t) { 

    int i,j,m,n,temp,subsitutionCost, deletionCost, insertionCost, keyDist; 
    deletionCost = 1; 

    m = s.length(); 
    n = t.length(); 
    int d[m+1][n+1]; 

    for(i=0;i<=m;i++) 
     d[i][0] = i; 
    for(j=0;j<=n;j++) 
     d[0][j] = j; 

    for (j=1;j<=n;j++) 
    { 
     for(i=1;i<=m;i++) 
     { 
      // getKeyboardDist(char a, char b) gives distance b/w the two keys 
      keyDist = getKeyboardDist(s[i-1],t[j-1]); 

      subsitutionCost = (s[i-1] == t[j-1]) ? 0 : keyDist; 

      // this line is the one i think the problem lies in 
      insertionCost = (i > j) ? getKeyboardDist(s[i-1],t[j-2]) : getKeyboardDist(s[i-2],t[j-1]); 


      insertionCost = insertionCost ? insertionCost : 1; 

      d[i][j] = min((d[i-1][j] + deletionCost), 
         min((d[i][j-1] + insertionCost), 
          (d[i-1][j-1] + subsitutionCost)));` 
     } 
    } 
    return d[m][n]; 
} 

Теперь подсекции работают правильно, я верю, но проблема заключается в вставках. Я не знаю, как найти, какие символы получить расстояние между вставками. Особенно случаи, когда вставка находится в начале или конце строки.

Я был бы признателен за любую помощь в этом, сообщите мне, если есть какая-либо другая информация.

Заранее спасибо.

Answer 1

Если вы поместите все ключи в график, вы можете легко рассчитать их расстояние. было бы проще, если вы построите его как простой neighbor list или matrix со значениями, которые вы вставляете сами.

По моему мнению, вставка должна считаться минимальным расстоянием между правыми и левыми (если есть) буквами + 1, потому что google и gooogle довольно похожи, но google и gowogle очень далеки. поэтому google-> googl: = 7.

Answer 2

То, что вы пытаетесь сделать, имеет смысл для замещений. Вы выдвигаете гипотезу, что человек, пытающийся нанести удар по ключу X, с большей вероятностью допустит ошибку, ударив ключ физически ближе к X, чем тот, который находится далеко.

Это не имеет особого смысла для вставки и удаления, потому что действие удара лишним ключом (ошибка ввода) или пропущенное нажатие клавиши (ошибка удаления) не имеет ничего общего с расстояниями между ключами.

Возможно, вы ошибаетесь в двух разных значениях «расстояния» в игре здесь. Расстояние Левенштейна измеряется между строками во вставке/замене/удалении. Расстояние клавиатуры - физическое разделение. Это яблоки и апельсины, которые описываются одним и тем же словом. Они не смешиваются очень хорошо.

Вы пытаетесь установить массы для операций Левенштейна. Физические расстояния между клавишами обеспечивают разумный вес для замещения.

Веса для вставки и удаления - которые включают только один символ каждый - не имеют очевидной связи с физическим разделением.

Что вам действительно нужно, так это частотные данные о том, какие именно люди фактически вставляют и удаляют по ошибке. Вы бы дали наиболее распространенные относительно низкие веса и наименее распространенные высокие.

Идея @ user6952491 о том, что повторение предыдущего ключа может быть высокой ошибкой вставки вставки, имеет смысл, но ее трудно расширить до полной схемы взвешивания.

Если вы находитесь в угадывающем настроении, вы можете предположить, что проще ошибочно вставить ключ рядом с серединой клавиатуры, чем по краям. Скажем, f и j получают наименьшие веса и персонажи, такие как ~, которые сдвинуты, а на клавиатуре экстремумы получают большие веса, потому что вряд ли вы сделаете физические движения, чтобы набирать их, не задумываясь.

Я оставлю это вам, чтобы сформулировать аналогичное предположение об удалении.

Для общей типизации я предполагаю, что ошибки в клавиатуре будут иметь, по крайней мере, столько же, что и неправильное понимание орфографии как физических ошибок. I.e., люди будут вводить «получать», потому что они забыли правило «i до e, за исключением c», не из-за положения клавиатуры i относительно e.

Другие виды печатания, например. компьютерный код, вполне могут иметь совершенно разные шаблоны для совершения ошибок. Приходят на ум забытые точки с запятой! У них будет очень низкий вес!

Следовательно, я практически уверен, что предложения, предлагаемые современными средствами проверки орфографии, основаны на алгоритмах машинного обучения, которые делают выводы из ошибок, которые многие тысячи людей делали в прошлом по схожим задачам, а не простые показатели на основе клавиатуры расстояние.