查找列表

假設同樣的模式，我們有如下列表：查找列表

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列表中查看。

因此我需要非常快速的模式匹配方式。

來源

2012-02-13 Behnam

你能解釋規則嗎？例如。爲什麼它不是'3 - > Journey1，Journey2，Journey4' – Blorgbeard 2012-02-13 17:41:37

哦，模式是（序列）=>（要搜索的列表清單）？ – Blorgbeard 2012-02-13 17:43:42

我們需要找到從最長到最短的圖案，因此我首先選擇2,3,4，這是在多次旅程中看到的最長的圖案。 – Behnam 2012-02-20 10:01:47

沒有預計算，用天真的即時搜索：

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萬等於操作。這是幾百毫秒。

這一切都取決於什麼是'非常快'的你。如果這太慢，你將需要更復雜的方法...

來源

2012-02-13 18:17:08 doblak

這是n^2，它不會創建模式來查找。只是將模式匹配到列表。這只是一半的工作。 – 2012-02-13 18:26:25

目前還不清楚這些模式是已知還是尚未找到。我認爲它們是已知的，因爲這個問題給我們提供了像'1'和'5'這樣的'單個'項目模式（並且通過機器學習發現這種模式沒有意義）。 – doblak 2012-02-13 18:31:13

非常感謝Darjan，但由於jb表示它不創建模式，它應該開始創建模式，創建模式，我們有一個簡單的角色，每個模式至少應該在一次Journey中看到。在進程結束時，如果有些節點仍然處於沒有任何模式的列表中，我們會將它們添加爲新模式。 – Behnam 2012-02-14 10:55:32

我不知道你想要什麼作爲輸出。我只是做了一個嘗試。

我建議你列出一個列表，而不是聲明單個列表變量。

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

列表編號從零開始。

來源

2012-02-13 18:55:34

對於暴力破解方法，您可以嘗試使用polynomial hash-functions加快子部分匹配。仍然需要瘋狂的比較次數，但至少匹配幾乎可以保持不變，而不考慮子序列的長度。

來源

2012-02-13 19:03:47

在你的情況下，有機會受益於模式預處理和文本預處理（http://en.wikipedia.org/wiki/String_searching_algorithm）。

例如，爲列表中的所有子序列構造一個trie將允許在時間上與該模式長度成比例地查詢給定模式的該列表。

來源

2012-02-15 23:13:40

回答

相關問題