c - 使用 c 和位移来解决特定需求

Question

我有一个 16 个字母的字母表。给定一个句子，我想计算每个字母的频率，然后使用巧妙的位移将所有频率封装在一个数字中。让我们假设这些句子每个都是 100 个字母，并且假设没有字母出现超过 31 次，我想要这样的东西:

A: occurs 2 times -> 0010
B: occurs 10 times -> 1010
C: occurs 7 times -> 0111

等等。

现在，我想将这些连接起来: 001010100111...

我只是集中了上面的频率。为了方便地存储数字，我想将上面的二进制转换为 64 位无符号整数。

我的另一个要求是有这么长的时间并重新提取每个字母的频率。因此，我需要能够生成小数，然后将其解析为各个频率位。

我将如何在 c 中做到这一点？我可以对这些频率进行位移和相加，但这意味着我在重叠频率。另一个问题是在提取频率时，我怎么知道要移动多少位，因为尾随 0 是微不足道的并且不保存在小数中，但它们在我的算法中非常重要。

有什么好主意吗？谢谢。

Answer 1

你有两个问题:一个数学问题和一个编码问题。

让我们暂时忽略数学问题。您可以构建一个包含 16 个整数的数组，并在扫描文本时计算每个字母的出现次数。如果您假设没有一个字母出现超过 15 次，那么您不必担心溢出，您可以很容易地将计数放入 64 位整数中。你会写:

int counts[16];  // has the counts
unsigned long long freqs;  // this holds the encoded value

// after you compute the counts
freqs = 0;
for (int i = 0; i < 16; ++i)
{
    freqs <<= 4;
    freqs |= (counts[i] & 0xF);
}

此时，第一个字母的计数在 freqs 的前 4 位，最后一个字母的计数在后 4 位。所有其他计数都介于两者之间。每一个恰好占据 64 位数字的 4 位。

现在，如果您希望能够使用更大的文本执行此操作，或者一个字母出现的次数可能超过 15 次，则必须在计数后缩放数字，使最大值不超过 15。这就是数学原理我提到的问题。我想你可能会想出如何处理那个。您只需要缩放数字即可。