c++ - 如何在 C++ 中用较小的字符串减少较大的字符串？可能是通过散列？

Question

我想在 C++ 中将一个较大的字符串压缩成一个较小的字符串。在 C++ 中有哪些不同的方法可以做到这一点？要求是输出也应该是一个字符串。

Answer 1

好吧，如果您以后不需要解压缩它：

string s = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
s = "";

编辑：听起来你想要一个哈希函数 - 那里有无数个，具体取决于你的要求。谷歌是你的朋友。

Answer 2

正如无人所说，谷歌是你的朋友：数据压缩算法。

以下是我的一些想法：
RLE——运行长度编码的
Huffman
Lepel-Ziv

Answer 3

正如我从问题评论中了解到的，您不需要解压缩它，而只希望唯一的字符串获得唯一的结果。我将要解释的散列算法非常容易理解并且效果很好（我在实践中使用过很多次）。这是一个非常简单的滚动哈希函数，用于Rabin-Karp字符串搜索算法。

好的，让我们将每个字符串视为 257 基系统中的数字（因为 257 是质数）。例子：

1. “10” = 代码（'1'）* 257 + 代码（'0'）
2. “p:;” = 代码('p') * 257^2 + 代码('0') * 257 + 代码(';')

code(char a)字符 + 1 的 ascii 代码在哪里a（取 +1 为字符串'\0'（n 次）和'\0'（m 次）给出不同的结果）。当然，如果字符串很大，那么它的适当数字就不能存储在int或事件中unsigned long long。但这不是问题，您可以将MOD其MAX_SIZE存储在要存储的数据类型中。因此，您的哈希函数的最终代码正在闲置。

unsigned long long hash(const string & s)
{
    unsigned long long ret = 0;
    for(int i = 0; i < s.size(); ++i)
    {
        ret *= 257;
        ret += s[i] + 1;
    }
    return ret;
}

编辑：添加了这个算法的来源。