두 개의 파일이 주어지면 각 파일의 각 줄에 대해 수행 방법comm그리고diff결정하다
- 이 줄이 다른 파일에도 나타납니까?
- 그렇다면 두 파일 모두에서 동일하게 표시됩니까, 아니면 다르게 표시됩니까?
각 파일의 줄 사이의 순서를 고려하십니까?
diff"두 파일에서 발생하지만 다른 줄" 또는 "한 파일에서는 발생하지만 다른 파일에서는 발생하지 않음"을 확인하는 방법은 무엇입니까?
두 파일을 빼는 데 둘 다 사용되는 경우 comm어떻게 다르며 어떻게 다릅니까 ?diff
감사해요.
(일부 초등 수학에 관심이 없다면 다음을 무시하십시오. 위의 내용은 제 질문에 관한 한 독립적입니다.)
나는 추측한다:
수학에서 집합은 요소들 사이에 순서를 부여하지 않습니다. (이런 집합을 순서집합이라고 부르는데, 이는 다른 개념입니다)
"S1-S2", 즉 두 집합 S1과 S2에 대한 차이 집합 연산은 첫 번째 집합의 요소 집합을 생성하지만 두 번째 집합의 요소 집합은 생성하지 않습니다.
두 세트의 교집합을 찾을 때 요소가 두 세트 모두에서 고려되는 경우 각 세트에서 해당 요소가 나타나는 위치는 중요하지 않습니다.
파일에 차이점을 설정하는 것과 같은 작업도 있습니다.commcoreutils에서그리고diffdiffutils에서. 그러나 파일을 줄 집합으로 생각할 수는 없지만 줄이 자연스럽게 줄 번호에 따라 정렬되기 때문에 정렬된 줄 집합으로 생각할 수 있습니다.
또한 다양한 방식으로 작업합니다 comm.diff
개념적 수준(입력 및 출력 수준)에서 각각 수행되고 있는 작업 comm과 수행하려는 작업은 무엇입니까 diff? 수학적으로도 설명할 수 있다면 더 명확할 수 있습니다(주문 세트에 대한 기본 지식이 필요할 수도 있습니다). 구현 수준에서 설명을 기대하지는 않지만 도움이 될 수 있습니다(일부 버전 제어 및 백업 소프트웨어는 증분 복사에 동일하거나 유사한 알고리즘을 사용함).
감사해요.
답변1
여기에 명시된 바와 같이; https://en.m.wikipedia.org/wiki/Diff
"diff 연산은 가장 긴 공통 부분 수열 문제를 푸는 데 기반을 두고 있습니다."
의견에서 지적했듯이 약간 다른 변형(diff, gdiff, vimdiff, git-diff, rdiff-backup 등)을 가진 여러 구현이 있습니다. LCS 위키 페이지에는 귀하가 요청한 수학적 정의가 있습니다. 2개의 정렬된 세트에서 모든 LCS를 빼면 그 차이가 나머지가 됩니다.
답변2
구현의 일반적인 문제
diff는 삭제 또는 삽입이 감지된 후 다음 공통 텍스트 블록을 찾는 것입니다.
유용한 결과를 얻으려면 구현 시 공통 코드 한 줄 이후에 재동기화를 감지할지, 아니면 더 많은 공통 코드가 있어야 하는지 결정해야 합니다.
그 이유는 삽입 후에 이미 존재하는 행과 동일한 단일 행이 삽입에 포함될 수 있기 때문입니다. 단일 동일한 행이 재동기화를 감지하는 데 사용되는 경우 diff 출력은 예상했던 것과는 다른 여러 삽입에 플래그를 지정합니다.
하지만 발견가장 긴 공통 문자열알고리즘이 아니라 문제이고 문제에 대한 솔루션(알고리즘)이 여러 가지가 있습니다.
find이 명령은 Douglas McIllroy가 1974년에 UNIX용으로 작성한 원래 알고리즘을 사용합니다 .
또 다른 유명하지만 완전히 다른 구현(다른 알고리즘을 사용)은 1980년대 후반에 누군가가 GNU용으로 작성했습니다.
재동기화 알고리즘이 완전히 다르기 때문에 두 구현은 경우에 따라 서로 다른 결과를 제공하는 것으로 알려져 있습니다.
diffUNIX가 최소 코드 크기에 대한 원래 최적화를 사용하는 한 GNU는 diffUNIX보다 빨랐 diff지만 몇 년 전 저는 diffUNIX 구현의 최적화를 코드 크기에 관계없이 가능한 한 빠르게 변경했습니다. 이제 일반적인 용도로 UNIX를 사용하는 한 파일 크기에 따라 UNIX가 diffGNU보다 빠릅니다.diff
Douglas McIllroy가 사용한 알고리즘은 그의 대학 홈페이지에 문서화되어 있습니다.http://www.cs.dartmouth.edu/~doug/diff.pdf
흥미롭게도 diff를 찾는 반대 과정은 diff 출력을 사용하여 원본 파일을 패치하여 파일의 새 버전을 얻는 것입니다.
SCCS이 문제에 대한 첫 번째 해결책은 Bell Labs의 Marc J. Rochkind가 1972년에 발명한 프로그램이었습니다. 그의 설명을 참조하세요.http://sccs.sourceforge.net/sccs_invention.htmlsccs 홈페이지에서:http://sccs.sourceforge.net/diff의 필요성 으로 인해 sccs1974년 이전에는 오래되었지만 덜 영리한 구현이 있었습니다 diff.
가능한 모든 버전의 스트림을 단일 파일에 포함할 수 있으므로 파일 패치를 피하는 SCCS매우 영리한 파일 형식을 사용합니다 . weave파일에서 단일 임의 버전을 추출하면 weave추출하려는 버전에 따라 시간이 달라지지 않으며 항상 동일한 속도로 완료됩니다.