1

ここで最適化の問題が発生しています。このコードを O(n) で実行したいと思います。これを数時間試しました。

バイト配列 c には文字列が含まれ、e には同じ文字列が含まれますが、ソートされています。内部配列 nc および ne には、文字列内のインデックスが含まれます。

c:
s l e e p i n g
nc:
0 0 0 1 0 0 0 0 
e:
e e g i l n p s
ne:
0 1 0 0 0 0 0 0

問題は get_next_index が線形であることです - これを解決する方法はありますか?

void decode_block(int p) {
    BYTE xj = c[p];
    int nxj = nc[p];

    for (int i = 0; i < block_size; i++) {
        result[i] = xj;
        int q = get_next_index(xj, nxj, c, nc);
        xj = e[q];
        nxj = ne[q];
    }

    fwrite(result, sizeof (BYTE), block_size, stdout);
    fflush(stdout);
}

int get_next_index(BYTE xj, int nxj, BYTE* c, int* nc) {
    int i = 0;
    while ( ( xj != c[i] ) || ( nxj != nc[i] ) ) {
      i++;
    }
    return i;
}

これはBurrows-Wheeler実装の一部です

それでは始まります

xj = c[p]
nxj = nc[p]

次に、block_size (= 長さ c = 長さ nc = 長さ e = 長さ ne) 回する必要があります

  • 結果 xj を result に格納する

  • c[i] == xj である数値インデックスを見つける

  • xj は e[i] になりました

ne と nc は、e と c のすべての文字が一意であることを確認するためにのみ使用されます (e_0 != e_1)。

4

3 に答える 3

1

Burrowes-Wheeler 変換の完全な実装を次に示します。

u8* bwtCompareBuf;
u32 bwtCompareLen;

s32 bwtCompare( const void* v1, const void* v2 )
{
   u8* c1 = bwtCompareBuf + ((u32*)v1)[0];
   u8* c2 = bwtCompareBuf + ((u32*)v2)[0];

   for ( u32 i = 0; i < bwtCompareLen; i++ )
   {
      if ( c1[i] < c2[i] ) return -1;
      if ( c1[i] > c2[i] ) return +1;
   }
   return 0;
}

void bwtEncode( u8* inputBuffer, u32 len, u32& first )
{
   s8* tmpBuf = alloca( len * 2 );

   u32* indices = new  u32[len];

   for ( u32 i = 0; i < len; i++ ) indices[i] = i;

   bwtCompareBuf = tmpBuf;
   bwtCompareLen = len;
   qsort( indices.data(), len, sizeof( u32 ), bwtCompare );

   u8* tbuf = (u8*)tmpBuf + ( len - 1 );
   for ( u32 i = 0; i < len; i++ )
   {
      u32 idx = indices[i];
      if ( idx == 0 ) idx = len;
      inputBuffer[i] = tbuf[idx];
      if ( indices[i] == 1 ) first = i;
   }

   delete[] indices;
}

void bwtDecode( u8* inputBuffer, u32 len, u32 first )
{
   // To determine a character's position in the output string given
   // its position in the input string, we can use the knowledge about
   // the fact that the output string is sorted.  Each character 'c' will
   // show up in the output stream in in position i, where i is the sum
   // total of all characters in the input buffer that precede c in the
   // alphabet, plus the count of all occurences of 'c' previously in the
   // input stream.

   // compute the frequency of each character in the input buffer
   u32 freq[256] = { 0 };
   u32 count[256] = { 0 };
   for ( u32 i = 0; i < len; i++ )
      freq[inputBuffer[i]]++;

   // freq now holds a running total of all the characters less than i
   // in the input stream
   u32 sum = 0;
   for ( u32 i = 0; i < 256; i++ )
   {
      u32 tmp = sum;
      sum += freq[i];
      freq[i] = tmp;
   }

   // Now that the freq[] array is filled in, I have half the
   // information needed to position each 'c' in the input buffer.  The
   // next piece of information is simply the number of characters 'c'
   // that appear before this 'c' in the input stream.  I keep track of
   // that information in the count[] array as I go.  By adding those
   // two numbers together, I get the destination of each character in
   // the input buffer, and I just write it directly to the destination.
   u32* trans = new u32[len];
   for ( u32 i = 0; i < len; i++ )
   {
      u32 ch = inputBuffer[i];
      trans[count[ch] + freq[ch]] = i;
      count[ch]++;
   }

   u32 idx = first;
   s8* tbuf = alloca( len );
   memcpy( tbuf, inputBuffer, len );
   u8* srcBuf = (u8*)tbuf;
   for ( u32 i = 0; i < len; i++ )
   {
      inputBuffer[i] = srcBuf[idx];
      idx = trans[idx];
   }

   delete[] trans;
}

O(n) でのデコード。

于 2012-11-25T18:10:52.477 に答える
1

あなたの宇宙 (つまり、文字) は小さいので、線形時間でうまくいくと思います。これには、リンクされたリストと シーケンス コンテナー、ルックアップ テーブルが必要です。

まず、ソートされた文字列を調べて、特定の文字の最初のリスト要素を見つけることができるルックアップ テーブルにデータを入力します。たとえば、ルックアップ テーブルは のようになりますstd::array<std::list<size_t>,(1<<sizeof(char))> lookup。が必要ない場合は、またはlistを使用することもできますが、2 番目の項目はベクトルの最初の有効なエントリのインデックスを表します (そうすれば、後で要素をポップする必要はなく、単にインクリメントするだけです)。索引）。std::dequestd::pair<std::vector,size_t>

したがってc、ソートされた文字列の各要素について、それを のコンテナに追加しますlookup[c]。

ここで、ソートされていない配列を反復処理すると、要素ごとに、ルックアップ テーブルで対応するインデックスをルックアップできます。完了したら、フロント要素をルックアップ テーブルにポップします。

全体として、これは直線的な時間と空間です。

明確にするために; ルックアップ テーブルを初期化する場合:

// Instead of a list, a deque will likely perform better,
// but you have to test this yourself in your particular case.
std::array<std::list<size_t>,(1<<sizeof(char))> lookup;
for (size_t i = 0; i < sortedLength; i++) {
  lookup[sorted[i]].push_back(i);
}

ソートさiれていない配列のインデックスの「最初のインデックス」を見つける場合:

size_t const j = lookup[unsorted[i]].front();
lookup[unsorted[i]].pop_front();
return j;
于 2012-11-25T17:48:58.763 に答える
1

xjと1 回スキャンしnxjて、ルックアップ テーブルを作成します。これは 2 つの O(n) 操作です。

最も賢明な方法は、xjまたはの値でソートされた二分木を持つことnxjです。ノードには、検索したインデックスが含まれます。これにより、ルックアップが O(lg n) に削減されます。

于 2012-11-25T17:49:02.510 に答える