在列表中查找相同的模式

Question

假设我们有以下列表：

    List<int> Journey1 = new List<int>() { 1, 2, 3, 4, 5 };
    List<int> Journey2 = new List<int>() { 2, 3, 4, 6, 7, 3, 4 };
    List<int> Journey3 = new List<int>() { 6, 7, 1 };
    List<int> Journey4 = new List<int>() { 3, 1, 4 };

这些模式是：

2, 3, 4 -> Journey1, Journey2;
6, 7    -> Journey2, Journey3;
1       -> Journey2, Journey3, Journey4;
5       -> Journey1;
3, 4    -> Journey2;
3       -> Journey4;
4       -> Journey4;

我们有5000个列表，每个列表大约有200个项目，所以模式可以有1-200个项目，可以在1-5000个列表中看到。

因此，我需要非常快的方式进行模式匹配。

Answer 1

在没有预计算和简单的即时搜索的情况下：

var matchedJourneys = journeys.Where(x => ContainsPattern(x, mypattern));

bool ContainsPattern(List<int> list, List<int> pattern)
{
    for(int i = 0; i < list.Count - (pattern.Count - 1); i++)
    {
        var match = true;
        for(int j = 0; j < pattern.Count; j++)  
            if(list[i + j] != pattern[j])
                     {
                         match = false;
                         break;
                     }
        if(match) return true;
    }
    return false;
}

这将执行最多2亿个等于检查你的‘数字’。但由于不希望对整个模式执行检查，因此如果检查所有列表，可能需要大约500万次等于操作(只是猜测)。那是几百毫秒。

这完全取决于什么对你来说是“非常快”的。如果这太慢了，你需要一个复杂得多的方法……

Answer 2

对于暴力方法，您可以尝试使用polynomial hash-functions来提速子部分匹配。仍然需要大量的比较，但至少匹配可以几乎是恒定的，而不管子序列长度。

Answer 3

在您的例子中，有机会从模式预处理和文本预处理(http://en.wikipedia.org/wiki/String_searching_algorithm)中获益。

例如，为列表中的所有子序列构建trie将允许在时间上与模式长度成比例地查询该列表中的给定模式。