, :
- First Base64 (345 → 256 )
- delta-encode (, , )
- - ( 3 2)
76 , .
Mercurial .
! , , , . , , , .
:
static void Main(string[] args)
{
string inputString = "ZmNiYWNma3F5gYqSmqCkpqenpKGdmJONiIN/e3d1c3FxcXFxcnN0dXZ3eXp7fHx9fn5/gIGDhISFhYWFhIOCgYGAgICBgoOEhYeIiYmJiYiGhIF+fHl3dHNyc3N1d3p9gIOGiYuMjY2NjIuKiIeFg4GAfnx7eXl4eHl5enx9fn5/gICAgYGBgYGBgYGBgoKDhISEhISEhIOCgoGAgH9/fn5+fn5/gICAgICAgICAgICAgICAf39/gICBgoOFhoeIiIiIiIeGhYOCgH99fHt6enp6e3x9foCAgoKDg4ODgoKBgH59fHt7e3t8fX5/gIKDhIWFhoaGhoaFhISDgoKBgQ==";
byte[] original = Convert.FromBase64String(inputString);
Console.WriteLine($"Original String: {inputString.Length}");
Console.WriteLine($"Original bytes: {original.Length}");
byte[] deltaEncoded = DeltaEncoderDecoder.Encode(original, 2);
byte[] compressed = HuffmanCompression.Compress(deltaEncoded);
Console.WriteLine($"Compressed bytes: {compressed.Length}");
byte[] deltaDecoded = HuffmanCompression.Decompress(compressed);
byte[] decompressed = DeltaEncoderDecoder.Decode(deltaDecoded, 2);
Console.WriteLine($"Decompressed bytes: {decompressed.Length}");
Console.WriteLine($"Decompressed == original: {decompressed.Length == original.Length && Enumerable.Range(0, original.Length).All(index => original[index] == decompressed[index])}");
}
:
Original String: 344
Original bytes: 256
Compressed bytes: 76
Decompressed bytes: 256
Decompressed == original: True
:
public static class HuffmanCompression
{
internal const byte CompressedSignature = 255;
internal const byte UncompressedSignature = 0;
[NotNull]
public static byte[] Compress([NotNull] byte[] input)
{
if (input == null)
throw new ArgumentNullException(nameof(input));
if (input.Length == 0)
return input;
var rootNode = GetNodesFromRawInput(input);
var bitStrings = GetBitStringsFromTree(rootNode);
var output = new MemoryStream(input.Length);
var writer = new BitStreamWriter(output);
writer.Write(CompressedSignature);
writer.Write(input.Length);
WriteNodes(writer, rootNode);
WriteStrings(writer, bitStrings, input);
writer.Flush();
if (output.Length < input.Length + 1)
return output.ToArray();
return EncodeAsUncompressed(input);
}
[NotNull]
private static byte[] EncodeAsUncompressed([NotNull] byte[] input)
{
var output = new MemoryStream();
output.WriteByte(UncompressedSignature);
output.Write(input, 0, input.Length);
return output.ToArray();
}
private static void WriteStrings([NotNull] BitStreamWriter writer, [NotNull] string[] bitStrings, [NotNull] byte[] input)
{
foreach (byte value in input)
{
Assume(bitStrings[value] != null);
foreach (char bitChar in bitStrings[value])
writer.Write(bitChar == '1');
}
}
private static void WriteNodes([NotNull] BitStreamWriter writer, [NotNull] Node node)
{
if (node.Left == null)
{
writer.Write(false);
writer.Write(node.Value);
}
else
{
Assume(node.Right != null);
writer.Write(true);
WriteNodes(writer, node.Left);
WriteNodes(writer, node.Right);
}
}
[NotNull, ItemNotNull]
private static string[] GetBitStringsFromTree([NotNull] Node node)
{
var result = new string[256];
TraverseToGetBitStringsFromTree(node, string.Empty, result);
return result;
}
private static void TraverseToGetBitStringsFromTree([NotNull] Node node, [NotNull] string prefix, [NotNull, ItemNotNull] string[] dictionary)
{
if (node.Left != null)
{
Assume(node.Right != null);
TraverseToGetBitStringsFromTree(node.Left, prefix + "0", dictionary);
TraverseToGetBitStringsFromTree(node.Right, prefix + "1", dictionary);
}
else
dictionary[node.Value] = prefix;
}
[NotNull]
private static Node GetNodesFromRawInput([NotNull] byte[] input)
{
var occurances = new int[256];
foreach (byte value in input)
occurances[value]++;
var nodes = new List<Node>(256);
for (int index = 0; index < 256; index++)
if (occurances[index] > 0)
nodes.Add(new Node
{
Occurances = occurances[index],
Value = (byte)index
});
while (nodes.Count > 1)
{
nodes.Sort((n1, n2) =>
{
Assume(n1 != null && n2 != null);
return n1.Occurances.CompareTo(n2.Occurances);
});
Assume(nodes[0] != null && nodes[1] != null);
nodes[0] = new Node
{
Left = nodes[0],
Right = nodes[1],
Occurances = nodes[0].Occurances + nodes[1].Occurances
};
nodes.RemoveAt(1);
}
Assume(nodes[0] != null);
return nodes[0];
}
[NotNull]
public static byte[] Decompress([NotNull] byte[] input)
{
if (input == null)
throw new ArgumentNullException(nameof(input));
if (input.Length == 0)
return input;
if (input[0] != CompressedSignature)
return DecodeUncompressed(input);
var reader = new BitStreamReader(new MemoryStream(input));
reader.ReadByte();
int length = reader.ReadInt32();
var rootNode = ReadNodes(reader);
var output = new byte[length];
for (int index = 0; index < length; index++)
output[index] = DecompressOneByte(reader, rootNode);
return output;
}
private static byte DecompressOneByte([NotNull] BitStreamReader reader, [NotNull] Node node)
{
while (node.Left != null)
{
if (reader.ReadBit())
node = node.Right;
else
node = node.Left;
Assume(node != null);
}
return node.Value;
}
[NotNull]
private static Node ReadNodes([NotNull] BitStreamReader reader)
{
if (reader.ReadBit())
return new Node
{
Left = ReadNodes(reader),
Right = ReadNodes(reader)
};
return new Node
{
Value = reader.ReadByte()
};
}
[NotNull]
private static byte[] DecodeUncompressed([NotNull] byte[] input)
{
return input.Skip(1).ToArray();
}
}
public class BitStreamReader
{
[NotNull]
private readonly MemoryStream _Source;
private byte _Buffer;
private int _InBuffer;
public BitStreamReader([NotNull] MemoryStream source)
{
if (source == null)
throw new ArgumentNullException(nameof(source));
_Source = source;
}
public bool ReadBit()
{
if (_InBuffer == 0)
FillBuffer();
return (_Buffer & BitStreamConstants.BitMasks[8 - _InBuffer--]) != 0;
}
public byte ReadByte()
{
if (_InBuffer == 8)
{
_InBuffer = 0;
return _Buffer;
}
return (byte)((ReadBit() ? 128 : 0) | (ReadBit() ? 64 : 0) | (ReadBit() ? 32 : 0) | (ReadBit() ? 16 : 0) | (ReadBit() ? 8 : 0) | (ReadBit() ? 4 : 0) | (ReadBit() ? 2 : 0) | (ReadBit() ? 1 : 0));
}
public int ReadInt32()
{
int result = 0;
if (ReadBit())
result |= ReadByte();
if (ReadBit())
result |= ReadByte() << 8;
if (ReadBit())
result |= ReadByte() << 16;
if (ReadBit())
result |= ReadByte() << 24;
return result;
}
private void FillBuffer()
{
int value = _Source.ReadByte();
if (value < 0)
throw new InvalidOperationException("Read past end of source stream");
_Buffer = (byte)value;
_InBuffer = 8;
}
}
public class BitStreamWriter
{
[NotNull]
private readonly MemoryStream _Target;
private byte _Buffer;
private int _InBuffer;
public BitStreamWriter([NotNull] MemoryStream target)
{
if (target == null)
throw new ArgumentNullException(nameof(target));
_Target = target;
}
public void Flush()
{
if (_InBuffer == 0)
return;
_Target.WriteByte(_Buffer);
_Buffer = 0;
_InBuffer = 0;
}
public void Write(bool bit)
{
unchecked
{
if (bit)
_Buffer = (byte)(_Buffer | 1 << (7 - _InBuffer));
if (++_InBuffer == 8)
Flush();
}
}
public void Write(byte value)
{
for (int index = 0; index < 8; index++)
Write((value & BitStreamConstants.BitMasks[index]) != 0);
}
public void Write(int value)
{
byte b0 = (byte)(value & 0xff);
byte b1 = (byte)((value >> 8) & 0xff);
byte b2 = (byte)((value >> 16) & 0xff);
byte b3 = (byte)((value >> 24) & 0xff);
Write(b0 != 0);
if (b0 != 0)
Write(b0);
Write(b1 != 0);
if (b1 != 0)
Write(b1);
Write(b2 != 0);
if (b2 != 0)
Write(b2);
Write(b3 != 0);
if (b3 != 0)
Write(b3);
}
}
internal static class BitStreamConstants
{
[NotNull]
public static readonly byte[] BitMasks = { 128, 64, 32, 16, 8, 4, 2, 1 };
public const byte CompressedSignature = 255;
}
public static class DeltaEncoderDecoder
{
[NotNull]
public static byte[] Encode([NotNull] byte[] input, int iterations)
{
if (input == null)
throw new ArgumentNullException(nameof(input));
var output = new byte[input.Length];
Buffer.BlockCopy(input, 0, output, 0, input.Length);
while (iterations-- > 0)
{
byte previous = 0;
for (int index = 0; index < output.Length; index++)
{
byte current = output[index];
output[index] = (byte)(current - previous);
previous = current;
}
}
return output;
}
[NotNull]
public static byte[] Decode([NotNull] byte[] input, int iterations)
{
if (input == null)
throw new ArgumentNullException(nameof(input));
var output = new byte[input.Length];
Buffer.BlockCopy(input, 0, output, 0, input.Length);
while (iterations-- > 0)
{
byte previous = 0;
for (int index = 0; index < output.Length; index++)
{
output[index] = (byte)(previous + output[index]);
previous = output[index];
}
}
return output;
}
}