간단한 소스 제어 시스템을 작성하고 파일 차이에 대해 어떤 알고리즘을 사용해야하는지 궁금합니다.소스 제어 시스템을위한 알고리즘?
라이센스 문제로 인해 기존 소스 코드를 조사하고 싶지 않습니다. MPL 라이선스가 있어야하므로 CVL이나 Mercurial과 같은 기존 시스템을 볼 수 없습니다. 모든 GPL 라이센스가 있습니다.
배경을 제공하기 만하면 폴더에 바이너리 파일이 정말 필요합니다. 하위 폴더는 없으며 모든 파일은 자체 저장소처럼 작동합니다. 일부 권한을 제외하고는 메타 데이터가 없습니다.
전반적으로 매우 단순한데, 내 단일 관심사는 너무 많은 공간을 낭비하지 않고 리비전에서 수정본까지 파일의 차이점을 저장하는 방법입니다. 너무 비효율적이지 않습니다. (아마 모든 X 변경 사항을 전체 버전으로 저장할 수 있습니다. 비디오의 키 프레임과 비슷합니까?)
가장 긴 Common Subsequence 알고리즘은 diff 유사 도구에서 사용되는 기본 메커니즘이며 소스 코드 제어 시스템에서 활용할 수 있습니다.
"역방향 델타"는 가장 최근의 개정판에서 시간상 뒤로 이동해야하기 때문에 저장소에 대한 일반적인 접근 방식입니다.
실제로 (? 허, 홀수) 다른 일이 비슷한 ...에 대해 생각했다
내가 당신을 위해 좋은 답변을하지 않습니다하지만 난 결론에 도달 않았다 내가 있다면 그 파일 diff 도구를 쓰려면, 내가 diffex를 찾기위한 알고리즘을 사용하여 REGEXes가 어떻게 자신의 탐욕과 함께 작동하는지와 같은 기능을 수행 할 것입니다.
DIFF를 저장하는 경우 ... 앞으로 나가는 DIFF를 저장하는 대신 (예 : 원본 파일로 시작한 다음 버전 151으로 작업 할 때 컴퓨터 150과 비교하여) 저장된 당신의 역사에 대한 DIFF는 있지만 최신 파일을 정식 버전으로 저장하십시오. 이런 식으로하면 최신 파일 (아마도 99 %)을 사용하여 작업 할 때마다 최고의 성능을 얻을 수 있습니다.
비록 화석은 GPL이며, 델타 알고리즘은 rsync를 기반으로 here
Patience Diff 사람들에게 이해를 할 가능성이 두 파일 사이의 델타를 찾기위한 좋은 알고리즘 설명되어 있습니다. 이것은 종종 순진한 "가장 긴 공통 서브 시퀀스"알고리즘보다 더 나은 결과를 제공하지만 결과는 주관적입니다.
많은 현대적인 개정 제어 시스템은 각 단계에서 완전한 파일을 저장하고 필요한 경우에만 나중에 실제 차이를 계산합니다. 바이너리 파일 (아마도 몹시 압축할만한 것은 아님)의 경우, 역 델타를 저장하는 것이 궁극적으로 더 효율적일 수 있습니다.
정말 멋집니다. 여전히 LCS 알고리즘 계열의 변형이지만, 아주 훌륭한 개선점입니다. – JasonTrue
흥미 롭습니다! (패드, 패드 ...) –
진 마이어스 (Gene Myers)는 좋은 종이 인 An O(ND) Difference Algorithm and its Variations을 작성했습니다. 시퀀스를 비교할 때 Myers가 그 사람입니다. RCS에 대한 Walter Tichy의 논문도 읽어야합니다. 최신 버전과 차이점을 저장하여 파일 세트를 저장하는 방법을 설명합니다.
델타 (정방향 또는 역방향)를 저장한다는 아이디어는 버전 제어와 관련하여 고전적입니다. 문제는 항상 "델타는 무엇입니까?"
많은 소스 제어 시스템은 본질적으로 가장 긴 공통 서브 시퀀스의 라인 중심 보완과 같은"diff "에 의해 계산 된 델타를 저장합니다. 그러나 특정 문서 유형에 대한 델타를 해당 문서에 특정한 방식으로 계산할 수 있습니다 더 작은 (더 자주 이해할 수있는) 델타를 얻을 수 있습니다.
프로그래밍 언어의 경우 프로그램 구조에 대해 Levenshtein 거리를 계산할 수 있습니다. 다양한 프로그래밍 언어에 대해 본질적으로 이것을 수행하는 도구 세트는 다음에서 찾을 수 있습니다. Smart Differencer
텍스트가 아닌 파일을 저장하는 경우 해당 구조를 활용하여 파일을 계산할 수 있습니다. maller 델타.
물론 최소한의 구현 만하고 싶다면 각 파일 버전의 전체 이미지를 저장하는 것이 쉽습니다. 테라 바이트 디스크는 그 해결책이 작동하지 않는 경우에도 가능합니다. (암묵적으로이 작업을 수행하는 데 사용 된 PDP10 파일 시스템).
흠, 나는 당신의 대답을 더 좋아합니다. 당신은 실제로 당신이 말하는 것을 알고 있습니다. :-P – Jaxidian