텍스트 차이 알고리즘
https://stackoverflow.com/questions/145607
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
두 개의 텍스트 파일을 비교하고 차이를 강조 할 수있는 알고리즘이 필요하며 (더 나은!) 의미있는 방식으로 차이를 계산할 수 있습니다 (두 개의 유사한 파일은 두 개의 비슷한 파일보다 유사한 점수가 있어야합니다. 정상 용어로 정의). 구현하기 쉽지만 그렇지 않습니다.
구현은 C# 또는 Python에있을 수 있습니다.
감사.
다른 팁
Neil Fraser의 코드 및 기사를 살펴 보는 것이 좋습니다.
현재 Java, JavaScript, C ++ 및 Python으로 제공됩니다. 언어에 관계없이 각 라이브러리에는 동일한 API와 동일한 기능이 있습니다. 모든 버전에는 포괄적 인 테스트 하네스가 있습니다.
Neil Fraser : Diff 전략 - 이론 및 구현 노트
보다 difflib. (파이썬)
그것은 다양한 형식의 차이를 계산합니다. 그런 다음 컨텍스트 Diff의 크기를 다른 두 문서의 측정 값으로 사용할 수 있습니까?
현재의 이해는 가장 짧은 편집 스크립트 (SES) 문제에 대한 최상의 솔루션은 Hirschberg 선형 공간 개선 기능을 사용한 Myers "Middle-Snake"메소드라는 것입니다.
Myers 알고리즘은 다음과 같습니다.
E. Myers,``O (ND) 차이 알고리즘과 그 변형 '' '
알고리즘 1, 2 (1986), 251-266.
GNU Diff 유틸리티는 Myers 알고리즘을 사용합니다.
당신이 말하는 "유사성 점수"는 한 시퀀스를 다른 시퀀스로 변환하는 데 필요한 삽입물 또는 삭제 수인 문헌의 "편집 거리"라고합니다.
많은 사람들이 Levenshtein 거리 알고리즘을 인용했지만, 비효율적이기 때문에 최적의 솔루션이 아니라 구현하기 쉽지만 "편집 스크립트를 제공하지 않기 때문에 최적의 솔루션이 아닙니다). "이것은 한 시퀀스를 다른 시퀀스로 변환하는 데 사용될 수 있고 그 반대도 마찬가지입니다.
좋은 myers / hirschberg 구현을 위해 다음을 살펴보십시오.
http://www.ioplex.com/~miallen/libmba/dl/src/diff.c
내부에 포함 된 특정 라이브러리는 더 이상 유지 관리되지 않고 내 지식으로는 Diff.c 모듈 자체가 여전히 정확합니다.
마이크
선보다 더 미세한 세분화가 필요한 경우 Levenshtein 거리를 사용할 수 있습니다. Levenshtein 거리는 비슷한 두 텍스트의 방법에 대한 간단한 측정입니다.
또한이를 사용하여 편집 로그를 추출 할 수 있으며 SO의 편집 기록 페이지와 유사하게 매우 세밀한 차이를 만들 수 있습니다. Levenshtein 거리는 상당히 CPU- 및 메모리 집약적으로 계산할 수 있다고 경고해야하므로 Douglas Leder가 제안한 것처럼 Difflib를 사용하면 더 빠를 것입니다.
cf. 또한 이 답변.
Paradoja가 Levenshtein 거리가 있다고 언급했듯이 많은 거리 지표가 있지만, nysiis 그리고 Soundex. Python 구현 측면에서 나는 사용했습니다 py-editdist 그리고 advas 전에. 둘 다 당신이 한 번의 숫자를 점수로 얻는다는 의미에서 좋습니다. 먼저 Advas를 확인하면 많은 알고리즘을 구현합니다.
언급 한 바와 같이, difflib를 사용하십시오. 출력이 다한 후에는 Levenshtein 거리 그들이 얼마나 다른지에 대한 "가치"를 제공하는 다른 줄의.
당신은 사용할 수 있습니다 가장 긴 공통 후속 (LCS) 문제에 대한 해결책. 이 솔루션을 최적화하는 가능한 방법에 대한 토론도 참조하십시오.
수정 된 파일의 새로운 데이터의 양을 계산하기 위해 다른 기능에 사용한 한 가지 방법이 귀하에게도 효과가있을 수 있습니다.
Diff/Patch 구현 C#이있어 동일한 파일의 구식 및 새 버전의 두 파일을 가져 와서 "차이"를 계산할 수 있지만 일반적인 단어의 의미는 아닙니다. 기본적으로 이전 버전에서 수행 할 수있는 일련의 작업 세트를 계산하여 새 버전과 동일한 내용을 갖도록 업데이트합니다.
처음에 설명 된 기능에이를 사용하기 위해, 새로운 데이터가 새로운 지 확인하기 위해 작업을 간단하게 실행했으며, 기존 파일에서 복사 한 모든 작업, 0 요인이있는 모든 작업 및 새 텍스트를 삽입 한 모든 작업에 대해 (기존 파일에서 발생하지 않았기 때문에 패치의 일부로 배포 됨)는 1 요소가있었습니다. 모든 캐릭터 에게이 공장이 주어졌으며,이 공장은 기본적으로 0과 1의 긴 목록을주었습니다.
내가해야 할 일은 0과 1을 집계하는 것이 었습니다. 귀하의 경우, 내 구현에서는 0과 비교하여 1의 낮은 수가 파일이 매우 유사하다는 것을 의미합니다.
이 구현은 수정 된 파일이 이전 파일에서 사본을 순서대로 삽입 한 경우를 처리하거나 심지어 복제 (즉, 파일의 시작에서 부품을 복사하여 하단 근처에 붙여 넣기)를 처리합니다. 이전 파일에서 동일한 원본 부분의 사본.
계량 사본을 실험하여 첫 번째 사본이 0으로 계산되고 동일한 문자의 후속 사본이 점차 더 높은 요인을 가졌으며, 사본/페이스트 작업에 "새 요인"을 제공하기 위해 점차 더 높은 요인을 가졌지 만 결코 완료 한 적이 없습니다. 프로젝트가 폐기되었습니다.
관심이 있으시면 내 Diff/Patch 코드는 내 Hubversion Repository에서 사용할 수 있습니다.
살펴보십시오 흐린 기준 치수. Soundex, Nysiis 및 Double Metaphone에 대한 빠른 (C로 작성) 기반 알고리즘이 있습니다.
좋은 소개는 다음에서 찾을 수 있습니다. http://www.informit.com/articles/article.aspx?p=1848528
