Хороший алгоритм, подобный Левенштейну, но взвешенный для клавиатур Qwerty?

Question

Я заметил некоторые сообщения здесь о совпадении строк, что напомнило мне о старой проблеме, которую я хотел бы решить. У кого-нибудь есть хороший алгоритм Levenshtein, который взвешен по отношению к клавиатурам Qwerty?

Я хочу сравнить две строки и разрешить опечатки. Левенштейн в порядке, но я бы предпочел также принимать орфографические ошибки на основе физического расстояния между клавишами на клавиатуре Qwerty. Другими словами, алгоритм должен предпочесть «yelephone» на «zelephone», так как клавиша «y» расположена ближе к клавише «t», чем к клавише «z» на большинстве клавиатур.

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

Answer 1

В биоинформатике, когда вы выровняете две последовательности ДНК, у вас может быть модель с разной стоимостью, основанная на том, что замена является переходом или трансверсией. Это именно то, что вы хотите, но вместо матрицы 4x4 вам нужна матрица 40x40 или некоторые, осмелюсь сказать, что функция расстояния? Таким образом, стоимость замены зависит от матрицы/функции, а не от константы.

CAVEAT: Убедитесь, что удаления и вставки правильно взвешиваются, поэтому они не принимаются в качестве минимума. В итоге вы получите строку символов вставки/удаления/замены без замены.

Новая функция, которую вы пытаетесь свести к минимуму будет:

d[i, j] := minimum(
    d[i-1, j] + del_cost, 
    d[i, j-1] + ins_cost, 
    d[i-1, j-1] + keyboard_distance(s[i], t[j]) 
)