我正在尝试对矩阵中仅包含 1 和 0 的数据实现最佳压缩。
为了说明我的意思，这是一个 6 x 6 矩阵示例：
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）。
我想它可能会被严重压缩，但我不确定如何。我会将最佳压缩标记为答案。性能无关紧要。
问问题
344 次
4 回答
1
我假设您想将字符串压缩成其他字符串，即使您的数据确实是二进制的。我不知道最好的压缩算法是什么（这将取决于您的数据），但您可以将输入文本转换为位，压缩这些，然后使用 base-64 编码再次将压缩字节转换为字符串。这将允许您从一个字符串转到另一个字符串，并且仍然应用您选择的压缩算法。
.NET 框架提供了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,096 x 4,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 回答
1
嗯......在不知道问题域的情况下，尽可能小是不可能的。
这是一般方法：
- 使用位而不是字节或字符或其他方式表示数组中的一和零。
- 使用通用无损压缩算法进行压缩。最常见的两种是：霍夫曼编码和某种类型的 LZW。
霍夫曼可以在数学上被证明可以提供最好的数据压缩，关键是为了解压缩数据，您还需要可能与原始数据一样大的霍夫曼树。对于大多数输入，LZW 为您提供相当于 Huffman 的压缩（在百分之几内），但在文本等重复段的数据上表现最佳。压缩算法的实现应该很容易实现（GZIP 使用 LZ77，它是 LZW 的较早的稍微不太理想的版本。）
使用现代算法的压缩算法的良好实现转到 7zip.org。它是开源的，他们有一个带有 DLL 的 C API，但你必须创建 .Net 接口（除非有人已经制作了。）
非通用方法：这依赖于数据的已知特征。例如：如果您知道大部分数据为零，则可以只编码这些数据的坐标。如果数据包含 1 和 0 的补丁，则可以使用 RLE 或算法的二维变体对其进行编码。
于 2012-11-06T10:03:31.513 回答
0
使用Huffman Coding，您可以将其压缩很多：
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 回答
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 回答