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

Question

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

Я хочу сравнить две строки и разрешить опечатки. С Левенштейном все в порядке, но я бы предпочел также принимать орфографические ошибки в зависимости от физического расстояния между клавишами на клавиатуре Qwerty. Другими словами, алгоритм должен предпочесть «yelephone» вместо «zelephone», поскольку клавиша «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] )
)