고급 서열 정렬

Question

은 표절에 대해 다음과 생식 모델을 가정 1. 2. 3. 새로운 텍스트를 추가합니다 텍스트의 일부를 다시 정렬 텍스트의 일부를 제거합니다.

Ex. ABCD 원래 텍스트 인 경우 (A, B, C 및 D가 단락 또는 문장 다발 일 수있다), 출력은 E, F 및 G는 추가 텍스트이다 DEAFCG가 첨가 될 수있다.

또한 표절자가 작은 오류 (작은 비율로 삽입, 대체 및 삭제)를 추가합니다.

이 표절 사건을 어떻게 감지합니까?

내가 지금까지 해 온 것 : 가장 긴 공통 부분 순서 방법을 사용해 보았습니다. 일치하는 텍스트의 선형 세트를 감지합니다. 위의 예에서 D 또는 AC를 감지합니다 (길이에 따라 다름)

필요한 것 :이 문제를 처리하는 원칙적인 방법입니다. 기존 문헌에 대한 인용은 매우 유용 할 것입니다. 아이디어를위한 의사 코드도 좋습니다. 제발 코드.

이것은 숙제가 아니며 면접 질문이 아닙니다. 나는이 장난스러운 문제에 대한 나의 실질적인 문제를 단순화했다.

Answer 1

수많은 응용 프로그램이 작업을 수행하는 알고리즘을 제공하고 있습니다. 지금까지 내가 말할 수있는, 그들은 거의 할 (하고 싶은) 어떤 것은 편집의 거리를 계산하는 것입니다 다소 차이가 서로 다른 알고리즘의 숫자, http://en.wikipedia.org/wiki/Levenshtein_distance#Relationship_with_other_edit_distance_metrics 에 따라 있습니다 http://en.wikipedia.org/wiki/Edit_distance

:

은

예 : 가장 긴 공통 서브 시퀀스는 추가 및 삭제를 처리하지만 대체는 처리하지 않습니다. Damerau-Levenshtein 거리는 인접 문자의 대체뿐만 아니라 대체를 고려합니다.