두 버전을 저장하지 않고 얼마나 많은 데이터가 변경되었는지 확인하는 방법

Question

파일을 생성하는 일괄 처리 작업을 두 번 실행하는 사이에 (텍스트) 파일의 데이터가 얼마나 변경되었는지 확인하고 싶습니다. 파일이 매우 커지므로 이전 파일을 저장하지 않고 새 파일로 diff를 만드는 것을 피하고 싶습니다. 변경된 정확한 바이트 수에 대해별로 신경 쓰지 않아도 충분합니다. 실행 사이에 파일 크기가 다를 수 있습니다. 거기에 알고리즘이 있습니까?

Answer 1

이 작업을 수행하는 일반적인 알고리즘을 알지 못합니다. 하지만 당신의 제약 조건을 감안할 때, 나는 매우 간단하다고 생각합니다.

CSV의 모든 행에 대해 32 비트 해시를 계산하고 정렬 된 배열에 저장합니다. 그런 다음 해시를 비교합니다. 해시 중 10 %가 변경된 경우 파일의 10 %가 변경되었을 가능성이 있습니다. (행의 백분율로)

이 값이 너무 크면 각 CSV 행의 32 비트 해시를 계산하지만 각 해시의 마지막 8 비트는 막대 그래프에 저장합니다. 예 : 마지막 바이트가 0 인 10 개의 해시가있는 경우 hist [0] = 10입니다. 그러면 변경된 행의 수를 대략 계산할 수 있습니다.

이 구조체는 256 개의 32 비트 숫자처럼 매우 작습니다. (약 1k)

행이 바뀌면 다른 버킷으로 이동하지만 해당 버킷의 일부 행이 나와서 들어간 행을 마스킹 할 수 있기 때문에 완벽하지 않습니다. 이는 해시 충돌에 문제가 있습니다. 더 많은 비트를 저장할수록 해시 충돌이 줄어들 기 때문에 데이터 구조가 더 커지지만 정확 해집니다.

히스토그램에서 사용하는 해시 비트 수를 늘리면 해시 충돌 확률을 높이거나 낮출 수 있습니다. 예를 들어 각 해시의 하위 12 비트를 사용하면 해시 충돌이 훨씬 적습니다. 데이터 구조는 4k 32 비트 숫자 또는 16k가 될 수 있습니다.

Answer 2

완성 된 아이디어처럼 보이지 않지만 더 나은 아이디어를 가리킬 수 있습니다.

초기 파일을 블록으로 나눕니다. 모든 블록의 해시를 계산합니다. 이 해시를 저장하십시오.

새 파일은 동일한 블록 크기를 사용하지만 다른 (적응 형) 방식으로 블록으로 분할합니다. 첫 번째 줄부터 블록부터 시작하십시오. 알려진 해시가 저장되어 있고 block_size 행을 아래로 이동합니다. 그렇지 않은 경우 해시를 저장하지 말고 1 행을 아래로 이동하십시오.

새 파일이 모두 처리되면 두 개의 해시 시퀀스에 대해 diff 알고리즘을 시도 할 수 있습니다.

대략 변경되거나 삭제 된 콘텐츠의 양을 나타냅니다. 콘텐츠를 추가하려면 두 번째 시퀀스에 무언가를 추가해야 할 것입니다.