Dict在Python中的解構和重構

Question

我有多個詞典。字典之間有很多重疊，但它們並不完全相同。

a = {'a':1,'b':2,'c':3} 
b = {'a':1,'c':3, 'd':4} 
c = {'a':1,'c':3} 

我試圖找出如何打破這些分解成最原始的片，然後在最有效的方式重建的字典。換句話說，我怎樣才能解構和重建的字典鍵入每個鍵/值對的最少次數（理想情況下一次）。這也意味着創建可以組合起來創建所有可能集合的最小數量的集合。

在上面的例子中。它可以細分爲：

c = {'a':1,'c':3} 
a = dict(c.items() + {'b':2}) 
b = dict(c.items() + {'d':4}) 

我在尋找關於如何在Python中實現這一點的建議。

實際上，我大概有60本字典，其中很多都有重疊的值。我試圖儘量減少輸入每個k/v對的次數，以最大限度地減少可能的拼寫錯誤，並使其更容易級聯更新特定鍵的不同值。

理想的輸出將是構建所有字典所需的最基本的字典以及重建公式。

Answer 1

這是一個解決方案。這不是最有效的方法，但它可能會讓你知道如何繼續。

a = {'a':1,'b':2,'c':3} 
b = {'a':1,'c':3, 'd':4} 
c = {'a':1,'c':3} 

class Cover: 
    def __init__(self,*dicts): 
     # Our internal representation is a link to any complete subsets, and then a dictionary of remaining elements 
     mtx = [[-1,{}] for d in dicts] 
     for i,dct in enumerate(dicts): 
      for j,odct in enumerate(dicts): 
       if i == j: continue # we're always a subset of ourself 
       # if everybody in A is in B, create the reference 
       if all(k in dct for k in odct.keys()): 
        mtx[i][0] = j 
        dif = {key:value for key,value in dct.items() if key not in odct} 
        mtx[i][1].update(dif) 
        break 

     for i,m in enumerate(mtx): 
      if m[1] == {}: m[1] = dict(dicts[i].items()) 

     self.mtx = mtx 

    def get(self, i): 
     r = { key:val for key, val in self.mtx[i][1].items()} 
     if (self.mtx[i][0] > 0): # if we had found a subset, add that 
      r.update(self.mtx[self.mtx[i][0]][1]) 
     return r 


cover = Cover(a,b,c) 

print(a,b,c) 
print('representation',cover.mtx) 
# prints [[2, {'b': 2}], [2, {'d': 4}], [-1, {'a': 1, 'c': 3}]] 
# The "-1" In the third element indicates this is a building block that cannot be reduced; the "2"s indicate that these should build from the 2th element 
print('a',cover.get(0)) 
print('b',cover.get(1)) 
print('c',cover.get(2)) 

的想法很簡單：如果有任何地圖都完整的子集，代替重複的參考。壓縮肯定會適得其反某些矩陣組合，並且可在

簡單的改進

變化在問題得到，或使用更簡潔的字典附加碼暗示第一線容易地改善，可能立即提高可讀性。

我們不檢查最大的子集，這可能是值得的。

實現是幼稚和不作任何優化

較大的改進

人們還可以實現在「積木」字典形成的根結點和樹的後代建立一個分層實施更大的字典。如果你的數據分層開始，這將是有益的。

（注：在python3測試）

Answer 2

下面的腳本來生成重建的字典的腳本。

例如，考慮本詞典辭書：

>>>dicts 
{'d2': {'k4': 'k4', 'k1': 'k1'}, 
'd0': {'k2': 'k2', 'k4': 'k4', 'k1': 'k1', 'k3': 'k3'}, 
'd4': {'k4': 'k4', 'k0': 'k0', 'k1': 'k1'}, 
'd3': {'k0': 'k0', 'k1': 'k1'}, 
'd1': {'k2': 'k2', 'k4': 'k4'}} 

爲了清楚起見，我們用套繼續，因爲關聯密鑰值可以在其他地方進行。

sets= {k:set(v.keys()) for k,v in dicts.items()} 

>>>sets 
{'d2': {'k1', 'k4'}, 
'd0': {'k1', 'k2', 'k3', 'k4'}, 
'd4': {'k0', 'k1', 'k4'}, 
'd3': {'k0', 'k1'}, 
'd1': {'k2', 'k4'}} 

現在計算的距離（鍵的數量增加和/或刪除去從一個字典到另一個）：

df=pd.DataFrame(dicts) 
charfunc=df.notnull() 
distances=pd.DataFrame((charfunc.values.T[...,None] != charfunc.values).sum(1), 
         df.columns,df.columns) 

>>>>distances 
    d0 d1 d2 d3 d4 
d0 0 2 2 4 3 
d1 2 0 2 4 3 
d2 2 2 0 2 1 
d3 4 4 2 0 1 
d4 3 3 1 1 0 

然後就是寫劇本的腳本。我們的想法是用最短的設定開始，然後在每一步構建從那些已經建立了最近的一組：

script=open('script.py','w') 
dicoto=df.count().argmin() # the shortest set 
script.write('res={}\nres['+repr(dicoto)+']='+str(sets[dicoto])+'\ns=[\n') 
done=[] 
todo=df.columns.tolist() 
while True : 
    done.append(dicoto) 
    todo.remove(dicoto) 
    if not todo : break 
    table=distances.loc[todo,done] 
    ito,ifrom=np.unravel_index(table.values.argmin(),table.shape) 
    dicofrom=table.columns[ifrom] 
    setfrom=sets[dicofrom] 
    dicoto=table.index[ito] 
    setto=sets[dicoto] 
    toadd=setto-setfrom 
    toremove=setfrom-setto 
    script.write(('('+repr(dicoto)+','+str(toadd)+','+str(toremove)+',' 
    +repr(dicofrom)+'),\n').replace('set','')) 
script.write("""] 
for dt,ta,tr,df in s: 
    d=res[df].copy() 
    d.update(ta) 
    for k in tr: d.remove(k) 
    res[dt]=d 
""")  
script.close() 

和生成的文件script.py

res={} 
res['d1']={'k2', 'k4'} 
s=[ 
('d0',{'k1', 'k3'},(),'d1'), 
('d2',{'k1'},{'k2'},'d1'), 
('d4',{'k0'},(),'d2'), 
('d3',(),{'k4'},'d4'), 
] 
for dt,ta,tr,df in s: 
    d=res[df].copy() 
    d.update(ta) 
    for k in tr: d.remove(k) 
    res[dt]=d 

測試：

>>> %run script.py 
>>> res==sets 
True 

隨着這裏的隨機字典的使用，腳本大小約爲大字典集大小的80％（Nd=Nk=100）。但是，如果重疊很大，這個比例肯定會更好。

補充：生成此類字典的腳本。

from pylab import * 
import pandas as pd 
Nd=5 # number of dicts 
Nk=5 # number of keys per dict 
index=['k'+str(j) for j in range(Nk)] 
columns=['d'+str(i) for i in range(Nd)] 
charfunc=pd.DataFrame(randint(0,2,(Nk,Nd)).astype(bool),index=index,columns=columns) 
dicts={i : { j:j for j in charfunc.index if charfunc.ix[j,i]} for i in charfunc.columns}