[發明專利]一種基于云服務的模式串匹配驗證方法及裝置

有效

• 申請號: 201611046778.1
• 申請日: 2016-11-23
• 公開（公告）號: CN106776791B
• 公開（公告）日: 2019-12-10
• 發明（設計）人: 陳飛;王東宏;熊馨雨;陳劍勇
• 申請（專利權）人: 深圳大學
• 主分類號: G06F16/903
• 分類號: G06F16/903
• 代理公司: 44350 深圳青年人專利商標代理有限公司
• 代理人: 吳桂華

1.一種基于云服務的模式串匹配驗證方法，其特征在于，所述方法包括：

數據擁有端根據預先存儲的文本串，生成關聯的查詢數據結構，所述查詢數據結構包括所述文本串的后綴數組和最長公共前綴數組；

所述數據擁有端根據預設的哈希函數，生成所述文本串關聯的可驗證數據結構，所述可驗證數據結構包括第一累加值集合、第二累加值集合、第一哈希樹和第二哈希樹；

所述數據擁有端將所述查詢數據結構和所述可驗證數據結構發送給預設云服務器，并將所述哈希函數向數據訪問端發布，將所述第一哈希樹根節點的累加值和所述第二哈希樹根節點的累加值設置為所述文本串關聯的驗證參數并發送給所述數據訪問端；

所述云服務器接收到所述數據訪問端的模式串匹配查詢請求時，獲取所述模式串匹配查詢請求中的待匹配模式串；

所述云服務器將所述待匹配模式串與預先存儲的所述文本串進行匹配；

當所述待匹配模式串在所述文本串中匹配成功時，所述云服務器根據所述文本串關聯的查詢數據結構和可驗證數據結構，獲取匹配成功的驗證證據，并將所述匹配成功的結果和所述匹配成功的驗證證據發送給所述數據訪問端，所述可驗證數據結構由數據擁有端通過所述哈希函數對所述文本串進行預處理得到；

所述數據訪問端根據所述待匹配模式串、所述匹配成功的驗證證據以及與所述文本串關聯的驗證參數，確定所述匹配成功的結果是否正確；

所述數據擁有端根據所述哈希函數，生成所述文本串關聯的可驗證數據結構的步驟，包括：

所述數據擁有端通過所述哈希函數計算所述文本串中每個后綴字符串的累加值，并將所述所有后綴字符串的累加值存儲在所述第一累加值集合中；

所述數據擁有端根據所述后綴數組和所述第一累加值集合，生成多個后綴元組，根據所述后綴元組和所述后綴數組，構建所述第一哈希樹并獲取所述第一哈希樹根節點的累加值；

所述數據擁有端根據所述后綴數組和所述最長公共前綴數組，生成多個匹配元組，通過所述哈希函數計算所述匹配元組集合中每個匹配元組的累加值，并將所述所有匹配元組的累加值存儲在所述第二累加值集合中；

所述數據擁有端根據所述第二累加值集合，構建所述第二哈希樹并獲取所述第二哈希樹根節點的累加值；

當所述待匹配模式串在所述文本串中匹配成功時，所述云服務器根據所述文本串關聯的查詢數據結構和可驗證數據結構，獲取匹配成功的驗證證據的步驟，包括：

獲取所述待匹配模式串在所述文本串中的當前匹配位置，根據所述查詢數據結構，獲取預設數量個匹配元組，所述預設數量個匹配元組中包含所述待匹配模式串在所述文本串中所有匹配成功的匹配位置；

根據所述當前匹配位置和所述待匹配模式串，在所述第一累加值集合中查找相關后綴字符串的累加值，并根據所述第一哈希樹，獲取用于驗證所述待匹配模式串是否存在于所述文本串中的證據，將所述證據設置為第一子證據；

在所述第二累加值集合中查找所述預設數量個匹配元組中預設位置處匹配元組的累加值，并根據所述第二哈希樹，獲取用于驗證所述預設數量個匹配元組中開始位置處匹配元組是否真實的證據，并將所述證據設置為第二子證據；

根據所述當前匹配位置、預設數量個匹配元組、相關后綴字符串的累加值、第一子證據、預設位置處匹配元組的累加值以及所述第二子證據，生成所述匹配成功的驗證證據。

2.如權利要求1所述的方法，其特征在于，所述數據訪問端根據所述待匹配模式串、所述匹配成功的驗證證據以及與所述文本串關聯的驗證參數，確定所述匹配成功的結果是否正確的步驟，包括：

根據所述待匹配模式串、所述哈希函數以及所述相關后綴字符串的累加值，計算所述當前匹配位置在所述文本串中所對應后綴字符串的累加值，通過所述累加值、后綴數組、所述第一子證據以及所述第一哈希樹根節點的累加值，確定所述當前匹配位置是否正確；

根據所述待匹配模式串、所述哈希函數以及所述預設位置處匹配元組的累加值，計算所述預設數量個匹配元組中開始位置處匹配元組的累加值，并根據所述累加值、所述第二子證據以及所述第二哈希樹根節點的累加值，確定所述預設數量個匹配元組包含的所有匹配位置中剩余匹配位置是否正確；

當確定所述當前匹配位置和所述剩余匹配位置正確時，確定所述匹配成功的結果正確。