質問編集履歴
1
追加
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -90,4 +90,183 @@
|
|
|
90
90
|
|
|
91
91
|
上記は[こちらのサイト](https://ics.media/entry/7298/)を元にselenium部分を追加しました。
|
|
92
92
|
|
|
93
|
-
ご教示願います。
|
|
93
|
+
ご教示願います。
|
|
94
|
+
|
|
95
|
+
```python
|
|
96
|
+
import random
|
|
97
|
+
import networkx as nx
|
|
98
|
+
import matplotlib.pyplot as plt
|
|
99
|
+
import copy
|
|
100
|
+
|
|
101
|
+
#要素が重複しているか
|
|
102
|
+
def has_duplicates(seq):
|
|
103
|
+
return len(seq) == len(set(seq))
|
|
104
|
+
|
|
105
|
+
def create_volumes(n):
|
|
106
|
+
#重複しないレコードの作成
|
|
107
|
+
V = random.sample(range(5,260), k=n)
|
|
108
|
+
#観測されるボリューム集合の生成
|
|
109
|
+
W = copy.copy(V)
|
|
110
|
+
for i in range(N-1):
|
|
111
|
+
W.append(V[i]+V[i+1])
|
|
112
|
+
return V, W
|
|
113
|
+
|
|
114
|
+
#候補解から生成されるボリュームを観測したボリュームと比較
|
|
115
|
+
def compare_volumes(S, W):
|
|
116
|
+
T = set()
|
|
117
|
+
#観測されるボリューム集合の生成
|
|
118
|
+
for s in S:
|
|
119
|
+
w = copy.copy(s)
|
|
120
|
+
for i in range(N-1):
|
|
121
|
+
w.append(s[i]+s[i+1])
|
|
122
|
+
if set(w) == set(W):
|
|
123
|
+
#print(tuple(s))
|
|
124
|
+
T.add(tuple(s))
|
|
125
|
+
return T
|
|
126
|
+
|
|
127
|
+
|
|
128
|
+
#１つ以上重複しているボリュームを作成(レコードは重複していない)
|
|
129
|
+
def create_duplicates(n):
|
|
130
|
+
data = create_volumes(n)
|
|
131
|
+
if has_duplicates(data[1]): #重複していないならば
|
|
132
|
+
return create_duplicates(n)
|
|
133
|
+
else:
|
|
134
|
+
return data
|
|
135
|
+
|
|
136
|
+
def create_no_duplicates(n):
|
|
137
|
+
data = create_volumes(n)
|
|
138
|
+
#print(data[1])
|
|
139
|
+
if has_duplicates(data[1]):
|
|
140
|
+
return data
|
|
141
|
+
else:
|
|
142
|
+
return create_duplicates(n)
|
|
143
|
+
|
|
144
|
+
|
|
145
|
+
Ans = []
|
|
146
|
+
N = 26 #攻撃者は既知
|
|
147
|
+
result = create_duplicates(N)
|
|
148
|
+
#result = create_no_duplicates(N)
|
|
149
|
+
V = result[0] #復元したいレコード
|
|
150
|
+
print("V = " + str(V))
|
|
151
|
+
print("W = " + str(result[1]))
|
|
152
|
+
W = list(set(result[1])) #攻撃者が観測するボリュームの集合
|
|
153
|
+
|
|
154
|
+
|
|
155
|
+
#要素を昇順に
|
|
156
|
+
W.sort()
|
|
157
|
+
print("昇順W = " + str(W) + " ( |W| = " + str(len(W)) +" )")
|
|
158
|
+
|
|
159
|
+
G = nx.Graph()
|
|
160
|
+
#step1 ２頂点の和がボリュームに含まれているのならエッジを追加
|
|
161
|
+
#連結しているて頂点のみをエッジごと抽出
|
|
162
|
+
n = len(W)
|
|
163
|
+
for i in range(n-2):
|
|
164
|
+
for j in range(i+1,n-1):
|
|
165
|
+
if W[i] + W[j] in W:
|
|
166
|
+
G.add_edge(W[i], W[j])
|
|
167
|
+
|
|
168
|
+
print("存在する枝 = " + str(G.edges))
|
|
169
|
+
print("抽出されたボリューム(" + str(len(G.nodes)) +"/" + str(len(W)) +") = " + str(G.nodes))
|
|
170
|
+
print(list(G.neighbors(W[0])))
|
|
171
|
+
|
|
172
|
+
#step2 確定レコード選別する
|
|
173
|
+
RNodes = [W[0], W[1]] #レコードは重複しない仮定より1,2番目に小さいボリュームはレコードである
|
|
174
|
+
for i in range(2, N):
|
|
175
|
+
for j in range(i):
|
|
176
|
+
#print("W[i] - W[j] = " + str(W[i]) + " - " + str(W[j]))
|
|
177
|
+
if W[i] - W[j] in W and W[i] != 2 * W[j] : #あるボリュームが確定レコード同士の和である時(その要素が隣同士orレコードであるor両方)
|
|
178
|
+
break
|
|
179
|
+
#else: 和でない場合は次に進める
|
|
180
|
+
#最終的にそのボリュームを生成する確定レコードの２要素の和が存在しない場合、そのボリューム確定レコード
|
|
181
|
+
if j == i-1:
|
|
182
|
+
RNodes.append(W[i])
|
|
183
|
+
|
|
184
|
+
print("確定レコード = " + str(RNodes))
|
|
185
|
+
|
|
186
|
+
|
|
187
|
+
|
|
188
|
+
#step3 確定レコードである頂点を通る経路長＝N-1である経路
|
|
189
|
+
S = []
|
|
190
|
+
#//集合の中にリストの集合
|
|
191
|
+
l = list(G.neighbors(W[0]))
|
|
192
|
+
|
|
193
|
+
for i in l: #一次元配列だとループが回せないため、二次元配列にしておく
|
|
194
|
+
S.append([W[0],i])
|
|
195
|
+
|
|
196
|
+
def right_shift(S,G):
|
|
197
|
+
#print("S = " + str(S))
|
|
198
|
+
for i in range(N-2): #解の長さがNになるまで
|
|
199
|
+
T = []
|
|
200
|
+
for s in S: #解の数
|
|
201
|
+
if len(s) != N:
|
|
202
|
+
right_num = len(s) - 1
|
|
203
|
+
l = list(G.neighbors(s[right_num]))#一番右の要素と隣合うノードを取得
|
|
204
|
+
for node in l:
|
|
205
|
+
if node not in s: #同じレコードは存在しないかの判定
|
|
206
|
+
C = copy.copy(s)
|
|
207
|
+
C.append(node)
|
|
208
|
+
if C not in T:
|
|
209
|
+
T.append(C)
|
|
210
|
+
T.append(s)#右に拡張できるがそのノードが終点である可能性があるため
|
|
211
|
+
#print(T)
|
|
212
|
+
S = copy.copy(T)
|
|
213
|
+
#print("S = " + str(S))
|
|
214
|
+
return S
|
|
215
|
+
|
|
216
|
+
#S = right_shift(S)
|
|
217
|
+
|
|
218
|
+
#左に拡張
|
|
219
|
+
def left_shift(S,G):
|
|
220
|
+
for i in range(N-2):
|
|
221
|
+
T = []
|
|
222
|
+
for s in S:
|
|
223
|
+
#print("s = " + str(s))
|
|
224
|
+
if len(s) != N:
|
|
225
|
+
l = list(G.neighbors(s[0]))
|
|
226
|
+
for node in l:
|
|
227
|
+
if node not in s: #同じレコードは存在しないかの判定
|
|
228
|
+
C = copy.copy(s)
|
|
229
|
+
C.insert(0,node) #先頭に要素を追加
|
|
230
|
+
if C not in T:
|
|
231
|
+
T.append(C)
|
|
232
|
+
T.append(s)
|
|
233
|
+
S = copy.copy(T)
|
|
234
|
+
#print("s = " + str(S))
|
|
235
|
+
return S
|
|
236
|
+
|
|
237
|
+
#step4 確定コードが解に含まれているか 現段階では確定レコードを通る効率的なアルゴリズムが考えられていないため
|
|
238
|
+
def confirm(S):
|
|
239
|
+
T = []
|
|
240
|
+
for s in S:
|
|
241
|
+
if len(s) == N:
|
|
242
|
+
for i in range(len(RNodes)):
|
|
243
|
+
if RNodes[i] not in s:
|
|
244
|
+
break
|
|
245
|
+
if i == len(RNodes)-1:
|
|
246
|
+
T.append(s)
|
|
247
|
+
return T
|
|
248
|
+
T = copy.copy(S)
|
|
249
|
+
T = right_shift(T,G)
|
|
250
|
+
T = left_shift(T,G)
|
|
251
|
+
S = left_shift(S,G)
|
|
252
|
+
S = right_shift(S,G)
|
|
253
|
+
#print("解候補 = " + str(T))
|
|
254
|
+
print("解の数1 = " + str(len(T)))
|
|
255
|
+
T = confirm(T)
|
|
256
|
+
S = confirm(S)
|
|
257
|
+
#print("解候補選別T = " + str(T))
|
|
258
|
+
#print("解候補選別S = " + str(S))
|
|
259
|
+
print("解の数2 = " + str(len(T)))
|
|
260
|
+
|
|
261
|
+
|
|
262
|
+
#step5 解からボリュームを計算し比較
|
|
263
|
+
G1 = compare_volumes(T, W)
|
|
264
|
+
#print("G1 = " + str(G1))
|
|
265
|
+
G2 = compare_volumes(S, W)
|
|
266
|
+
#print("G2 = " + str(G2))
|
|
267
|
+
G3 = G1|G2
|
|
268
|
+
|
|
269
|
+
print("候補解(" + str(len(G3)) + "個) = " + str(G3))
|
|
270
|
+
print("真の解 = " + str(V))
|
|
271
|
+
|
|
272
|
+
```
|