数据压缩(游程编码) -- C++实现


此算法适用于比特串,也就是字符串的字符只能是0或1

实现代码

// RunLengthCoding.h
#ifndef RunLengthCoding_h
#define RunLengthCoding_h

#include<iostream>
using namespace std;

namespace jay{

class RunLengthCoding
{
public:
	RunLengthCoding()
	{
		m_BitUse = 4;
	}

	string GetBitString(int d,int r)
	{
		string strb = "";
		for (int i = 0; i < r; i++) 
		{
			// (d >> (r - i -1)) & 1 
			// 第一次获取的是最高位 第二次是次高位,以此类推
			bool bit = ((d >> (r - i - 1)) & 1) == 1;
			if (bit)
			{
				strb += "1";
			}
			else
			{
				strb += "0";
			}
		}

		return strb;
	}

	int GetIntFromStringBit(string str,int r)
	{
		int d = 0;
		for (int i=0;i<r;i++)
		{
			char c = str.at(i);
			// 如果当前位为1
			if (c == 49)
			{
				d += pow(2.0,r-i-1);
			}
		}
		return d; 
	}

	string GetStringFromInt(string str,int r,bool tag)
	{
		int iLength = GetIntFromStringBit(str,r);
		string strR;
		string str0 = "000000000000000";
		string str1 = "111111111111111";

		if (tag)
		{
			strR = str1.substr(0,iLength);
		}
		else
			strR = str0.substr(0,iLength);

		return strR; 
	}

	// str必须只能是0或者1组成的字符(比特)串
	string Compress(string str)
	{
		string strCompress;
		char run = 0; 
		bool old = false;
		int strlength = str.length();
		for (int i=0;i<strlength;i++)
		{ 
			char tmp = str.at(i);
			bool b ;
			if (tmp == 48)
			{
				b = false;
			}
			else
				b = true;
			
			if (b != old) 
			{   // 遇到不同的字符
				strCompress += GetBitString(run,m_BitUse);
				strCompress += " ";
				run = 1;
				old = !old;
			}
			else 
			{ 
				// 相同的字符
				// 用于处理计数较大的情况,此处暂不实现
// 				if (run == R-1) 
// 				{ 
// 					strCompress += GetBitString(run,m_BitUse);
// 					run = 0;
// 					strCompress += GetBitString(run,m_BitUse);
// 				}

				run++;

				// 如果是最后一个字符
				if (i +1 == strlength)
				{
					strCompress += GetBitString(run,m_BitUse);
				}
			} 
		} 

		return strCompress;
	}

	string Expand(string str)
	{
		bool tag = false;
		string strExpand;
		for (int i = 0; i < str.length(); i = i+m_BitUse) 
		{
			string strCurrent =  str.substr(i,m_BitUse);
			strExpand += GetStringFromInt(strCurrent,m_BitUse,tag);

			tag = !tag;
		}

		return strExpand;
	}

	~RunLengthCoding()
	{
	}
private:
	int m_BitUse; // 用于计数的整数的位数
};
};

#endif

测试代码

//main.cpp
#include "Component.h"
#include "RunLengthCoding.h"
using namespace jay;


int main(int argc, char* argv[])
{

	RunLengthCoding rlc;
	// 源比特串约定以"0"开头,如果以"1"开头,第一个整数计数记为0
	// 目前只能处理连续计数不超过15的情况(4位) 如果有超过的需要改成更大的数(>4位)
	string strC = rlc.Compress("0000000000000001111111000000011111111111");
	cout << "原始字符(比特串):    0000000000000001111111000000011111111111" <<endl;
	cout << "压缩后的字符[每一个整数(目前假定为4位二进制数)表示当前串的长度]:" <<endl;
	cout << strC <<endl;
	strC.erase(remove(strC.begin(), strC.end(), ' '), strC.end());
	cout << "解压后的字符(比特串):"<<rlc.Expand(strC) <<endl;

}

测试结果

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。