2

私は16文字のアルファベットを持っています。文が与えられたら、各文字の頻度を数え、巧妙なビット シフトを使用してすべての頻度を 1 つの数値にカプセル化します。これらの文が常にそれぞれ 100 文字であると仮定し、文字が 31 回以上出現しないと仮定すると、次のようになります。

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

等。

ここで、次のように連結したいと思います: 001010100111...

上記の周波数を集中させただけです。数値を簡単に格納するために、上記のバイナリを 64 ビットの unsigned int に変換したいと考えました。

私の他の要件は、その長さを持ち、文字ごとに周波数を再抽出することです。そのため、10 進数を生成し、それを個々の周波数ビットに解析できる必要があります。

cでそれを行うにはどうすればよいですか？これらの周波数のビット シフトと加算を行うことはできますが、それはつまり、周波数がオーバーラップしていることを意味します。もう1つの問題は、周波数を抽出するときです。末尾の0は重要ではなく、10進数で保存されないため、シフトするビット数をどのように知ることができますが、アルゴリズムでは非常に重要です。

何か賢いアイデアはありますか？ありがとうございました。

4

4 に答える 4

5

数学の問題とコーディングの問題の 2 つの問題があります。

とりあえず数学の問題は無視しましょう。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 に答える