0

特定のシーケンスから特定の長さのすべてのサブシーケンスを固定アルファベット (0、1、2、3 としましょう) で抽出し、どのサブシーケンスが読み取られ、どのサブシーケンスが読み取られないかを抽出する効率的なアルゴリズムを探しています。

したがって、シーケンスの場合

[0,1,3,2,4,3,1]

取得したいサブシーケンスの長さ 2

[[0,1],[1,3],[3,2],[2,4],[4,3],[3,1],

およびブール配列

 00 01 02 03 10 11 12 13 20 21 22 23 30 31 32 33
[ 0  1  0  0  0  1  0  1  0  0  0  0  0  1  1  0].

私の現在のアプローチは次のようなものです：

size_t              alphSize     = 4;
size_t              subSeqLength = 2;
std::deque<size_t>  currSub;
std::vector<bool>   subSeqRead ( pow( alphSize , subSeqLength ) );

for (size_t i = 0; i < seqLength - subSeqLength + 1; ++i)
{
    for (size_t j = 0; j < subSeqLength; ++j)
    {
        currSub.pop_front();
        currSub.push_back(sequence[i+j]);
    }
    if (currSub.size() == subSeqLength)
    {
        subSeqRead[ arrayPos(currSub) ] = true;
    }
}

どこ

arrayPos(currSub)

ヒープ ツリー構造で動作し、乗算なしでブール配列内のサブシーケンスの位置を計算します。

ただし、これはどこかに近い

O( seqLength * subSeqLength )

誰かが何かをより速く知っていますか？

私のシナリオでは、アルファベットのサイズは実際には 4 で、サブシーケンスの長さは >=6 で、シーケンスの長さは 10^4 から 10^6 です。そして、それらのシーケンスの多くを処理する必要があります。

そこから、入力シーケンスにワイルドカードの数字が含まれている可能性があります (「w」としましょう)。

[1,w,2]

私はこれを読んだかのように扱わなければならない

[[1,0],[1,1],[1,2],[1,3],[2,0],[2,1],[2,2],[2,3]].

提案をよろしくお願いします。

4

2 に答える 2

0

具体的な数値を使用すると、各要素を 2 ビットで表すことができます。最終的な配列を表現したいので、サブシーケンスが長くなりすぎないため、配列がメモリに収まると思います。

サブシーケンスの値を使用するだけです（アルファベットの各文字を0、1、2、3（それぞれ00 01 10 11 ）にマップしvector<bool>ます）サイズalphSize ^ SubSeqLengthの（単純なビットマップ）のインデックスとして。これはより大きなアルファベットですが、シーケンスはより多くのスペースを必要とします.その配列/ビットベクトルのインデックスはサブシーケンスに対応します.

たとえば、サブシーケンス 1030 は 01001100 であるため、インデックスは 76 です。

シーケンスを調べて、それぞれ (seqLength - subSeqLength + 1) を uint 値として取得し、対応する要素を true に設定します。

あなたにあげる

O(seqLength - subSeqLength + 1) = O(seqLength).

入力に各要素 (ASCII 文字列など) のバイト全体がある場合でも、結果配列を設定する前に、シフトおよびマスクしてサブシーケンスのコンパクトな表現を作成できます。これは、サイズが 4 より大きいアルファベットでも機能するはずです。アルファベットのサイズとサブシーケンスの長さが制限要因であることに注意してください。しかし、とにかく完全な出力配列を生成したいので、メモリに収まると思います。

基本的にこれはあなたの提案と同じですが、「arrayPos」は（ほぼ）無料です

于 2013-04-30T17:19:42.263 に答える