C# .net에서 2 바이트 배열의 이진 diff를 생성하는 방법이 있습니까?

Question

두 개의 바이트 배열을 메모리에서 비교하고 차이를 보관할 데이터 구조를 만들어서 바이트 배열 B와 차이를 유지하는 데이터 구조로 바이트 배열 A를 다시 만들 수 있습니다.

바이트 배열은 항상 동일하고 상대적으로 작습니다. 바이트 배열은 일반적으로 1000x1000x32에서 128x128x32 크기의 비트 맵을 나타냅니다.

차이점을 보유하고있는 데이터 구조와 두 번째 바이트 배열을 조합하여 바이트 배열 A를 재구성하는 데 사용되는 속도와 효율성 (CPU 시간에서)은 가장 중요합니다. 차이 객체의 생성이 효율적이지 않은 것은 중요하지 않습니다.

지금 당장 내 해결책은 이진 탐색 + md5 해싱 방식을 사용하여 이미지 내에서 가장 작은 단위 차이 목록을 작성하고 바이트 배열 A 내부의 오프셋 참조를 사용하여 원시 바이트 데이터를 패키징하는 것입니다.

e 이미지 A의 바이트 배열에 대한 해시를 생성하고 이미지 B의 바이트 배열 해시 값과 비교합니다. 일치하지 않으면 이미지를 가로로 나누고 각 블록을 해시 한 다음 이미지 사이에있는 해시를 비교합니다.이 프로세스는 다음과 같습니다. 일치하지 않는 모든 블록이 32x32x32 및/또는 최대 분할 수와 같은 최소 크기를 초과 할 때까지 재귀 적으로 반복됩니다. 블록이 일치하는 것으로 표시되면 더 이상 재귀 적 검색의 일부가 아닙니다. 모든 차이점이 확인되면 변경 사항 목록에 추가되고 해당 목록은 차이 개체가됩니다.

찾고있는 결과를 효율적으로 생성 할 수있는 방법이 있습니까? 아니면 그 일을 할 도서관이 있습니까?

---

참고 :이 (WCF, WPF 및 기타 기술의 수에 대한) 학습 프로젝트입니다

• ,
• 그것은 VNC 스타일의 시스템입니다
- 그래서 이미지를 스냅 샷입니다 LAN 연결을 통해 전송됩니다.
• 바이트 배열 A를 재구성해야하는 이유는 클라이언트가 둘 이상의 서버에 연결할 수 있고 각 서버가 두 개 이상의 창을 제공 할 수 있기 때문에 클라이언트가 30 개 이상의 창을 모니터링/상호 작용할 수 있기 때문입니다.
• 변경 내용이있는 각 창마다 3fps +를 얻고 싶습니다.

Answer 1

실제 크기가 동일 함을 보증한다면이 모든 해싱 및 이진 검색 및 기타 오버 헤드의 중요성을 알 수 없습니다. 루프에서 두 바이트를 간단히 비교할 수 있습니다. 일치하지 않으면 A에 인덱스와 값이 모두 포함 된 diff에 "point"를 추가하십시오. 프로세스를 되돌리려면 이미 색인이 있기 때문에 모든 바이트를 볼 필요가 있습니다.

2 개의 배열이 1 바이트 만 다른 경우에는 인덱스의 Int32를 사용한다고 가정하고 크기가 5 바이트 인 diff 구조로 끝나고 정확히 하나의 반복을 사용하여 변경합니다 B에서 A.일반적으로 프로세스는 diff의 경우 O (n)이고 되돌리기의 경우 O (m)입니다. 여기서 m은 실제로 변경된 총 포인트 수입니다. 나는 데이터 구조에 대한 전문가는 아니지만 좀 더 효율적인 것으로 생각할 수 있을지는 의문입니다.

그래서,이 같은 일이 :

Diff GetDiff(byte[] a, byte[] b) 
{ 
    Diff diff = new Diff(); 
    for (int i = 0; i < a.Length; i++) 
    { 
     if (a[i] != b[i]) 
     { 
      diff.Points.Add(new DiffPoint(i, a[i])); 
     } 
    } 
    return diff; 
} 

// Mutator method - turns "b" into the original "a" 
void ApplyDiff(byte[] b, Diff diff) 
{ 
    foreach (DiffPoint point in diff.Points) 
    { 
     b[point.Index] = point.Value; 
    } 
} 

// Copy method - recreates "a" leaving "b" intact 
byte[] ApplyDiffCopy(byte[] b, Diff diff) 
{ 
    byte[] a = new byte[b.Length]; 
    int startIndex = 0; 
    foreach (DffPoint point in diff.Points) 
    { 
     for (int i = startIndex; i < point.Index; i++) 
     { 
      a[i] = b[i]; 
     } 
     a[point.Index] = point.Value; 
     startIndex = point.Index + 1; 
    } 
    for (int j = startIndex; j < b.Length; j++) 
    { 
     a[j] = b[j]; 
    } 
    return a; 
} 

struct DiffPoint 
{ 
    public int Index; 
    public byte Value; 

    public DiffPoint(int index, byte value) : this() 
    { 
     this.Index = index; 
     this.Value = value; 
    } 
} 

class Diff 
{ 
    public Diff() 
    { 
     Points = new List<DiffPoint>(); 
    } 

    public List<DiffPoint> Points { get; private set; } 
} 

ApplyDiffCopy에 루핑이 많이있다하지만 당신은 그것을 밖으로 작동하는지 당신은 실제로 단지 포인트 당 하나 개의 작업을 수행하는 것을 볼 수 있습니다. 물론 사본이 필요 없으며 B를 변경하려는 경우 실제 차이가 많지 않으면 첫 번째 ApplyDiff 메서드가 매우 빠릅니다.

그리고 분명히 여기서 많은 오류 검사를 수행하지 않았습니다. 좀 더 방어 적으로 버전을 작성하고 싶습니다. (배열 길이 등을 확인하십시오.)

여기에서 가정과 해결하려는 문제를 올바르게 이해했다면 원래 ApplyDiff 메소드는 다음과 같이 될 것입니다. 원본 이미지를 복원하는 가장 빠른 방법입니다.

Answer 2

Crikey! - 조금 복잡합니다. 두 배열의 XOR의 런 길이 인코딩이 잘못되었습니다. 한 번에 인코딩 및 디코딩을 수행하며, 대부분의 값이 0이 되듯이 공간에서 합리적으로 효율적이어야하지만, 필요한 경우 RLE 데이터를 더 압축하십시오.

Answer 3

당신은 BitArray 클래스를 사용 (또는 더를 가속화하기 위해 귀하의 배열의 복사를하지 않도록이 구현 어떻게 볼 리플렉터를 사용)

 byte[] s1 = new byte[] {0,1,2,3,4,5,6}; 
     byte[] s2 = new byte[] {0,1,2,4,4,6,6}; 
     var orig1 = new BitArray(s1); 
     var orig2 = new BitArray(s2); 
     var diff = orig1.Xor(orig2); 
     byte[] diffArray = new byte[s1.Length]; 
     diff.CopyTo(diffArray, 0); // here we have a byte diff array of s1 and s2 

     var reconstruct = orig2.Xor(diff); 
     reconstruct.CopyTo(diffArray, 0); // diffArray is now the same as s1