[發明專利]一種基于并行環路檢測的虛開增值稅專用發票檢測方法

有效

• 申請號: 201710147850.8
• 申請日: 2017-03-14
• 公開（公告）號: CN106920162B
• 公開（公告）日: 2021-01-29
• 發明（設計）人: 丁軍;張宇;牛臻;劉卓瑞;謝峰;劉海明;盧華
• 申請（專利權）人: 西京學院
• 主分類號: G06Q40/00
• 分類號: G06Q40/00
• 代理公司: 西安西達專利代理有限責任公司 61202
• 代理人: 郭秋梅

1.一種基于并行環路檢測的虛開增值稅專用發票檢測方法，其特征在于，包括以下步驟：

1）構建數據結構來對圖數據進行存儲；

2）采用了BSP總體同步并行計算模型思想作為算法的主體；

3）數據存儲單元會將圖數據分布式的保存在各個計算節點中，在每個超級步中，集群中的各個進程，也就是Processors會提取數據存儲單元中的數據來進行計算；每一個超級步中包含計算主要分成3個部分，分別為Vprog點初始化，SendMsg分發信息，MergeMsg結合信息；所述的Vprog點初始化表示將設定的初始化程序運行在每一個頂點中，負責接收進來的信息，計算新的頂點信息，并將滿足條件的點進行激活；所述的SendMsg分發信息是指被激活的點會向它的下一個節點進行信息傳遞，由于分布式計算，SendMsg傳來的信息會有多條；所述的MergeMsg結合信息則負責將這些多條信息安裝一定的規則整合到一起，再交給Vprog；

4）Vprog點初始化負責在每個超級步的初始階段，對每個頂點的信息進行初始化以及更新；

5）SendMsg分發信息模塊負責生成路由信息同時檢測環路，對各類的情況進行分析設計，頂點的數據結構定義為 Int VertexId，String route,Int round,Int flag，同時已知flag為點屬性中保存標志位信息，且數值0表示該頂點從來沒有被激活過，1表示該頂點被激活，2表示該頂點曾經被激活過但現在處于未激活狀態，所以在SendMsg階段，就需要通過標志位信息調用不同的send方法；在進行SendMsg分發信息時，源節點一定處于激活狀態；

6）MergeMsg結合信息是這個算法主體的最后一個部分，MergeMsg結合信息會將SendMsg暫存的信息以設定的方法，將信息結合到一起，并賦給newMsg，MergeMsg模塊主要分成2類情況來進行分析；

a更新節點的節點信息都是來自上一層節點；

b更新節點的信息除了來自上層節點外，自身也會傳來“過時”的節點信息，即這個節點在上個超級步中也是處于激活狀態，它的信息往下一層傳遞后，它自身要消去激活狀態，所以，在迭代器中，也會保存它自身“過時”的信息；

構建數據結構來對圖數據進行存儲，使用Vertex來存儲頂點信息，屬性包括ID和點屬性，這其中，用戶自定義點屬性包含的信息，同時，使用Edge來存儲邊信息，屬性包括三個部分，源頂點的ID，目標頂點的ID，邊屬性，同樣邊屬性的內容可由用戶進行設計,在算法的實現過程中，Edge的邊屬性只需要保存點的連通方向，所以在邊屬性中保存了點之間的距離，用Int sourceId,Int destinationId,Int distance表示， sourecId表示為源頂點的ID，destinationId為目標頂點的ID，而distance則表示2個頂點之間的距離，具體表示從源頂點指向目標頂點，且距離為distance值，而Vertex中所需要保存的信息會相對較多，主要將各個頂點的路由，標志位，超級步這三類信息保存在點屬性中，具體的數據結構使用IntVertexId,String route,Int round,Int flag，VertexId表示頂點的id信息，route表示頂點的當前超級步更新的路由，round表示當前進入第幾個超級步，flag值為標志位，其中，0表示該頂點沒有被激活，1表示該頂點被激活，2表示該頂點曾經被激活過，但現在處于未激活狀態；

BSP模型由以下幾個方面來描述：

