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

使用您的具体数字，您可以用两位表示每个元素。由于您想表示最终数组，我假设子序列不能太长，因此该数组适合内存。

只需使用子序列的值（将字母表的每个字符映射到 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 回答
0

这个怎么样：

令 X 保存表示在当前位置结束的子序列（其在布尔向量中的索引）的值。

让 Y 保存值字母大小 ^ 子序列长度（布尔向量的大小或pow( alphSize , subSeqLength )）。

  1. 将 X 设置为 0

  2. 遍历序列和每个步骤：

    1. 将 X 乘以字母大小。
    2. 将序列的当前值添加到 X
    3. 将 X 设置为 X % Y

    这应该等效于在字母大小的基础上添加一个数字并截断第一个数字以使其仅与子序列一样长。

    现在，如果我们至少处于与子序列长度相等的位置，我们可以将布尔向量中 X 处的值设置为 true。

但是，这不会将子序列生成为向量，因此您必须从生成的布尔向量构建它们，这会稍微快一些，因为不能有任何重复。

于 2013-04-30T16:09:29.453 回答