[發明專利]異常消息篩選方法和裝置以及計算機可讀存儲介質

在審

• 申請號: 201810147696.9
• 申請日: 2018-02-13
• 公開（公告）號: CN110147289A
• 公開（公告）日: 2019-08-20
• 發明（設計）人: 白榮林;徐峰;張帥
• 申請（專利權）人: 北京京東尚科信息技術有限公司;北京京東世紀貿易有限公司
• 主分類號: G06F11/00
• 分類號: G06F11/00
• 代理公司: 中國國際貿易促進委員會專利商標事務所 11038
• 代理人: 李昊;許蓓

本發明公開了一種異常消息篩選方法和裝置以及計算機可讀存儲介質，涉及消息處理領域。異常消息篩選方法包括：獲取消息集合中每條消息的編號，其中，一種編號在消息集合中的出現次數為第一數值，其余的每種編號的出現次數為第二數值；依次輸入消息集合中每條消息的編號，根據狀態更新規則更新統計狀態的值，其中，統計狀態的值包括一個或多個狀態集合中的值，狀態集合中包括第二數值個有序的值，狀態集合中的最后一個值更新后的下一個值為狀態集合中的第一個值；根據最后一次更新后獲得的統計狀態確定消息集合中出現次數為第一數值的編號，以確定異常消息。從而，能夠在空間復雜度為O(1)的情況下篩選異常消息，提高了異常消息的篩選效率。

技術領域

本發明涉及消息處理領域，特別涉及一種異常消息篩選方法和裝置以及計算機可讀存儲介質。

背景技術

在大型的消息處理系統中，每種消息都有固定數量的一系列處理流程，并且具有編號，消息例如可以為指令、數據包等等。當一系列處理流程完成時，系統需要向匯總管道發送經過每個處理流程的消息的編號。例如，每條消息出現3條、消息的種類數為m，在正常情況下，匯總的消息總數應當為m*3。

當部分流程發生異常時，會出現某個編號的消息數量不正常、其他編號的消息數量正常的情況。例如，只有一個編號的消息出現1次，其他消息均出現了3次。為了找出異常消息，相關技術中主要采用哈希表的方式進行查找。即，用哈希表(HashMap)統計每個編號的統計次數，統計完畢后再遍歷一次哈希表，查找出現次數異常的消息。

然而，采用哈希表統計和查找的方式在確定異常消息時效率較低，尤其是在消息量較大的情況下。

發明內容

發明人經過分析后發現，哈希表的空間復雜度為O(n)，即空間復雜度與消息量大小n成線性關系。因此，隨著消息量的增大，查找異常消息時所占用的存儲空間和計算資源也會急劇增長，因而導致了效率低下。

本發明實施例所要解決的一個技術問題是：如何提高異常消息的篩選效率。

根據本發明一些實施例的第一個方面，提供一種異常消息篩選方法，包括：獲取消息集合中每條消息的編號，其中，一種編號在消息集合中的出現次數為第一數值，其余的每種編號在消息集合中的出現次數為第二數值；依次輸入消息集合中每條消息的編號，根據狀態更新規則更新統計狀態的值，其中，統計狀態的值包括一個或多個狀態集合中的值，狀態集合中包括第二數值個有序的值，狀態集合中的最后一個值更新后的下一個值為狀態集合中的第一個值；根據最后一次更新后獲得的統計狀態確定消息集合中出現次數為第一數值的編號，以確定出現次數為第一數值的編號對應的異常消息。

在一些實施例中，統計狀態包括編號的各個二進制位上的位統計狀態，每個位統計狀態包括一個或多個比特、并且值為狀態集合中的值，狀態集合中的值為二進制數。

在一些實施例中，狀態轉移規則包括：位的輸入值為1時，令位統計狀態的值轉移到狀態集合中的下一個值；位的輸入值為0時，位統計狀態的值不變。

在一些實施例中，異常消息篩選方法還包括：建立真值表，真值表中的每一行包括原位統計狀態變量的值、輸入變量的值以及根據原位統計狀態變量的值和輸入變量的值確定的更新后的位統計狀態變量的值；根據真值表，采用位原統計狀態變量、輸入變量的各個比特之間的邏輯關系表示更新后的位統計狀態變量，建立狀態更新規則。

在一些實施例中，根據真值表，采用位原統計狀態變量、輸入變量的各個比特之間的邏輯關系表示更新后的位統計狀態變量，建立狀態更新規則包括：對于真值表中位統計狀態變量的值為1的各個行，在將行中的原位統計狀態變量的每個比特和位輸入變量中值為0的變量取反后，將行中的原位統計狀態變量的每個比特以及位輸入變量進行與運算；對于真值表中更新后的位統計狀態的同一個比特，將每個比特值為1的行的與運算結果進行或運算，獲得同一個比特的狀態更新規則。