后续搜索

Question

我有大量的列表(总共35 MB),我想搜索子序列:每个术语必须按顺序出现,但不一定是连续出现.所以1,2,3匹配每个

1, 2, 3, 4, 5, 6
1, 2, 2, 3, 3, 3

但不是

6, 5, 4, 3, 2, 1
123, 4, 5, 6, 7

(,是分隔符,而不是要匹配的字符.)

如果没有/1, ([^,]+, )*2, ([^,]+, )*3/在数十或数十万个序列上运行正则表达式(例如),我如何确定哪些序列匹配？我可以预处理序列,但内存使用需要保持合理(在现有序列大小的常数因子内,比方说).最长的序列很短,小于一千字节,因此您可以假设查询也很短.

Answer 1

如果各个数字分散在文件中并且没有出现在大多数行上，那么对它们出现的行号进行简单索引可以提高速度。然而，如果您的数据是以不同顺序重复的相同数字的行，则速度会更慢。

要构建索引只需要按照以下方式传递一次数据：

Hash<int, List<int>> index

line_number = 1
foreach(line in filereader)
{
    line_number += 1
    foreach(parsed_number in line)
        index[parsed_number].append(line)
}

该索引可以被存储并重新用于数据集。要搜索它只需要这样的东西。请原谅混合的伪代码，我已尽力使其尽可能清晰。当没有可能的匹配时，它会“返回”；当子字符串的所有元素都出现在该行上时，它会“产生”行号。

// prefilled hash linking number searched for to a list of line numbers
// the lines should be in ascending order
Hash<int, List<int>> index

// The subsequence we're looking for
List<int> subsequence = {1, 2, 3}
int len = subsequence.length()

// Take all the lists from the index that match the numbers we're looking for
List<List<int>> lines = index[number] for number in subsequence

// holder for our current search row
// has the current lowest line number each element occurs on 
int[] search = new int[len]
for(i = 0; i < len; i++)
    search[i] = lines[i].pop()

while(true)
{
    // minimum line number, substring position and whether they're equal
    min, pos, eq = search[0], 0, true

    // find the lowest line number and whether they all match
    for(i = 0; i < len; i++)
    {
        if(search[i] < min)
            min, p, eq = search[i], i, false
        else if (search[i] > min)
            eq = false
    }

    // if they do all match every one of the numbers occurs on that row
    if(eq)
    {
        yield min; // line has all the elements

        foreach(list in lines)
            if(list.empty())  // one of the numbers isn't in any more lines
                 return

        // update the search to the next lowest line number for every substring element
        for(i = 0; i < len; i++)
            search[i] = lines[i].pop()
    }
    else
    {
        // the lowest line number for each element is not the same, so discard the lowest one
        if(lines[position].empty()) // there are no more lines for the element we'd be updating
            return

        search[position] = lines[position].pop();
    }
}

笔记：

1. 这可以简单地扩展为存储行中的位置以及行号，然后在“yield”点只需一点额外的逻辑就能够确定实际的匹配，而不仅仅是所有项目都存在。

2. 我使用“pop”来显示它如何在行号中移动，但您实际上并不希望每次搜索都破坏索引。

3. 我假设这里的数字都适合整数。如果你有非常大的数字，请将其扩展为 long，甚至将每个数字的字符串表示形式映射为 int。

4. 有一些加速，特别是在“流行”阶段跳线，但我寻求更清晰的解释。

无论使用此方法还是其他方法，您都可以根据数据减少计算量。一次计算出每行是升序、降序、全奇数、全偶数，或者最高和最低数字是什么，可以用来减少每个子字符串的搜索空间。这些是否有用完全取决于您的数据集。