10個の数を6個の数に圧縮して表す

0-9で表される数字列は、そのうちの4つの数字が使用できないようにし、残りの数字で再符号化する.符号化と復号関数を書き出します.
プレフィックス符号化、最初の5つの残りの符号化は1つのデジタル符号化である.最後の1つと使用できない4つの数字は、2つの数字で符号化されます.

 1 class Coding {

 2     public:

 3         void init(int uncode[], int n) {

 4             // get the code left

 5             vector<int> left;

 6             for (int i = 0, j = 0, m = 0; i < 10; ++i) {

 7                 if (j < 4 && i == uncode[j]) {

 8                     j++;

 9                     continue;

10                 }

11                 left.push_back(i);

12                 if (m < 5) {

13                     string code; code += (left[m++] + '0');

14                     codebook[i + '0'] = code;

15                     decodebook[code] = i + '0';

16                 }

17             }

18 

19             // code for the last one left

20             string code; code; code += (left.back() + '0');

21             code += (left.front() + '0');

22             codebook[left.back() + '0'] = code;

23             decodebook[code] = left.back() + '0';

24 

25             //generate codebook for uncode

26             for (int i = 0; i < 4; ++i) {

27                 string code; code += (left.back() + '0');

28                 code += (left[i + 1] + '0');

29                 codebook[uncode[i] + '0'] = code;

30                 decodebook[code] = (uncode[i] + '0');

31             }

32             //for (map<char, string>::iterator it = codebook.begin(); it != codebook.end(); it++) 

33             //  cout << it->first << " " << it->second << endl;

34         }

35 

36         string encode(string &str) {

37             if (str.empty()) return "";

38             stringstream ans;

39             for(int i = 0; i < str.length(); ++i) {

40                 ans << codebook[str[i]];

41             }

42             return ans.str();

43         }

44 

45         string decode(string &str) {

46             if (str.empty()) return "";

47             stringstream ans;

48             for(int i = 0; i < str.length(); ++i) {

49                 string tmp;

50                 tmp += str[i];

51                 if (decodebook.find(tmp) != decodebook.end() ||

52                         (++i < str.length() && decodebook.find(tmp += str[i]) != decodebook.end())){

53                     ans << decodebook[tmp];

54                 } else {

55                     return "error";

56                 }

57             }

58             return ans.str();

59         }

60     private:

61         map<string, char> decodebook;

62         map<char, string> codebook;

63 };

たとえばuncode={2,5,8,9}では、符号化テーブルは次のようになります.

 1 0 0

 2 1 1

 3 2 71

 4 3 3

 5 4 4

 6 5 73

 7 6 6

 8 7 70

 9 8 74

10 9 76

7は70で符号化される.
ところで、コードテーブル伝送にもオーバーヘッドがかかります.ただし、入力列が長い場合は、オーバーヘッドは無視できるはずです.