Damerau-Levenshtein distance for distance

Question

나는 알고리즘을 찾고 있지만, 단어 사이를 바꾸거나 글자 사이를 바꾸지 않는다. 그런 알고리즘이 있습니까?

SQL Server를 사용하여 구현을 찾고 있지만 알고리즘 이름이 충분할 것입니다.

Answer 1

필자가 알고있는 한, 기존의 Levenshtein 알고리즘을 사용할 수있는 이유가 없습니다. 글자 대신 기호로 단어를 사용하십시오.

Answer 2

1. 분할 공간
2. 로하여 두 문자열이 두 문자열의 단어를 (당신이 원하는 경우, 하나에 분할 작업에서 얻을 CONCATENATE 배열)를 이동하여 워드 해시 테이블을 만들고, 각각의 새로운 단어는 점진적를 가져옵니다 새 번호
수의 2 결과 arays (에
3. 사용 Levenshtein 알고리즘하지만 11, 12 년부터 문자열로 다시 변환하지 않고 -> "1112"-> 1,1,1,2

당신이 만약 철자를 찾아야 할 때 단어를 다시 정렬해야합니다. 분할 된 배열을 다른 순서로 정렬 된 문자열로 다시 음소거 한 다음 새로운 단어와 두 번째 구문에서 Levenshtein을 실행하면 좋습니다!

Harward 의대 (2 구역 6 순열) 의학 Harward 학교 (3 개 공간 (24) 순열) Levenshtein 거리 - 17 비교 말하자면 "스탠포드 의과 대학"(Levenshtein 거리 5)

행

Harward School Medical 대 Harward School of Medicine (의학 대 Harward School of Medicine)은 6의 LD를 받았습니다. 그러나 Stanford에 실수를 허용하고 있지만 순위를 올리는 데는 많은 시간이 걸리므로 단어를 삭제하는 것과 같은 방법으로 구축 할 수 있습니다. of 3)

공간에 의한 치환 단어의 수행은 O (n!)이고, 단어의 삭제는 O (n + m)이고, n, m은 wo 당신이 한 단어 이상을 놓기를 원하지 않는 한, 각 문구에있는 rds는 4 문자보다 적은 단어 또는 전치사/형용사 목록의 단어 만 제외시킬 수 있습니다.

Levenshtein의 성능은 다음과 같습니다. 위키 피 디아 페이지에서 설명했다.