자체 게임에서 Diff를 이길 수 있습니까?

https://stackoverflow.com/questions/1020925

06-07-2019
|

문제

두 파일을 비교하는 데 사용할 적절한 알고리즘을 찾고 있습니다. 나는 내가 더 잘할 수 있다고 생각합니다 diff 일부 추가 제약으로 인해.

내가 가지고있는 것은 각각 파일 목록을 포함하는 두 개의 텍스트 파일입니다. 그들은 두 번 다른 시스템의 모든 파일의 스냅 샷입니다. 두 개의 스냅 샷 사이에 어떤 파일이 추가되거나 삭제되었는지 알아 내고 싶습니다.

나는 사용할 수있다 diff 이 파일을 비교하기 위해서는 원하지 않습니다.

diff 그룹 변경을 시도하여 파일의 청크가 변경된 것을 찾으십시오. 나는 변경된 줄 목록 만 찾고 있으며, 가장 긴 공동체를 찾거나 그와 같은 것을 찾는 것보다 훨씬 간단한 문제가되어야합니다.
일반화 된 DIFF 알고리즘입니다 O (Mn) 런타임 또는 공간에서. 나는 더 좋아하는 것을 찾고 있습니다 O (M+N) 시간과 o (1) 우주에서.

문제에 대한 제약은 다음과 같습니다.

파일 목록은 두 파일 모두에서 동일한 순서입니다. 그들은 ~ 아니다 반드시 알파벳 순서로, 그들은 동일합니다. 상대적인 주문하다.
대부분의 경우 목록간에 차이가 없습니다. 차이가있는 경우 일반적으로 소수의 새/삭제 된 파일 만 있습니다.
"이 전체 디렉토리가 삭제되었습니다"또는 "100-200 행이 새로워졌습니다"라는 말과 같이 결과를 함께 그룹화 할 필요가 없습니다. 다른 라인을 개별적으로 나열 할 수 있습니다.

나는 이것이 두 개의 정렬 된 목록을 가지고 있고 두 목록 사이의 차이점을 파악하는 문제와 동일하다고 생각합니다. 히치는 목록 항목이 반드시 알파벳순으로 정렬되지는 않으므로 한 항목이 다른 항목보다 "더 큰 "지 알 수 없습니다. 두 목록에있는 파일이 동일한 순서가 될 것임을 알고 있습니다.

가치가있는 것에 대해, i 이전에 게시되었습니다 이 질문은 메타 필터에게 물어보십시오 몇 년 전. 몇 가지 잠재적 답변에 미리 응답 할 수 있습니다.

대답: 이 문제를 호출합니다 가장 긴 일반적인 후속.

응답: 간단한 알고리즘이 실행되기 때문에 가장 긴 공통 후속을 피하려고합니다. O (Mn) 시간/공간과 더 나은 공간은 복잡하고 "휴리스틱"입니다. 내 직관은 추가 제약으로 인해 선형 시간 알고리즘이 있다고 말합니다.

대답: 알파벳순으로 정렬 한 다음 비교하십시오.

응답: 그럴 것입니다 o (m log m+n log n), 그것은보다 나쁩니다 O (M+N).

해결책

이것은 그다지 아닙니다 O(1) 메모리, 변경 수 순서의 메모리 요구 사항이지만 O(m+n) 실행 시간.

본질적으로 주어진 라인에서 모든 이전 라인의 차이를 알고있는 버퍼링 스트리밍 알고리즘입니다.

// Pseudo-code:
initialize HashMap<Line, SourceFile> changes = new empty HashMap
while (lines left in A and B) {
    read in lineA from file A
    read in lineB from file B

    if (lineA.equals(lineB)) continue

    if (changes.contains(lineA) && changes.get(lineA).SourceFile != A) {
         changes.remove(lineA)
    } else {
         changes.add(lineA, A)
    }

    if (changes.contains(lineB) && changes.get(lineB).SourceFile != B) {
         changes.remove(lineB)
    } else {
         changes.add(lineB, B)
    }
}

for each (line in longerFile) {
    if (changes.contains(line) && changes.get(line).SourceFile != longerFile) {
         changes.remove(line)
    } else {
         changes.add(line, longerFile)
    }
}

Lines in the HashMap from SourceFile == A have been removed
Lines in the HashMap from SourceFile == B have been added

