使用C++进行运行长度解压缩

Question

我有一个文本文件，其中包含我编码的字符串。

假设它是：aaahhhhiii kkkjjhh ikl wwwwwweeeett

这里的编码代码，它工作得非常好：

void Encode(std::string &inputstring, std::string &outputstring)
{
for (int i = 0; i < inputstring.length(); i++) {
int count = 1;
while (inputstring[i] == inputstring[i+1]) {
count++;
i++;
}
if(count <= 1) {
outputstring += inputstring[i];
} else {
outputstring += std::to_string(count);
outputstring += inputstring[i];
}
}
}

输出如预期：3a4h3i 3k2j2h ikl 6w4e2t

现在，我想将输出解压回原始。

从几天以来，我一直在为此而挣扎。

到目前为止我的想法：

void Decompress(std::string &compressed, std::string &original)
{
char currentChar = 0;
auto n = compressed.length();
for(int i = 0; i < n; i++) {
currentChar = compressed[i++];
if(compressed[i] <= 1) {
original += compressed[i];
} else if (isalpha(currentChar)) {
//
} else {
//
int number = isnumber(currentChar).....
original += number;
}
}
}

我知道我的解压功能看起来有点乱，但我对这个功能很着迷。抱歉。

也许有人在斯塔克夫弗洛想帮助一个迷失和初学者的灵魂。

谢谢你的帮助，我很感激。

Answer 1

假设输入字符串不能包含数字(这不能被您的编码覆盖，例如字符串"3a"和"aaa"都会导致编码字符串"3a"——您希望如何再次分解？(，那么您可以如下解压缩：

unsigned int num = 0;
for(auto c : compressed)
{
if(std::isdigit(static_cast<unsigned char>(c)))
{
num = num * 10 + c - '0';
}
else
{
num += num == 0; // assume you haven't read a digit yet!
while(num--)
{
original += c;
}
}
}

不过，未测试的代码。。。

不过，字符串中的字符实际上只是数值。您也可以将char(或signed char、unsigned char(视为普通的8位整数。你也可以在这样一个字节中存储一个数值。通常，运行长度编码就是这样进行的：最多计数255个相等的字符，将计数存储在一个字节中，将字符存储在另一个字节。一个单独的"a"会被编码为0x01 0x61(后者是a的ASCII值(，"aa"会得到0x02 0x61，依此类推。如果你必须存储超过255个相等的字符，你可以存储两对：0xff 0x61, 0x07 0x61用于包含262倍字符a的字符串。。。然后解码变得琐碎：您成对读取字符，第一个字节解释为数字，第二个字节理解为字符——其余的都是琐碎的。你也可以很好地用这种方式覆盖数字。

Answer 2

#include "string"
#include "iostream"

void Encode(std::string& inputstring, std::string& outputstring)
{
for (unsigned int i = 0; i < inputstring.length(); i++) {
int count = 1;
while (inputstring[i] == inputstring[i + 1]) {
count++;
i++;
}
if (count <= 1) {
outputstring += inputstring[i];
}
else {
outputstring += std::to_string(count);
outputstring += inputstring[i];
}
}
}
bool alpha_or_space(const char c)
{
return isalpha(c) || c == ' ';
}
void Decompress(std::string& compressed, std::string& original)
{
size_t i = 0;
size_t repeat;
while (i < compressed.length())
{
// normal alpha charachers
while (alpha_or_space(compressed[i]))
original.push_back(compressed[i++]);
// repeat number
repeat = 0;
while (isdigit(compressed[i]))
repeat = 10 * repeat + (compressed[i++] - '0');
// unroll releat charachters
auto char_to_unroll = compressed[i++];
while (repeat--)
original.push_back(char_to_unroll);
}
}
int main()
{
std::string deco, outp, inp = "aaahhhhiii kkkjjhh ikl wwwwwweeeett";
Encode(inp, outp);
Decompress(outp, deco);
std::cout << inp << std::endl << outp << std::endl<< deco;
return 0;
}

Answer 3

解压缩不可能以明确的方式工作，因为您没有定义sentinel字符；即，在给定压缩流的情况下，不可能确定一个数字是原始的单个数字还是它表示重复RLE命令。我建议使用"0"作为sentinel字符。编码时，如果看到"0"，则只输出010。任何其他字符X将转换为0NX，其中N是重复字节计数器。如果超过255，只需输出一个新的RLE重复命令