Расстояние Левенштейна с неравномерной стоимостью для вставок и замен:
Я пытался реализовать функцию расстояния Левенштейна в C ++, которая дает различные веса для замен и вставок в зависимости от того, какие символы заменяются или вставляются.
Стоимость рассчитывается исходя из расстояния клавиш на qwerty-клавиатуре. Например, в стандартном алгоритме редактирования расстояния расстояние между google, hoogle и zoogle одинаково; 1. То, что я хочу, это разные расстояния для них. Что-то вроде google -> hoogle = 1, google -> zoogle = 4, hoogle -> zoogle = 5.
Я следовал за Алгоритм википедии используя матрицу для запоминания и реализовал ее на с ++. Вот моя функция.
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];
}
Теперь положения работают должным образом, я верю, но проблема заключается в вставках. Я не знаю, как найти какие символы, чтобы получить расстояние между вставками. Особенно в тех случаях, когда вставка находится в начале или конце строки.
Я был бы признателен за любую помощь в этом, дайте мне знать, если есть какая-либо другая информация, необходимая.
Заранее спасибо.
Решение
То, что вы пытаетесь сделать, имеет смысл для замен. Вы выдвигаете гипотезу о том, что человек, пытающийся ударить по клавише X, с большей вероятностью совершит ошибку, ударив ключ физически около X, чем тот, который находится далеко.
Это не имеет особого смысла для вставок и удалений, потому что действие удара по дополнительному ключу (ошибка вставки) или пропуск нажатия клавиши (ошибка удаления) не имеет ничего общего с расстояниями между клавишами.
Вполне возможно, что вы попадаете в заблуждение из-за двух разных значений «расстояния» в игре. Расстояние Левенштейна измеряется между строками в операциях вставки / замены / удаления. Расстояние от клавиатуры — это физическое разделение. Это яблоки и апельсины, которые описываются одним словом. Они не очень хорошо смешиваются.
Вы пытаетесь определить веса для операций Левенштейна. Физические расстояния между ключами составляют разумные веса для замены.
Веса для вставки и удаления — которые включают только один символ каждый — не имеют никакого очевидного отношения к физическому разделению.
Что вам действительно нужно, так это данные о частоте, какие ключи люди фактически вставляют и удаляют по ошибке. Вы бы дали наиболее распространенные относительно низкие веса и наименее распространенные высокие.
Идея @ user6952491 о том, что повторение предыдущего ключа может быть высокочастотной ошибкой вставки, имеет смысл, но ее сложно расширить до полной схемы взвешивания.
Если вы в угадывающем настроении, вы можете предположить, что легче ошибочно вставить клавишу в середине клавиатуры, чем на ее краях. Сказать f а также j получить самые низкие веса и символы, такие как ~ которые сдвинуты, и у крайностей клавиатуры появляются большие веса, потому что вряд ли вы будете делать физические движения, чтобы набирать их, не задумываясь.
Я оставлю это вам, чтобы сформулировать аналогичное предположение об удалениях.
Для общего набора текста, я предполагаю, что ошибки клавиатуры будут иметь как минимум столько же общего с неправильным написанием, сколько с физическими ошибками. То есть, люди будут печатать «получить», потому что они забыли правило «i до e, кроме как после c», а не из-за положения клавиатуры i относительно e.
Другие виды печатания, например компьютерный код, вполне может иметь совершенно разные шаблоны для ошибок. На ум приходят забытые точки с запятой! У тех были бы очень низкие веса!
Следовательно, я практически уверен, что предложения, представленные современными программами проверки правописания, основаны на алгоритмах машинного обучения, которые делают выводы из ошибок, которые многие тысячи людей делали в прошлом при выполнении аналогичных задач, а не простых показателей, основанных на расстоянии клавиатуры.
Другие решения
если вы поместите все ключи в график, вы можете легко рассчитать их расстояние. было бы даже проще, если бы вы построили это так просто neighbor list или matrix со значениями вы вставляете себя.
по моему мнению, вставка должна учитываться как минимальное расстояние между правыми и левыми (если есть) буквами + 1, потому что Google и Gooogle очень похожи, но Google и Gowogle очень далеко. поэтому google-> googl: = 7.