[發(fā)明專利]一種子圖匹配方法、裝置、設備及存儲介質(zhì)

在審

• 申請?zhí)枺?/td>: 202011623281.8
• 申請日: 2020-12-30
• 公開（公告）號: CN112667860A
• 公開（公告）日: 2021-04-16
• 發(fā)明（設計）人: 劉元弘;王釗
• 申請（專利權(quán)）人: 海南普適智能科技有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/9035;G06F16/903
• 代理公司: 北京集佳知識產(chǎn)權(quán)代理有限公司 11227
• 代理人: 劉翠香

1.一種子圖匹配方法，其特征在于，包括：

根據(jù)預設的查詢規(guī)則構(gòu)建查詢圖，所述查詢圖為一層或多層樹結(jié)構(gòu)，包括多個查詢節(jié)點，每個查詢節(jié)點具有各自的節(jié)點類型，查詢節(jié)點之間的邊表示查詢節(jié)點間關系；

根據(jù)所述查詢圖的各查詢節(jié)點類型和查詢節(jié)點間關系，對原始圖進行點邊過濾處理，獲得目標圖；

確定所述目標圖中與所述查詢圖匹配的子圖。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述根據(jù)所述查詢圖的各查詢節(jié)點類型和查詢節(jié)點間關系，對原始圖進行點邊過濾處理，獲得目標圖，包括：

根據(jù)所述查詢圖的各查詢節(jié)點類型，將原始圖中不具有相應節(jié)點類型的節(jié)點過濾掉；

根據(jù)所述查詢圖的查詢節(jié)點間關系，將所述原始圖中不具有相應節(jié)點間關系的節(jié)點過濾掉；

將過濾后的所述原始圖確定為目標圖。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述確定所述目標圖中與所述查詢圖匹配的子圖，包括：

將所述查詢圖的層數(shù)確定為迭代輪數(shù)N，并初始化所述目標圖中每個目標節(jié)點的局部匹配狀態(tài)信息，N為正整數(shù)；

在第一輪迭代中，針對所述目標圖中的每個目標節(jié)點，將該目標節(jié)點與所述查詢圖中的根節(jié)點進行匹配，如果匹配成功，則更新該目標節(jié)點的局部匹配狀態(tài)信息，并將該目標節(jié)點更新后的局部匹配狀態(tài)信息發(fā)送給該目標節(jié)點的所有鄰居節(jié)點；

在第n輪迭代中，針對所述目標圖中的每個目標節(jié)點，如果該目標節(jié)點接收到該目標節(jié)點的鄰居節(jié)點發(fā)送的局部匹配狀態(tài)信息，則基于接收到的局部匹配狀態(tài)信息，將該目標節(jié)點與所述查詢圖中的第n層相對應的查詢節(jié)點進行匹配，如果匹配成功，則更新該目標節(jié)點的局部匹配狀態(tài)信息，將該目標節(jié)點更新后的局部匹配狀態(tài)信息發(fā)送給該目標節(jié)點的除向該目標節(jié)點發(fā)送信息的鄰居節(jié)點外的其他所有鄰居節(jié)點，n＝2,3,…,N-1；

在第N輪迭代中，針對所述目標圖中的每個目標節(jié)點，如果該目標節(jié)點接收到該目標節(jié)點的鄰居節(jié)點發(fā)送的局部匹配狀態(tài)信息，則基于接收到的局部匹配狀態(tài)信息，將該目標節(jié)點與所述查詢圖中的第N層相對應的查詢節(jié)點進行匹配，如果匹配成功，則更新該目標節(jié)點的局部匹配狀態(tài)信息；

根據(jù)所述目標圖中每個目標節(jié)點的局部匹配狀態(tài)信息，確定所述目標圖中與所述查詢圖匹配的子圖。

4.根據(jù)權(quán)利要求3所述的方法，其特征在于，所述局部匹配狀態(tài)信息包括：

用于記錄已經(jīng)匹配上的所述目標圖中目標節(jié)點與對應的所述查詢圖中查詢節(jié)點的信息、

用于記錄下一輪迭代將要進行匹配的所述查詢圖中查詢節(jié)點的信息、

用于記錄當前子圖的起始節(jié)點信息；

所述根據(jù)所述目標圖中每個目標節(jié)點的局部匹配狀態(tài)信息，確定所述目標圖中與所述查詢圖匹配的子圖，包括：

基于所述目標圖中每個目標節(jié)點的局部匹配狀態(tài)信息，將具有相同起始節(jié)點信息的局部匹配狀態(tài)信息分到一組；

針對每一組，如果該組中的局部匹配狀態(tài)信息的數(shù)量大于或等于所述查詢圖中查詢節(jié)點的數(shù)量，則基于每個查詢節(jié)點的數(shù)量及每個查詢節(jié)點所連接的邊的條數(shù)，確定該組對應的子圖是否為與所述查詢圖匹配的子圖。

5.根據(jù)權(quán)利要求4所述的方法，其特征在于，所述基于每個查詢節(jié)點的數(shù)量及每個查詢節(jié)點所連接的邊的條數(shù)，確定該組對應的子圖是否為與所述查詢圖匹配的子圖，包括：

基于該組中匹配規(guī)則信息，確定該組已經(jīng)匹配上的查詢節(jié)點的數(shù)量；

如果該組已經(jīng)匹配上的查詢節(jié)點的數(shù)量符合所述查詢圖中查詢節(jié)點的邏輯數(shù)量關系，且每個已經(jīng)匹配上的查詢節(jié)點的數(shù)量及每個已經(jīng)匹配上的查詢節(jié)點所連接的邊的條數(shù)均匹配，則將該組對應的子圖確定為與所述查詢圖匹配的子圖。

6.根據(jù)權(quán)利要求5所述的方法，其特征在于，在該組中的局部匹配狀態(tài)信息的數(shù)量大于或等于所述查詢圖中查詢節(jié)點的數(shù)量、且該組已經(jīng)匹配上的查詢節(jié)點的數(shù)量符合所述查詢圖中查詢節(jié)點的邏輯數(shù)量關系的情況下，在所述將該組對應的子圖確定為與所述查詢圖匹配的子圖之前，還包括：

判斷該組中與起始節(jié)點信息中的目標節(jié)點相鄰的節(jié)點比例是否符合預設的比例條件；

如果符合，則執(zhí)行所述將該組對應的子圖確定為與所述查詢圖匹配的子圖的步驟。