이것은 파일이 동일한 상대 순서로 나열되어 있다는 사실에 크게 의존합니다. 그렇지 않으면 메모리 요구 사항이 변경 수보다 훨씬 클 것입니다. 그러나이 순서로 인해이 알고리즘은 2 * numchanges보다 훨씬 더 많은 메모리를 사용해서는 안됩니다.

다른 팁

하나의 파일을 읽고 각 파일 이름을 a에 넣습니다 해시 세트-와 유사한 데이터 구조 O(1) 추가 및 O(1) 구현이 포함되어 있습니다.

그런 다음 초 파일을 읽고 해시 세트에 대해 각 파일 이름을 확인하십시오.

총 알고리즘 파일 하나의 길이가있는 경우 m 두 번째 파일의 길이가 있습니다 n ~이다 O(m+n) 필요에 따라.

참고 :이 알고리즘은 데이터 세트가 물리적 메모리에 편안하게 맞는 것으로 가정합니다.

데이터 세트가 메모리에 쉽게 맞지 않으면 일부 변형을 사용하여 조회를 구현할 수 있습니다. B- 트리 디스크 페이징으로. 그러면 복잡성이 될 것입니다 O(mlog m) 처음에 설정하고 O(n log m) 서로 파일을 비교합니다.

이론적 관점에서, 두 줄 사이의 편집 거리를 비교하는 (여기서 '문자'가 파일 이름 인 재미있는 언어로 된 문자열이 있기 때문에 o (m+n)를 만들 수 없습니다. 그러나 여기에는 단순화가 있습니다.

귀하의 경우 알고리즘 구현 (실수가 포함되어 있어야 함) :

# i[0], i[1] are undoable iterables; at the end they both return Null

while (a = i[0].next()) && (b = i[1].next()) :    # read one item from each stream
    if a != b:                 # skip if they are identical
        c = [[a],[b]]          # otherwise, prepare two fast arrays to store difference
        for (w = 1; ; w = 1-w) # and read from one stream at a time
             nxi = Null        
             if (nx = i[1-w].next()) in c[w]:  # if we read a new character that matches
                  nxi = c[w].index(nx)          
             if nx is Null: nxi = -1           # or if we read end of stream
             if nxi is not Null:               # then output that we found some diff
                 for cc in c[1-w]: yield cc              # the ones stored 
                 for cc in c[w][0:nxi-1]: yield cc       # and the ones stored before nx
                 for cc in c[w][nxi+1:]: i[w].undo(cc)   # about the remainder - put it back
                 break                         # and return back to normal cycle
 # one of them finished
 if a: yield a
 if b: yield b
 for ci in i: 
     while (cc = ci.next()): yield cc

내가 빠른 배열이라고 부르는 데이터 구조가 있습니다. 아마 HashSet 사물, 그러나 질서를 기억하는 것들. 그들 안에 추가와 조회가 있어야합니다 O(log N), 그러나 메모리 사용 O(N).

이것은 메모리 나주기를 넘어 사용하지 않습니다 O(m+n) 차이점을 찾는 것 외에. 모든 '차이 블록'에 대해 - m consequtive 항목을 빼고 N을 추가하는 것으로 설명 할 수있는 작업에 대해 - 이것은 필요합니다. O(M+N) 기억과 ~~O(MN)~~ O(Mlog N+Nlog M) 지침. 블록이 완료된 후에 메모리가 해제되므로 실제로 작은 변경 사항 만있는 경우에는 많은 일이 아닙니다. 물론 최악의 성능은 일반적인 방법만큼 나쁘다.

실제로 정렬 시간의 로그 계수 차이는 아마도 중요하지 않을 것입니다. sort 몇 초 안에 수십만 개의 줄을 정렬 할 수 있습니다. 따라서 실제로 코드를 작성할 필요는 없습니다.

sort filelist1 > filelist1.sorted
sort filelist2 > filelist2.sorted
comm -3 filelist1.sorted filelist2.sorted > changes

나는 이것이 반드시 가장 빠른 해결책이라고 주장하는 것은 아닙니다. Ben S는 받아 들여진 답변입니다 적어도 N의 일부 가치보다 적어도 나일 것입니다. 그러나 그것은 확실히 가장 간단합니다. 그것은 많은 파일로 확장 될 것이며 (Google의 백업 작업을 담당하는 사람이 아니라면) 숫자에 대해 충분히 빠를 것입니다. 당신이 가진 파일의.

사전 (해시 맵)이 O (N) 공간이고 O (1) 삽입/조회임을 인정하면이 솔루션은 시간과 공간 모두에서 O (M+N)이어야합니다.

from collections import defaultdict
def diff(left, right):
    left_map, right_map = defaultdict(list), defaultdict(list)
    for index, object in enumerate(left): left_map[object] += [index]
    for index, object in enumerate(right): right_map[object] += [index]
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left_map[right[j]]:
            i2 = left_map[right[j]].pop(0)
            if i2 < i: continue
            del right_map[right[j]][0]
            for i in range(i, i2): print '<', left[i]
            print '=', left[i2], right[j]
            i, j = i2 + 1, j + 1
        elif right_map[left[i]]:
            j2 = right_map[left[i]].pop(0)
            if j2 < j: continue
            del left_map[left[i]][0]
            for j in range(j, j2): print '>', right[j]
            print '=', left[i], right[j2]
            i, j = i + 1, j2 + 1
        else:
            print '<', left[i]
            i = i + 1
    for j in range(j, len(right)): print '>', right[j]

>>> diff([1, 2, 1, 1, 3,    5, 2,    9],
...      [   2, 1,    3, 6, 5, 2, 8, 9])
< 1
= 2 2
= 1 1
< 1
= 3 3
> 6
= 5 5
= 2 2
> 8
= 9 9

좋아, 약간 부정 행위 list.append 그리고 list.__delitem__ O (1)가 링크 된 목록이라면 실제로는 사실이 아닙니다 ...하지만 어쨌든 그 아이디어입니다.

Ephemient의 답변을 개선하면 변경 사항이있을 때만 추가 메모리를 사용합니다.

def diff(left, right):
    i, j = 0, 0

    while i < len(left) and j < len(right):
        if left[i] == right[j]:
            print '=', left[i], right[j]
            i, j = i+1, j+1
            continue

        old_i, old_j = i, j
        left_set, right_set = set(), set()

        while i < len(left) or j < len(right):
            if i < len(left) and left[i] in right_set:
                for i2 in range(old_i, i): print '<', left[i2]
                j = old_j
                break

            elif j < len(right) and right[j] in left_set:
                for j2 in range(old_j, j): print '>', right[j2]
                i = old_i
                break

            else:
                left_set .add(left [i])
                right_set.add(right[j])
                i, j = i+1, j+1

    while i < len(left):
        print '<', left[i]
        i = i+1

    while j < len(right):
        print '>', right[j]
        j = j+1

코멘트? 개량?

나는 메모리가 부족하지 않고 큰 파일을 차단하기위한 프로그램을 겪었지만 내 목적에 맞는 것은 발견되지 않았습니다. 패치를 위해 Diffs를 사용하는 데 관심이 없습니다 (그렇다면 아마 사용합니다. rdiff librdiff에서), 그러나 diffs를 시각적으로 검사하기 위해, 아마 dwdiff --diff-input (Unified Diff 형식을 읽습니다)와 어쩌면 어쨌든 단어를 수집 할 수 있습니다.

(일반적인 사용 사례 : 큰 텍스트 코퍼스를 처리하는 데 사용하는 NLP 도구가 있습니다. 한 번 실행하고 122760246 줄 길이의 파일을 얻고 도구를 변경하고 다시 실행하고 파일을 얻습니다. 마다 백만 행, 2 개의 삽입 및 삭제 또는 한 줄만이 다릅니다.)

아무것도 찾을 수 없었기 때문에 약간의 대본을 만들었습니다. https://github.com/unhammer/diff-large-files - 작동합니다 (DWDIFF는 입력으로 받아들입니다), 충분히 빠릅니다 (파이프 라인에서 종종 실행되는 XZ 프로세스보다 빠릅니다). 가장 중요한 것은 메모리가 부족하지 않는 것입니다.

파일 목록을 두 세트로 읽고 어느 목록에 고유 한 파일 이름을 찾을 것입니다.

파이썬에서 :

files1 = set(line.strip() for line in open('list1.txt'))
files2 = set(line.strip() for line in open('list2.txt'))
print('\n'.join(files1.symmetric_difference(files2)))

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow