首页 > 代码库 > 10个数压缩成6个数表示

10个数压缩成6个数表示

由0-9表示的数字串,现使其中4个数字不可用,用余下的数字进行重编码。写出编码和解码函数。

前缀编码,前5个剩下的编码用一个数字编码。最后一个以及不可用的4个数字,用两个数字进行编码。

 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 left20             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 uncode26             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 7410 9 76

7用70来编码。

10个数压缩成6个数表示