a、Processors，指的是集群中的進行并行計算的進程，一個集群中會包含多個Processors計算進程；

b、LocalComputation，指單個Processors的計算，即每個Processors進行的本地計算；

c、Communication，指各個Processors間的通訊，各個并行計算的進程通過信息交互來實現同步；

d、Superstep，叫做超級步，指BSP的一次計算迭代，一個算法由許多的超級步構成，一個超級步相當于一個集群一次總體的分布式計算；

e、BarrierSynchronization，叫做障礙同步或者柵欄同步，每一次同步就是一個超步的完成以及下一個超步的開始;

f、程序什么時候結束，由程序的主節點Master確定，Master在若干個超步后，發現所有的進程的計算都已經結束且再沒有新的計算任務，即通知所有的Processors結束并退出任務；

Vprog負責在每個超級步的初始階段，對頂點信息進行初始化以及更新，分為2個方面：

a、當第一次運行該算法時，圖信息的初始化；

b、該算法以及運行了若干個超級步后，圖信息的更新；

在進行SendMsg時，源節點一定處于激活狀態，由flag的狀態分類可知，flag分成以下3種情況：

a、situation1對應它的源節點處于激活狀態，而它的目標節點處于非激活狀態，且從未被訪問過，所以取源節點中的route信息，更新目標節點的route信息，源節點的route信息可能保存不只一條路徑，即當源節點的上層節點有多個節點同時指向它時或者它的上層節點內本身就保存了多條路由時，這個路由情況就會繼承下來，它也會保存多條路由，這種情況的產生會在MergeMsg模塊進行解釋，所以每一條路由信息都要更新到目標節點中，在更新完路由信息后，還需將目標節點激活，并在目標節點的round中記錄當前超級步階段，再把源節點轉換為非激活狀態，除此之外，SendMsg模塊會將所有的信息先暫存在迭代器Iterator中，信息的整合將在MergeMsg模塊進行；

b、situation2對應它的源節點處于激活狀態，目標節點處于非激活狀態，但目標節點曾經被訪問過，在這種情況下，除了像situation1一樣需要將路由情況更新到目標節點中外，還需要判斷是否已經形成環路，假如沒有形成環路，則不需要進行處理；假如形成了環路，還要分成3種情況進行分析，第1種就是源節點的route里只保存了一條路徑，假如這條路徑與目標節點形成環路，將環路輸出，且不需要再對目標節點進行激活；第2種情況就是源節點的route里保存了多條路徑，且至少有一條路徑與目標節點形成環，但沒有全部路徑都形成環路，那么將形成環路的節點輸出，在更新目標節點的route時，去掉以及形成環路的路徑，保存還沒有形成環路的路徑，再更新目標節點的round值并激活目標節點；第3種情況與第1中情況類似，源節點的route里保存了多條路徑，但每條路徑都與目標節點構成了環路，那么也將形成環路的路徑輸出，也不必對目標節點進行激活，最后，再將源節點的激活狀態轉化成非激活狀態，這些輸出會都先暫存在迭代器Iterator中；

c、situation3，的路由情況為源節點處于激活狀態，而其目標節點也處于激活狀態，目標節點是否處于激活狀態對SendMsg并不會造成影響，它提供的有用的信息就是它的目標節點曾經被訪問過，也就是situation2這種情況，SendMsg更新的信息是先暫存在迭代器Iterator中，直到MergeMsg模塊，再將這個超級步中所有的運行結果更新；

對于第一種情況，需要考慮的節點的前驅，即上層有多個的情況，也就是這個原因，造成了上文SendMsg模塊中situation1的節點的route中保存了多條路徑，需要將他們所有的route信息都要結合到一起形成newMsg，同時，使用“；”來進行分隔多條路徑，對于第二種情況，使用到點屬性中的round屬性值，也就是通過round值來區分是第一類情況還是第二類情況；round值記錄了該頂點被激活時的超級步的階段，假如取出2個迭代器中的round相同，則表明這是第一種情況，而假如取出2個迭代器中的round有大小只差，則表明round值較小的是“過時”的，即可去掉，保存round值較大的值即可。