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

Question

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

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

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

Answer 1

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

ПРЕДОСТЕРЕЖЕНИЕ:Однако убедитесь, что удаления и вставки взвешены должным образом, чтобы они не были приняты как минимальные.В итоге вы получите строку вставок / удалений / символов без подстановки изменений.

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

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] )
)