在資料集中情況下壓縮比還不錯 , 依據資料格式類型壓縮到上百倍也不是問題
未來: 可加入平行化處理 加速Encode 跟 Decode
各種演算法參考資料
Run Length Encoding 參考資料
其他壓縮法簡單比較:
CodeTree ( 四元樹演算法 O(n)
LZMA ( 對重複的組合 壓縮比較有效 可平行化 O(n)
RunLen ( 目前使用 實作簡單 可平行化 適合資料單一結構 O(n)
QOI (針對圖片地壓縮格式 純資料可能沒這麼好
Huffman Compression ( 把重複地編碼建表 再來壓縮
Code:
using System;
using System.Collections.Generic;
public class RunLengthCompression
{
public byte[] EncodeUshort(ushort[] bAy)
{
if (bAy == null)
{
return null;
}
List codeList = new List();
for (int i = 0; i < 4; i++)
{
codeList.Add(0);
}
byte count = 1;
for (int i = 0; i < bAy.Length - 1; i++)
{
ushort now = bAy[i];
ushort next = bAy[i + 1];
if (now.Equals(next))
{
count++;
if (count == 255 || i >= bAy.Length - 2)
{
AddUshort(codeList, now);
codeList.Add(count);
count = 0;
}
}
else
{
if (count == 255)
{
AddUshort(codeList, now);
codeList.Add(count);
}
else if (i >= bAy.Length - 2)
{
AddUshort(codeList, now);
codeList.Add(count);
AddUshort(codeList, next);
codeList.Add(1);
}
else
{
AddUshort(codeList, now);
codeList.Add(count);
count = 1;
}
}
}
byte[] result = codeList.ToArray();
byte[] grouptCountBytes = BitConverter.GetBytes(bAy.Length);
for (int i = 0; i < 4; i++)
{
result[i] = grouptCountBytes[i];
}
return result;
}
public ushort[] DecodeUshort(byte[] bAy, ushort[] ogAy = null)
{
byte header = 4;
if (bAy == null || bAy.Length < 4)
{
return null;
}
int orginLen = BitConverter.ToInt32(bAy, 0);
ushort[] result = new ushort[orginLen];
int idx = 0;
for (int i = header; i < bAy.Length; i += 3)
{
ushort val = GetUshort(bAy, i);
byte count = bAy[i + 2];
for (int j = 0; j < count; j++)
{
if (idx >= orginLen)
{
ErrorLog("over idx ?");
break;
}
result[idx] = val;
if (ogAy != null && ogAy[idx] != result[idx])
{
ErrorLog($"not same in {idx}");
break;
}
idx++;
}
}
return result;
}
private void AddUshort(List list, ushort val)
{
list.Add((byte)val);
list.Add((byte)(val >> 8));
}
private ushort GetUshort(byte[] bAy, int idx)
{
ushort val = (ushort)((bAy[idx]) + (bAy[idx + 1] << 8));
return val;
}
public byte[] Encode(byte[] bAy)
{
if (bAy == null)
{
return null;
}
List codeList = new List();
for (int i = 0; i < 4; i++)
{
codeList.Add(0);
}
byte count = 1;
for (int i = 0; i < bAy.Length - 1; i++)
{
byte now = bAy[i];
byte next = bAy[i + 1];
if (now == next)
{
count++;
if (count == 255 || i >= bAy.Length - 2)
{
codeList.Add(now);
codeList.Add(count);
count = 0;
}
}
else
{
if (count == 255)
{
codeList.Add(now);
codeList.Add(count);
}
else if (i >= bAy.Length - 2)
{
codeList.Add(now);
codeList.Add(count);
codeList.Add(next);
codeList.Add(1);
}
else
{
codeList.Add(now);
codeList.Add(count);
count = 1;
}
}
}
int orginLen = bAy.Length;
codeList[0] = (byte)orginLen;
codeList[1] = (byte)(orginLen >> 8);
codeList[2] = (byte)(orginLen >> 16);
codeList[3] = (byte)(orginLen >> 24);
byte[] result = codeList.ToArray();
return result;
}
public byte[] Decode(byte[] bAy, byte[] ogAy = null)
{
byte header = 4;
if (bAy == null || bAy.Length < 4)
{
return null;
}
int orginLen = (bAy[3] << 24) | (bAy[2] << 16) | (bAy[1] << 8) | bAy[0];
byte[] result = new byte[orginLen];
int idx = 0;
for (int i = header; i < bAy.Length; i += 2)
{
byte val = bAy[i];
byte count = bAy[i + 1];
for (int j = 0; j < count; j++)
{
if (idx >= orginLen)
{
ErrorLog("over idx ?");
goto ERROR;
}
result[idx] = val;
if (ogAy != null && ogAy[idx] != result[idx])
{
ErrorLog($"not same in {idx}");
goto ERROR;
}
idx++;
}
}
return result;
ERROR:
{
return null;
}
}
public static void TestCase(byte[] orgin)
{
RunLengthCompression compreesion = new RunLengthCompression();
byte[] encode = compreesion.Encode(orgin);
byte[] decode = compreesion.Decode(encode);
if (orgin.Length != decode.Length)
{
ErrorLog("not same len");
}
for (int i = 0; i < orgin.Length; i++)
{
if (orgin[i] != decode[i])
{
ErrorLog($"not same [{i}] ,{orgin[i]},{decode[i]}");
continue;
}
}
}
public static void TestCase(ushort[] orgin)
{
RunLengthCompression compreesion = new RunLengthCompression();
byte[] encode = compreesion.EncodeUshort(orgin);
ushort[] decode = compreesion.DecodeUshort(encode);
if (orgin.Length != decode.Length)
{
ErrorLog("not same len");
}
for (int i = 0; i < orgin.Length; i++)
{
if (orgin[i] != decode[i])
{
ErrorLog($"not same [{i}] ,{orgin[i]},{decode[i]}");
continue;
}
}
}
static void ErrorLog(string errorLog, params string[] p)
{
UnityEngine.Debug.LogErrorFormat(errorLog, p);
}
}
Test Code:
using NUnit.Framework;
public class RunLengthCompressionTester
{
[Test]
public void ByteUshort123()
{
RunLengthCompression.TestCase(new ushort[] { 1, 2, 3 });
}
[Test]
public void ByteUshort1212()
{
RunLengthCompression.TestCase(new ushort[] { 1, 2, 1, 2 });
}
[Test]
public void ByteUshort655_655_1_1()
{
RunLengthCompression.TestCase(new ushort[] { 655, 655, 1, 1 });
}
[Test]
public void ByteUshort1111_9999_9999_9999()
{
RunLengthCompression.TestCase(new ushort[] { 1111, 9999, 9999, 9999 });
}
[Test]
public void Ushort6666Reapeat257Times()
{
ushort[] b = new ushort[257];
for (int i = 0; i < 257; i++)
{
b[i] = 6666;
}
RunLengthCompression.TestCase(b);
}
[Test]
public void Ushort6666Reapeat513Times()
{
ushort[] b = new ushort[513];
for (int i = 0; i < 513; i++)
{
b[i] = 6666;
}
RunLengthCompression.TestCase(b);
}
[Test]
public void Byte123()
{
RunLengthCompression.TestCase(new byte[] { 1, 2, 3 });
}
[Test]
public void Byte1212()
{
RunLengthCompression.TestCase(new byte[] { 1, 2, 1, 2 });
}
[Test]
public void Byte122()
{
RunLengthCompression.TestCase(new byte[] { 1, 2, 2 });
}
[Test]
public void Byte1122()
{
RunLengthCompression.TestCase(new byte[] { 1, 1, 2, 2 });
}
[Test]
public void Byte1112()
{
RunLengthCompression.TestCase(new byte[] { 1, 1, 1, 2 });
}
[Test]
public void Byte12123()
{
RunLengthCompression.TestCase(new byte[] { 1, 2, 1, 2, 3 });
}
[Test]
public void Byte12344()
{
RunLengthCompression.TestCase(new byte[] { 1, 2, 3, 4, 4 });
}
[Test]
public void Byte257()
{
byte[] b = new byte[257];
for (int i = 0; i < 256; i++)
{
b[i] = 1;
}
b[256] = 2;
RunLengthCompression.TestCase(b);
}
[Test]
public void Byte258()
{
byte[] b = new byte[258];
for (int i = 0; i < 256; i++)
{
b[i] = 1;
}
b[256] = 2;
b[257] = 2;
RunLengthCompression.TestCase(b);
}
[Test]
public void Byte259()
{
byte[] b = new byte[259];
for (int i = 2; i < 259; i++)
{
b[i] = 1;
}
b[0] = 2;
b[1] = 2;
RunLengthCompression.TestCase(b);
}
[Test]
public void Byte515()
{
byte[] b = new byte[515];
for (int i = 2; i < 515; i++)
{
b[i] = 1;
}
b[0] = 2;
b[1] = 2;
RunLengthCompression.TestCase(b);
}
}
沒有留言:
張貼留言