0

マトリックス内の1と0のみで構成されるデータに対して可能な限り最高の圧縮を実現しようとしています。

私が何を意味するかを示すために、ここにサンプル6x6マトリックスがあります。

1,0,0,1,1,1
0,1,0,1,1,1
1,0,0,1,0,0
0,1,1,0,1,1
1,0,0,0,0,1
0,1,0,1,0,1

それをできるだけ小さな文字列またはバイト配列に圧縮したいと思います。ただし、圧縮する必要のある行列は大きくなります（常に4096 x 4096の1と0）。

かなり圧縮される可能性があると思いますが、どうすればよいかわかりません。答えとして最高の圧縮をマークします。パフォーマンスは重要ではありません。

4

4 に答える 4

1

うーん...問題のドメインを知らなければ、できるだけ小さくすることは実際には不可能です。

一般的なアプローチは次のとおりです。

  1. バイトや文字などではなくビットを使用して、配列内の1と0を表します。
  2. 汎用のロスレス圧縮アルゴリズムを使用して圧縮します。最も一般的な2つは、ハフマン符号化とある種のLZWです。

ハフマンは、データの可能な限り最高の圧縮を提供することが数学的に証明できます。キャッチは、データを解凍するために、元のデータと同じ大きさのハフマンツリーも必要です。LZWは、ほとんどの入力でハフマンと同等の圧縮（数パーセント以内）を提供しますが、テキストなどの繰り返しセグメントを持つデータで最高のパフォーマンスを発揮します。圧縮アルゴリズムの実装は簡単に入手できるはずです（GZIPはLZWの以前のわずかに最適ではないバージョンであるLZ77を使用します）。

最新のアルゴリズムを使用した圧縮アルゴリズムの適切な実装は、7zip.orgにアクセスしてください。これはオープンソースであり、DLLを使用したC APIがありますが、.Netインターフェイスを作成する必要があります（誰かがすでに作成している場合を除く）。

非一般的なアプローチ：これは、データの既知の特性を中継します。例：ほとんどのデータがゼロであることがわかっている場合は、1つの座標のみをエンコードできます。データに1と0のパッチが含まれている場合、それらはRLEまたはアルゴリズムの2次元バリアントでエンコードできます。

于 2012-11-06T10:03:31.513 に答える
1

データが実際にはバイナリであっても、文字列を他の文字列に圧縮したいと思います。最適な圧縮アルゴリズムが何であるかはわかりませんが（データによって異なります）、入力テキストをビットに変換し、これらを圧縮してから、base-64エンコーディングを使用して圧縮バイトを文字列に再度変換できます。これにより、文字列から文字列に移動しながら、選択した圧縮アルゴリズムを適用できます。

.NET Frameworkは、DeflateStreamバイトのストリームを圧縮できるようにするクラスを提供します。Stream最初のステップは、テキスト形式の読み取りと書き込みを可能にするカスタムを作成することです。より良い名前がないため、私はそれに名前を付けましたTextStream。問題を単純化するために\n、（の代わりに）行末として使用することに注意してください\r\n。

class TextStream : Stream {

  readonly String text;

  readonly Int32 bitsPerLine;

  readonly StringBuilder buffer;

  Int32 textPosition;

  // Initialize a readable stream.
  public TextStream(String text) {
    if (text == null)
      throw new ArgumentNullException("text");
    this.text = text;
  }

  // Initialize a writeable stream.
  public TextStream(Int32 bitsPerLine) {
    if (bitsPerLine <= 0)
      throw new ArgumentException();
    this.bitsPerLine = bitsPerLine;
    this.buffer = new StringBuilder();
  }

  public override Boolean CanRead { get { return this.text != null; } }

  public override Boolean CanWrite { get { return this.buffer != null; } }

  public override Boolean CanSeek { get { return false; } }

  public override Int64 Length { get { throw new InvalidOperationException(); } }

  public override Int64 Position {
    get { throw new InvalidOperationException(); }
    set { throw new InvalidOperationException(); }
  }

  public override void Flush() {
  }

  public override Int32 Read(Byte[] buffer, Int32 offset, Int32 count) {
    // TODO: Validate buffer, offset and count.
    if (!CanRead)
      throw new InvalidOperationException();

    var byteCount = 0;
    Byte currentByte = 0;
    var bitCount = 0;
    for (; byteCount < count && this.textPosition < this.text.Length; this.textPosition += 1) {
      if (text[this.textPosition] != '0' && text[this.textPosition] != '1')
        continue;
      currentByte = (Byte) ((currentByte << 1) | (this.text[this.textPosition] == '0' ? 0 : 1));
      bitCount += 1;
      if (bitCount == 8) {
        buffer[offset + byteCount] = currentByte;
        byteCount += 1;
        currentByte = 0;
        bitCount = 0;
      }
    }
    if (bitCount > 0) {
      buffer[offset + byteCount] = currentByte;
      byteCount += 1;
    }
    return byteCount;
  }

  public override void Write(Byte[] buffer, Int32 offset, Int32 count) {
    // TODO: Validate buffer, offset and count.
    if (!CanWrite)
      throw new InvalidOperationException();

    for (var i = 0; i < count; ++i) {
      var currentByte = buffer[offset + i];
      for (var mask = 0x80; mask > 0; mask /= 2) {
        if (this.buffer.Length > 0) {
          if ((this.buffer.Length + 1)%(2*this.bitsPerLine) == 0)
            this.buffer.Append('\n');
          else
            this.buffer.Append(',');
        }
        this.buffer.Append((currentByte & mask) == 0 ? '0' : '1');
      }
    }
  }

