数据压缩(双位编码) -- C++实现


该算法适用于具备以下特点的数据

小规模的字母表/较长的连续相同的位或者字符/频繁使用的字符/较长的连续重复的位或者字符

实现代码

// TwoBitCoding.h
#ifndef TwoBitCoding_h
#define TwoBitCoding_h

#include<iostream>
using namespace std;

namespace jay{

    class TwoBitCoding
{
public:
	TwoBitCoding(string alpha,int bituse = 2,int tablesize = 256 )
	{
		m_tablesize = tablesize;
		m_BitUse = bituse;
		m_R = alpha.length();
		
		bool *unicode = new bool[m_tablesize];
		for (int i = 0; i <m_tablesize;i++)
		{
			unicode[i] = false;
		}

		for (int i = 0; i < m_R; i++) 
		{
			char c = alpha.at(i);
			if (unicode[c])
			{
				char szError[100] = {0x00};
				sprintf(szError,"Illegal alphabet: table find repeated character = '","c","'");
				throw (szError);
			}
			unicode[c] = true;
		}

		// 字符串转字符数组
		m_alphabet = new char[m_R];
		for (int i = 0; i < m_R; i++) 
		{
			m_alphabet[i] = alpha.at(i);
		}

		// 反向数组
		m_inverse = new int[m_tablesize];
		for (int i = 0; i < m_tablesize; i++)
			m_inverse[i] = -1;

		// m_alphabet[i]存放的是字符串alpha的值
		// m_inverse 是 m_alphabet的反向数组
		for (int i = 0; i < m_R; i++)
			m_inverse[m_alphabet[i]] = i;

	}

	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 Compress(string str)
	{
		string strCompress;
		for (int i = 0; i < str.length(); i++) 
		{
			int d = m_inverse[str.at(i)];
			strCompress += GetBitString(d,m_BitUse);
		}

		return strCompress;
	}

	string Expand(string str)
	{
		string strExpand;
		for (int i = 0; i < str.length(); i = i+m_BitUse) 
		{
			string strCurrent =  str.substr(i,m_BitUse);
			int d = GetIntFromStringBit(strCurrent,m_BitUse);
			strExpand += m_alphabet[d];
		}

		return strExpand;
	}

	~TwoBitCoding()
	{
		delete []m_alphabet;
		delete []m_inverse;
		m_alphabet = nullptr;
		m_inverse = nullptr;
	}
private:
	char *m_alphabet;     // the characters in the alphabet
	int *m_inverse;       // indices
	int m_tablesize;      // 总字母表的大小
	int m_R;              // 实际使用的字母的大小
	int m_BitUse;
};
};

#endif

测试代码

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


int main(int argc, char* argv[])
{
	// 实际使用的字符只有4个,索引为0-3对应二进制数00 01 10 11 可以用2个位来表示
	// 这里是双位编码 最多可以处理 8位的字符表
	TwoBitCoding tbc("ACGT");
	cout << "实际使用的字母表顺序:ACGT [A-0(00) C-1(01) G-2(10) T-3(11)]" << endl;
	cout << "原始字符:ATAGATGCATAGCGCATAGCTAGATGTGCTAGC" <<endl;
	string strC = tbc.Compress("ATAGATGCATAGCGCATAGCTAGATGTGCTAGC");
	cout << "压缩后的字符(二进制),每2位代表一个字母:"<< strC <<endl;
	cout << "解压后的字符:"<<tbc.Expand(strC) <<endl;

	cout << "---------------------" <<endl;
	// 三位编码 最多可以处理 8位的字符表
	TwoBitCoding tbc2("ACGTZX",3);
	cout << "原始字符:ATAGATGCZZZATXXAGCGCATAGCTAGATGTGCTAGCZ" <<endl;
	strC = tbc2.Compress("ATAGATGCZZZATXXAGCGCATAGCTAGATGTGCTAGCZ");
	cout << "压缩后的字符(二进制),每3位代表一个字母:"<< strC <<endl;
	cout << "解压后的字符:"<<tbc2.Expand(strC) <<endl;

}

测试结果

暂无评论

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