Levenshtein과 비슷한 좋은 알고리즘이지만 Qwerty 키보드에 가중치가 있습니까?

Question

문자열 일치와 관련된 몇 가지 게시물을 발견했습니다. 이는 해결해야 할 오래된 문제를 상기 시켰습니다. 누군가가 좋은 Levenshtein 같은 알고리즘을 Qwerty 키보드 가중치가 있습니까?

두 개의 문자열을 비교하고 오타를 허용하고 싶습니다. Levenshtein은 괜찮지 만 Qwerty 키보드의 키 사이의 물리적 거리를 기반으로 맞춤법 오류를 허용하는 것을 선호합니다. 즉, 알고리즘은 "y"키가 "t"키에 가깝기 때문에 대부분의 키보드에서 "z"키보다 "yelephone"을 "zelephone"으로 선택해야합니다.

도움이 될 것입니다.이 기능은 내 프로젝트의 중심이 아니므로 더 생산적인 일을해야 할 때 쥐구멍으로 벗어나고 싶지는 않습니다.

Answer 1

생물 정보학에서 두 개의 DNA 염기 서열을 정렬하면 대체가 전이 또는 전이 였을 때 다른 비용을 가진 모델을 가질 수 있습니다. 이것은 정확히 당신이 원하는 것입니다. 그러나 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]) 
)