큰 ASCII 파일 비교

Question

저는 다양한 데이터베이스에서 ETL을 사용하는 회사에서 일합니다. 클라이언트 컴퓨터에 2 개의 전체 히스토리 데이터 세트에 대한 패치를 작성하여 우리 서버로 전송해야합니다. 이 패치는 우리의 소프트웨어에서 호출 할 수 있도록 프로그램 적이어야합니다.

데이터 세트는 간단한 텍스트 파일입니다. 추출을 수행하기 위해 고객의 시스템에서 실행되는 추출 소프트웨어가 있습니다. 추출 파일의 크기는 최대 3GB +까지입니다. Microsoft의 FC.exe를 사용하여 솔루션을 구현했지만 한계가 있습니다.

그때/제거 업데이트, 그 추가 된이 된 레코드를 추출하기 위해 우리 측에 펄에서 구문 분석, 비교 파일을 생성하기 위해 FC를 사용하고 있습니다.

FC는 128자를 초과하지 않는 텍스트 줄만큼 완벽하게 나를 위해 잘 작동합니다. 이 경우 출력은 비교 파일의 다음 줄에 추가되므로 추가/삭제 된 레코드로 나타납니다. 파일을 사전 처리 할 수는 있을지는 모르겠지만 시간이 엄청나게 걸릴 것입니다.

내가 Diffutils의를 사용하여 시도하지만 큰 파일에 대해 불평.

는 또한 패치 프로세스 나 자신을 구현하기 위해 몇 가지 C# 코드 장난 삼아 생각해. 이것은 작은 파일에서도 효과가 있었지만 큰 파일을 처리 할 때 끔찍하게 비효율적이었습니다 (2.8 GB 추출물에서 테스트).

이 패치 파일을 만드는 데 사용할 수있는 좋은 명령 행 유틸리티 또는 C# 라이브러리가 있습니까? ? 그것이 나 자신을 구현하는 데 사용할 수있는 알고리즘이 있습니까? 레코드가 업데이트, 추가 및 삭제 될 수 있음을 기억하십시오. (클라이언트가 레코드를 삭제하는 것이 아니라, 레코드를 삭제한다는 의미입니다.)

명확성을 위해 편집 :

나는 두 개의 서로 다른 시대에서 두 개의 별도의 데이터베이스 추출물을 비교해야합니다. 보통 이것들은 약 1 일 간격으로 떨어져있을 것입니다. 아래의 파일을 감안할 때

:

a 
3 
b 
c 
4 
d 
e 
1 
f 
g 

a 
b 
c 
d 
e 
1 
f 
2 
5 

New.txt (이 분명히 훨씬 더 길고 훨씬 더 넓은 것)

---

Old.txt

예상되는 출력은 b E :

3 added 
4 added 
2 removed 
g added 
5 removed 

Answer 1

다음은 매우 효율적인 솔루션입니다. 대략 O (n)라고 생각하지만 추가 및 삭제 분포에 따라 달라집니다. 메모리 소비는 매우 적지 만 연속적인 추가 및 삭제 횟수에 따라 달라집니다.

제한 :

1. 가 원래 파일에 있던 것과 같은 순서로 패치 라인을 유지하지 않습니다이 알고리즘; 중요한 경우 Dictionary < 문자열 (int >)을 사용하는 것과 같은 작업을 할 수 있습니다. 여기에서 HashSet < 문자열 >을 사용하여 추가 및 제거 된 줄을 추적하는 대신 키가 줄이고 값이 원래 줄 번호입니다.
2. 대상 ("새") 파일은 원본 ("이전") 파일과 다소 유사해야합니다. 특히 변경되지 않은 모든 줄은 원본과 대상에서 같은 순서로 있어야합니다. 이 조건이 충족되지 않으면 알고리즘이 잘못 작동합니다.
3. 각 행은 인접한 행과 관련하여 고유해야합니다. 여기서 "근"은 소스와 목표 사이에 변경되지 않은 가장 가까운 행 사이를 의미합니다. 이 조건이 충족되지 않으면 알고리즘에 변경 내용이 누락됩니다.
4. 이 구현은 수정 된 행을 고려하지 않습니다. 나는 당신이 == 비교를 == 비교를 바꾸어서 추가 할 수 있다고 생각한다. 두 개의 라인이 "같은"라인이라는 것을 알아 내는데 사용하는 연산과 같고, 내용 변경이있는 "같은"라인이라면 패치에 쓰는 것이다.

알고리즘은 "추가"및 "제거 된"버퍼 쌍을 사용하여 추가되거나 제거 된 행이 파일을 통과 할 때 추적합니다. 파일 사이에 일치하지 않는 라인은 "추가됨"또는 "제거됨"으로 잠정적으로 표시됩니다. 파일 중 하나에서 임시로 표시된 행이 발견되면 ("제거 된"행이 대상 파일에서 발견되거나 "추가 된 행"이 소스 파일에서 발견 된 경우), 이는 모든 행이 다른 버퍼가 거기에 속해 있으므로 다른 버퍼가 패치 파일로 플러시 된 다음 일치하는 줄이 발견 된 파일에서 한 줄을 앞당겨 읽습니다. 예를 들어

:

