4

大きな (一定の) ビット配列を必要とするコードを扱っています。大きな定数スパン (すべて 0 またはすべて 1) が含まれているため、次のように重複したスパン (定数またはそれ以外) を省略できる 2 レベルのテーブルに分割しました。

bitn = table2[table1[n/256]+n%256/8]&1<<n%8

この時点で、 のエントリtable1はすべて 32 の倍数 (256 ビット) ですが、スパンをオーバーラップさせることで大幅な節約ができるのではないかと考えていtable2ます。だから私の質問は（抽象的な形で述べられている）です：

長さ K の N 個の文字列 { S_n : n=1..N } が与えられた場合、各 S_n が S の部分文字列になるように、最短の長さの文字列 S を見つける効率的な方法はありますか?

(私はおそらくビット配列を 8 ビットに揃えておきたいので、この問題の特定のアプリケーションはおそらくビットの文字列ではなく 8 ビットのバイトの文字列を扱うことに注意してください。 - ビット、バイト、または何でも。)

4

2 に答える 2

1

定数の大きなセクションを持つ大きな定数ビット配列に関連して、検討するテーブルを設計する別の方法を次に示します (正確なニーズがわからないため、役立つかどうかはわかりません)。

基数ツリーのようなものを考えてみましょう。説明を簡単にするために、get 関数を定義します。

#define TYP_CONST
#define TYP_ARRAY

struct node {
    unsigned min;
    unsigned max;
    int typ;
    union {
        char *bits;
        int constant;
    } d;
    struct node *left;
    struct node *right;
}

struct bit_array {
    unsigned length;
    struct node *root;
}

int get(struct bit_array *b, unsigned ix)
{
    struct node *n = b->root;
    if (ix >= b->length)
        return -1;
    while (n) {
        if (ix > n->max) {
            n = n->right;
            continue;
        } else if (ix < n->min) {
            n = n->left;
            continue;
        }
        if (n->typ == TYP_CONST)
            return n->d.constant;
        ix -= n->min;
        return !!(n->d.bits[ix/8] & (1 << ix%8));
    }
    return -1;
}

人間の言葉で言えば、ツリーを調べてビットを探します。すべてのノードはビットの範囲を担当し、範囲をバイナリ検索して目的の範囲を見つけます。

範囲が見つかったら、定数または配列の 2 つのオプションがあります。定数の場合は、定数を返すだけです (多くのメモリを節約できます)。配列の場合、ビット配列で配列ルックアップを行います。

O(1) の代わりに O(log n) のルックアップ時間が必要になりますが、それでも信じられないほど高速なはずです。

ここでの問題は、適切なデータ構造を設定するのが煩わしく、エラーが発生しやすいことです。しかし、あなたは配列が一定であると言ったので、それは問題ではないかもしれません.

于 2012-04-23T20:36:21.433 に答える
1

まず、この問題は TSP として定式化できます。ノードのセット (各文字列がノード) があり、すべてのノードにアクセスするパスを見つける必要があります。文字列 x と y の間の距離は、len(xy)+len(y) として定義されます。xy は、x と y の両方を持ち、x で始まる最適な文字列です (例: x=000111、y=011100、xy=0001100)。 、距離 (x、y) = 8-6 = 2)。

これは三角不等式 (distance(x,z) <= distance(x,y)+ distance(y,z) ) にも従うことに注意してください。距離は 1 から k までの整数です。また、距離は非対称です。

このバージョンの TSP は (1,B)-ATSP と呼ばれます。このような問題の分析と近似解については、http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.3439を参照してください。

于 2012-04-23T18:57:27.070 に答える