Подтвердить что ты не робот

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

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 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] )
)