var path = /* path */; 
var sourcePath = Path.Combine(path, "source.txt"); 
var targetPath = Path.Combine(path, "target.txt"); 
var expectedPath = Path.Combine(path, "expected.txt"); 
var rnd = new Random(10); 

using(var sourceWriter = new StreamWriter(sourcePath)) 
using(var targetWriter = new StreamWriter(targetPath)) 
using(var expectedWriter = new StreamWriter(expectedPath)) 
{ 
    var limit = 10.0 * 100000; 
    for (int i = 0; i < limit; i++) 
    { 
     if(i % 10000 == 0) Console.Write("{0:P0} ...", i/limit); 
     var guid = Guid.NewGuid().ToString(); 
     var r = rnd.Next(0,10); 
     var removed = 3; 
     var added = 6; 
     if(r >= 0 && r < removed) 
     { 
      sourceWriter.WriteLine(guid); 
      expectedWriter.WriteLine(guid + " 0"); 
     } 
     else if(r >= removed && r < added) 
     { 
      targetWriter.WriteLine(guid); 
      expectedWriter.WriteLine(guid + " 1"); 
     } 
     else if(r >= added) 
     { 
      sourceWriter.WriteLine(guid); 
      targetWriter.WriteLine(guid);   
     } 
    } 
} 

어떤 실수 나 문제를 참조하십시오

public void Diff(
    string sourcePath, 
    string targetPath, 
    string patchPath, 
    string addedSuffix, 
    string removedSuffix) 

{ 
    using(var sourceReader = new StreamReader(sourcePath)) 
    using(var targetReader = new StreamReader(targetPath)) 
    using(var patchWriter = new StreamWriter(patchPath, append:false)) 
    { 
     var sourceLine = sourceReader.ReadLine(); 
     var targetLine = targetReader.ReadLine(); 

     var added = new HashSet<string>(); 
     var removed = new HashSet<string>(); 

     do{ 
      if(sourceLine == targetLine) 
      { 
       sourceLine = sourceReader.ReadLine(); 
       targetLine = targetReader.ReadLine(); 
      } 
      else 
      { 
       if(removed.Contains(targetLine)) 
       { 
        // Found targetLine in tentatively removed lines, so it wasn't actually removed. 
        removed.Remove(targetLine); 
        // Since we found something we thought had been removed, we know that all tentatively added lines actually are new. 
        Flush(patchWriter, added, addedSuffix);    
        added.Clear(); 

        targetLine = targetReader.ReadLine();    
       } 
       else if(added.Contains(sourceLine)) 
       { 
        // Found sourceLine in tentatively added lines, so it wasn't actually added. 
        added.Remove(sourceLine); 
        // We found something we thought had been added, so all candidates for removal should actually be removed. 
        Flush(patchWriter,removed, removedSuffix); 
        removed.Clear(); 

        sourceLine = sourceReader.ReadLine();    
       } 
       else 
       { 
        // Source and target don't match, so we assume that the source was removed and the target was added. 
        // If we're wrong, we'll clean it up when we come across the line later on. 
        removed.Add(sourceLine); 
        added.Add(targetLine); 
        sourceLine = sourceReader.ReadLine();    
        targetLine = targetReader.ReadLine();    
       }  
      } 
     } while(sourceLine != null || targetLine != null); 

     Flush(patchWriter, added, addedSuffix); 
     Flush(patchWriter, removed, removedSuffix); 
    } 
} 

public void Flush(StreamWriter writer, IEnumerable<string> lines, string suffix) 
{ 
    foreach (var line in lines.Where (l => l != null)) 
    { 
     writer.WriteLine("{0} {1}", line.Trim(), suffix); 
    } 
} 

여기에 몇 가지 내가 테스트 파일을 생성하는 데 사용되는 코드입니다 : 여기

 
Source Target Added Removed 
A-------A  _  _ 
B-------X  +X  +B 
C-------B  Flush X -B 
D--\ \-C  _  _ 
E-\ \---E  +E  +D 
F \----F  -E  Flush D 

코드인가? 이게 니가 찾고있는거야?

Answer 2

글쎄, 당신은이 개 텍스트 파일을 비교하고, 각각의 하나는 임의의 순서로 필요하지 않은 항목이, 나는이 권리를 이해한다면 나는 그것에 어떤 형식을 가지고 항목을 기대하고 있습니다 , 당신이 정말로해야하는 것이 : *이 나타내는 항목 의 시작은 @ 항목 의 끝을 나타냅니다 그래서 OLD.TXT *는 @의 * B 형 @ * C @ 등 ... 원유 "알고리즘"이 될 것입니다 : 1) NEW의 복사, 전화 확인은) OLD 3.0에서 항목을 얻을 해당 항목에 추가 스캔) 2를 추가했다. STILLEXISTS라는 파일에 항목을 저장하고 ADDED 파일에서 해당 항목을 삭제하십시오. 3.1) 항목이 ADDED에 없으면 DELETED라는 파일에 저장하고 OLD에서 다음 항목 가져 오기 4)이 작업이 끝나면 추가, 삭제 및 보너스 항목이있는 파일이 각각 3 개 있습니다. "파일, 모두 한 번에 패스) 희망, 나는 그것을 올바르게 이해하고, 이것은 당신을 도울 수 있습니다.