2

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

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

等等。

现在，我想连接这样的：001010100111 ...

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

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

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

有什么聪明的主意吗？谢谢你。

4

4 回答 4

5

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

让我们暂时忽略数学问题。您可以构建一个包含 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);
}

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

现在，如果你想用更大的文本来做这个，或者一个字母可以出现超过 15 次，你必须在计数后缩放你的数字，使最大值不大于 15。这就是我提到的数学问题至。我想你可能会弄清楚如何处理那个。你只需要缩放数字。

于 2013-07-21T18:43:00.017 回答
1

试试这个，好处是不需要中间数组来计算你的字母：

int ch_to_index(char ch) { return ch-'A'; }

unsigned long long get_freq(unsigned long long freq, int index)
{
    return (freq>>(4*index))&0x0f;
}


unsigned long long set_freq(unsigned long long freq, int index, unsigned long val)
{
    return (  ((val&0x0fULL)<<(4*index)) | (freq & (0xffffffffffffffffULL ^ (0xfULL<<(4*index)))) );
}

unsigned long long inc_freq(unsigned long long freq, int index)
{
    return set_freq(freq, index, get_freq(freq, index) +1) ;
}

int main()
{
    int i;
    unsigned long long freq=0;
    freq = inc_freq(freq, ch_to_index('A'));
    freq = inc_freq(freq, ch_to_index('A'));
    freq = inc_freq(freq, ch_to_index('B'));

    for(i=0;i<16;i++)
    {
        printf("%i = %i\n", i, (int)get_freq(freq, i));
    }
}
于 2013-07-21T18:48:54.833 回答
1

像这样的东西就足够了：

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

const static int  SIZE       = 16;
const static char ALPHABET[] = "0123456789ABCDEF";

char* getFrequency(char* str);
uint64_t getFrequencyNumber(char* freq);

int main() {
  char*    str     = "1337CODE";
  uint64_t freqNum = getFrequencyNumber(getFrequency(str));
  printf("%llu\n",freqNum);
  return 0;
}

char* getFrequency(char* str) {
  int i,j;
  char* freq = (char*) calloc(SIZE, sizeof(char));
  for(i=0; str[i]; ++i)
    for(j=0; j<SIZE; ++j)
      if(str[i] == ALPHABET[j])
        if(freq[i] < 15) //ignore overflow
          (freq[j])++;
  return freq;
}

uint64_t getFrequencyNumber(char* freq) {
  uint64_t i,num;
  for(i=num=0; i<SIZE; ++i)
    num |= freq[i] << (4*i); //use bit shifting to concatenate 4 bit values
  return num;
}
于 2013-07-21T18:52:25.783 回答
1

现有的答案很好；也许以下更好。

很容易只使用一个 64 位数字，并增加其中的各个 4 位部分。

例如，以下增加第 3、5 和 13 个字母的计数器（从 0 开始计数）：

uint64_t my_counters = 0;
my_counters += (uint64_t)1 << (4 * 3);
my_counters += (uint64_t)1 << (4 * 5);
my_counters += (uint64_t)1 << (4 * 13);

如果您的字母在 ASCII 表中是连续的（例如[a-p]），则很容易根据其数值计算字母的索引：

uint64_t my_counters = 0;
size_t i;
for (i = 0; str[i] != '\0'; ++i)
{
    int index = str[i] - 'a';
    my_counters += (uint64_t)1 << (4 * index);
}

打印：

char c;
for (c = 'a'; c <= 'p'; ++c)
{
    int index = c - 'a';
    int counter = (int)((my_counters >> (4 * index)) & 0xf);
    printf("Letter %c, count %d\n", c, counter);
}

注意：与您想要的相比，我的代码以相反的顺序连接位；似乎这种方式更清楚了。如果替换为 ，则可以颠倒4 * index顺序60 - 4 * index。

于 2013-07-23T23:11:58.487 回答