基於三元組的高效匹配算法

我正在尋找一種有效的方法來解決以下問題。基於三元組的高效匹配算法

表1是由一個原始的三重標識的記錄列表：

X | Y | Z

表2是由三套標識的記錄列表。一個XS，一個YS，一個ZS。 X，Y，Zs與列表1中的類型相同，因此可以直接相互比較。

Set(X) | Set(Y) | Set(Z)

對於列表1，我需要找到在列表2.這一切都在清單2中相對應的組中的項目，其中X，Y，發生來自列表1的所有的Z項目最好是通過一個例子證明：

列表1：

X1, Y1, Z1

列表2：

(X1, X2) | (Y1) | (Z1, Z3) 

(X1) | (Y1, Y2) | (Z1, Z2, Z3) 

(X3) | (Y1, Y3) | (Z2, Z3)

在上面，列表1中的項目將匹配列表2中的前兩個項目。第三個項目不匹配，因爲X1不會出現在X集合中，並且Z1不會出現在Z集合中。

我寫了一個功能正確的算法版本，但我擔心在較大的數據集上的性能。兩個列表都非常大，因此對列表1進行迭代，然後對列表2進行迭代，每個項目的效率都非常低。

我試圖通過將列表2中的每個項目去歸一化爲一個映射來構建索引，但是索引中每個項目的索引條目數量與項目子集的大小成正比。因此，它使用非常高的內存，並且還需要一些重要的資源來構建。

任何人都可以向我建議解決這個問題的最佳方法。我很高興能夠考慮內存和CPU的最佳解決方案，但要實現平衡會很好！

來源

2010-01-04 Scruffers

是否有任何排序，以一組表2中的項目？（即這些東西是否可以對他們有邏輯順序？） – Amber 2010-01-04 20:40:12

Gawd我很困惑。通常「|」意思是「或」而不是「，」和（X1，X2）是指2個元素而不是X1 |的元組X2。我的頭正在旋轉閱讀所有這些東西。 – 2010-01-04 20:41:19

每組中的典型元素數是多少？這只是你例子中的一小部分，還是可以有幾百個？ – 2010-01-04 21:21:28

將會有很多方法來解決這個問題。這是正確的取決於數據和有多少內存可用。

一個簡單的技術是從list2構建一個表，以加速來自list1的查詢。

from collections import defaultdict 

# Build "hits". hits[0] is a table of, for each x, 
# which items in list2 contain it. Likewise hits[1] 
# is for y and hits[2] is for z. 
hits = [defaultdict(set) for i in range(3)] 
for rowid, row in enumerate(list2): 
    for i in range(3): 
     for v in row[i]: 
      hits[i][v].add(rowid) 

# For each row, query the database to find which 
# items in list2 contain all three values. 
for x, y, z in list1: 
    print hits[0][x].intersection(hits[1][y], hits[2][z])

來源

2010-01-04 21:08:53

謝謝賈森，這讓我以完全不同的方式思考問題。我被困在'一個指標'的思路中，但創建三個更靈活。 – Scruffers 2010-01-04 21:34:06

如何使用HashSet（或HashSet S）爲表2？這樣你只需要迭代列表1

來源

2010-01-04 21:16:08

如果列表1和列表2中的項目可以直接比較，那麼這將起作用。但是，我們需要測試列表1中每個項目的每個項目，因爲項目不能直接比較，列表2是驅動程序。 – Scruffers 2010-01-04 21:30:54

在List2包含基元集合和List1包含基元的意義上，不具有可比性？在這種情況下轉換列表2到單個的HashSet（例如{X1，X2，Y1，Z1，Z3}），並通過迭代的List1進行，爲每個成員做快速含有（）上的HashSet。創建哈希集不是免費的，但你可以推理有關的折衷。 – 2010-01-05 06:47:44

大衛，我明白你的觀點，而且這可以奏效。我應該澄清X，Y，Zs實際上只是整數集合，所以在X和Y集合中可能具有相同的值，但這種區別在單個哈希集中會丟失。我很抱歉。 – Scruffers 2010-01-05 10:43:39

如果集合的總大小不是太大，你可以試着將列表2設置爲位域。儘管結構可能會非常分散 - 也許維基百科文章Bit arrays（Judy數組，嘗試，Bloom過濾器）中引用的結構可以幫助解決您的規範化方法的內存問題。

來源

2010-01-04 21:29:38 yawn

您可以在List2之外創建一棵樹;樹的第一層是出現在集合X中的第一個（X1..Xn）。第二層是第二個項目的值，加上包含僅包含X1的列表集合的葉節點。下一個級別包含下一個可能的值，依此類推。

Root --+--X1--+--EOF--> List of pointers to list2 lines containing only "X1" 
     |  | 
     |  +--X2---+--EOF--> List of pointers to list2 lines containing only "X1,X2" 
     |  |  | 
     |  |  +--X3--+--etc-- 
     |  |  
     |  +--X3---+--EOF--> "X1,X3" 
     |    
     +--X2--+--EOF--> "X2" 
     |  | 
     |  +--X3---+--EOF--> "X2,X3" 
     |  |  | 
     ...

這是在內存消耗昂貴（N^2個對數K，我認爲？其中對於X N =值，在列表2 K =行）但是導致快速檢索倍。如果可能的X的數量很大，那麼這種方法會崩潰...

顯然，您可以爲元組的所有3個部分構建此索引，然後將搜索每棵樹的結果與在一起。

來源

2010-01-04 21:30:05

如果使用Guava，有一個高層次的方式來做到這一點，並不一定是最佳但沒有做任何瘋狂：

List<SomeType> list1 = ...; 
List<Set<SomeType>> candidateFromList2 = ...; 
if (Sets.cartesianProduct(candidateFromList2).contains(list1)) { ... }

但它並不難，以檢查這個「 longhand「。

來源

2010-01-05 01:42:30

有一個單傳過來列表2做到這一點相當有效的方式。您首先建立list1中項目的索引。

from collections import defaultdict 

# index is HashMap<X, HashMap<Y, HashMap<Z, Integer>>> 
index = defaultdict(lambda: defaultdict(dict)) 
for rowid, (x, y, z) in enumerate(list1): 
    index[x][y][z] = rowid 

for rowid2, (xs, ys, zs) in enumerate(list2): 
    xhits = defaultdict(list) 
    for x in xs: 
     if x in index: 
      for y, zmap in index[x].iteritems(): 
       xhits[y].append(zmap) 

    yhits = defaultdict(list) 
    for y in ys: 
     if y in xhits: 
      for z, rowid1 in xhits[y].iteritems(): 
       yhits[z].append(rowid1) 

    for z in zs: 
     if z in yhits: 
      for rowid1 in yhits[z]: 
       print "list1[%d] matches list2[%d]" % (hit[z], rowid2)

這裏額外的簿記將可能使它比索引列表2慢。但是因爲在你的情況下list1通常比list2小得多，所以這將使用更少的內存。如果你從磁盤讀取list2，使用這種算法，你永遠不需要將它的任何部分保留在內存中。

內存訪問可以是一個大問題，所以我不能肯定這將是更快的做法說。必須測量。在這兩種情況下，最壞情況下的時間複雜度都是O（len（list1）* len（list2）），除非哈希表出現故障。

來源

2010-01-05 20:41:05

基於三元組的高效匹配算法

回答

相關問題