  public override String ToString() {
    if (this.text != null)
      return this.text;
    else
      return this.buffer.ToString();
  }

  public override Int64 Seek(Int64 offset, SeekOrigin origin) {
    throw new InvalidOperationException();
  }

  public override void SetLength(Int64 length) {
    throw new InvalidOperationException();
  }

}

次に、を使用して圧縮および解凍するためのメソッドを記述できますDeflateStream。非圧縮入力は質問で提供したような文字列であり、圧縮出力はbase-64でエンコードされた文字列であることに注意してください。

String Compress(String text) {
  using (var inputStream = new TextStream(text))
    using (var outputStream = new MemoryStream()) {
      using (var compressedStream = new DeflateStream(outputStream, CompressionMode.Compress))
        inputStream.CopyTo(compressedStream);
      return Convert.ToBase64String(outputStream.ToArray());
    }
}

String Decompress(String compressedText, Int32 bitsPerLine) {
  var bytes = Convert.FromBase64String(compressedText);
  using (var inputStream = new MemoryStream(bytes))
    using (var outputStream = new TextStream(bitsPerLine)) {
      using (var compressedStream = new DeflateStream(inputStream, CompressionMode.Decompress))
        compressedStream.CopyTo(outputStream);
      return outputStream.ToString();
    }
}

それをテストするために、私はランダムな文字列を作成する方法を使用しました（固定シードを使用して常に同じ文字列を作成します）：

String CreateRandomString(Int32 width, Int32 height) {
  var random = new Random(0);
  var stringBuilder = new StringBuilder();
  for (var i = 0; i < width; ++i) {
    for (var j = 0; j < height; ++j) {
      if (i > 0 && j == 0)
        stringBuilder.Append('\n');
      else if (j > 0)
        stringBuilder.Append(',');
      stringBuilder.Append(random.Next(2) == 0 ? '0' : '1');
    }
  }
  return stringBuilder.ToString();
}

ランダムな4,096x4,096文字列を作成すると、非圧縮サイズは33,554,431文字になります。これは2,797,056文字に圧縮され、元のサイズの約8％に縮小されます。

base-64エンコーディングをスキップすると、圧縮率がさらに向上しますが、出力は文字列ではなくバイナリになります。入力をバイナリと見なすと、確率が0と1のランダムデータに対して実際に次の結果が得られます。

  入力バイト：4,096 x 4,096 / 8 = 2,097,152
  出力バイト：2,097,792
  圧縮後のサイズ：100％

単純にバイトに変換する方が、デフレートを使用して変換するよりも優れています。ただし、ランダム入力を使用しますが、25％0と75％1を使用すると、次の結果が得られます。

  入力バイト：4,096 x 4,096 / 8 = 2,097,152
  出力バイト：1,757,846
  圧縮後のサイズ：84％

どの程度の収縮がデータを圧縮するかは、実際にはデータの性質によって異なります。それが完全にランダムである場合、テキストからバイトに変換した後、多くの圧縮を得ることができません。

于 2012-11-06T11:21:20.457 に答える
0

このデータを具体的に圧縮するための独自のアルゴリズムを作成しようとしても、ほとんど成果が得られない可能性があります。

Create a GZipStream with Max CompressionLevel
Run a 4096x4096 loop
 - set all 64 bits of a ulong to bits of the array
 - when 64 bits are done write the ulong to the compressionstream and start at the first bit again

これにより、キューブをかなり圧縮されたメモリブロックに非常に簡単に追加できます

于 2012-11-06T09:35:09.037 に答える
0

ハフマンコーディングを使用すると、かなり圧縮できます。

0  => 111
1  => 10
,  => 0
\r => 1100
\n => 1101

マトリックスの例（ビット単位）を生成します。

10011101 11010010 01011001 10111101 00111010 01001011 00110110 01110111
01001110 11111001 10111101 00100111 01001011 00110110 01110111 01110111 
01011001 10111101 00111010 0111010

カンマ、改行、およびキャリッジリターンを除外できる場合は、各値を格納するために必要なのはBitArrayだけです。ただし、デコードするときに行列の次元を知る必要があります。そうでない場合は、データをシリアル化することを計画している場合は、それをintとして保存し、次にデータ自体を保存することができます。

何かのようなもの：

var input = @"1,0,0,1,1,1
              0,1,0,1,1,1
              1,0,0,1,0,0
              0,1,1,0,1,1
              1,0,0,0,0,1
              0,1,0,1,0,1";

var values = new List<bool>();
foreach(var c in input)
{
  if (c == '0')
    values.Add(false);
  else if (c == '1')
    values.Add(true);
}

var ba = new BitArray(values.ToArray());

次に、BitArrayをシリアル化します。データを適切にデコードするには、おそらくパディングビットの数を追加する必要があります。（4096 * 4096は8で割り切れます）。

マトリックスに大量の繰り返しパターンがない限り、BitArrayアプローチで最大の圧縮が得られるはずです（はい、データはほとんどランダムであると想定しています）。

于 2012-11-06T10:07:56.720 に答える