在列表中查找相同的模式

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

我不确定你想要什么作为输出。我刚刚尝试了一下。

我建议您创建一个列表列表，而不是声明单独的列表变量。

List<List<int>> journeys = new List<List<int>>();
journeys.Add(new List<int>() { 1, 2, 3, 4, 5 });
journeys.Add(new List<int>() { 2, 3, 4, 6, 7, 3, 4 });
journeys.Add(new List<int>() { 6, 7, 1 });
journeys.Add(new List<int>() { 3, 1, 4 });

我假设数字范围从 0 到 255。通过此查询

var result = Enumerable.Range(0, 256)
    .Select(number => new
    {
        number,
        listIndexes = journeys
            .Select((list, index) => new { index, list })
            .Where(a => a.list.Contains(number))
            .Select(a => a.index)
            .ToList()
    })
    .Where(b => b.listIndexes.Count > 0)
    .ToList();

和此测试循环，

foreach (var item in result) {
    Console.Write("Number {0} occurs in list # ", item.number);
    foreach (var index in item.listIndexes) {
        Console.Write("{0} ", index);
    }
    Console.WriteLine();
}

您将得到此结果

    Number 1 occurs in list # 0 2 3 
    Number 2 occurs in list # 0 1 
    Number 3 occurs in list # 0 1 3 
    Number 4 occurs in list # 0 1 3 
    Number 5 occurs in list # 0 
    Number 6 occurs in list # 1 2 
    Number 7 occurs in list # 1 2 

，其中列表编号从零开始。

Answer 3

对于暴力方法，您可以尝试使用多项式哈希函数来加速子部分匹配。仍然需要疯狂的比较次数，但至少匹配可以几乎恒定，而不管子序列长度如何。

Answer 4

在您的情况下，有机会从模式预处理和文本预处理中受益（http://en.wikipedia.org/wiki/String_searching_algorithm）。

例如，为列表中的所有子序列构建一个字典树将允许在与模式长度成比例的时间内查询该列表以查找给定模式。