인수로 두 문자열, 원본 및 대상을 사용하고 원본 문자열을 대상으로 변환하는 데 필요한 단계를 반환하는 알고리즘을 찾고 있습니다. Levenshtein 거리를 한 걸음 더 멀리 내딛는 것.기본 문자열 차이 알고리즘을위한 권장 검색
예
입력 : 소스 위치 1의 'B'를 삽입
입력 : 소스 "ABC"최종 도착 "AC"
출력 "ABBC"소스 "ABC"최종 도착 출력 : 소스의 위치 1에서 'b'를 삭제하십시오.
고마워요.
Wikipedia의 diff 알고리즘을 살펴보십시오.
먼저 모든 문자를 쌍으로 나열 해보십시오. 최대한 많은 수를 페어링 한 후에 삽입 및 삭제가 명확해야합니다.
abcde
| /|
acbdd
를 추가합니다.
실제로는 메서드가 최적의 솔루션을 보장하지 않습니다. 가장 최적의 솔루션은 예를 들어, 하나의 삽입물이 아닌 직관적이지 않고 대체 할 수 있습니다. 그것은 당신이 어떻게 작동에 가중치를 주느냐에 달려 있습니다 (삽입과 삭제는 일반적으로 매우 비쌉니다). 잘 알려진 알고리즘은이를 고려합니다. 그들은 대개 동적 프로그래밍 솔루션에 의존합니다. –
정확합니다. 나는 이것이 학교 임무이고 단순함이 정확도보다 더 가치 있다고 가정하에 가고있었습니다. 정확성을 원한다면 일치하는 가장 큰 청크를 검색 한 다음 해당 청크의 양쪽에 남아있는 문자열 (문자열 모두)과 재귀를 가져옵니다. –
기존의 잘 알려진 diff 유틸리티로 보내고 해당 diff의 결과를 사용하는 방법을 찾으려고합니다. diff -e 또는 diff -n.
숙제와 같은 소리가 들립니다. - 태그를 지정해야한다면, 우리가 대답하지 않을 것입니다. –
확실히 숙제가 아니라 내 맞춤식 심비안 텍스트 상자에서 터치 기반의 단어 교정 용입니다. – kujawk
Dan Gusfield의 책이 없으면 권하고 싶습니다. 그것은 주제에 관한 유일한 결정판입니다. –