[發(fā)明專利]基于有序小枝模式的航空物流XML報文并行過濾方法

有效

• 申請?zhí)枺?/td>: 201910249408.5
• 申請日: 2019-03-29
• 公開（公告）號: CN109977270B
• 公開（公告）日: 2023-07-18
• 發(fā)明（設計）人: 李國;莊波;李永華
• 申請（專利權）人: 中國民航大學
• 主分類號: G06F16/835
• 分類號: G06F16/835;G06F9/50
• 代理公司: 天津市鼎和專利商標代理有限公司 12101
• 代理人: 蒙建軍

1.一種基于有序小枝模式的航空物流XML報文并行過濾方法，其特征在于，包括：

步驟一：?使用XPath路徑表達式來選取?XML?文檔中的節(jié)點或者節(jié)點集；帶謂詞的XPath路徑表達式被表示成樹的形式，將討論都集中在XPath路徑表達式的子集上，定位步驟集合為：{/a,//a,/*,//*,[]},謂詞用于討論等值謂詞；

步驟二：XML文檔與小枝模式查詢進行標簽序列化得到標簽序列，為了將小枝模式查詢中節(jié)點之間的信息包含在標簽序列中，F(xiàn)iST算法對標簽序列進行屬性擴充；擴充后的序列為查詢序列，包含小枝模式中的所有信息；

步驟三：并行過濾方法的體系結構中，系統(tǒng)在處理XML數(shù)據(jù)流之前，XPath訂閱表達式首先被傳遞到系統(tǒng)中，然后將XPath路徑表達式通過XPath解析器解析成Prüfer?序列，任務組調度算法將根據(jù)Prüfer?序列計算每個查詢序列的任務耗時，并根據(jù)任務耗時將所有任務平均分配到各個線程上，使每個線程的任務達到負載平衡，并且為每個線程分配一個CPU核心；FiST算法在各CPU核心上執(zhí)行查詢處理，將匹配結果直接分發(fā)給訂閱者；

步驟四：任務組調度算法中FiST算法通過判斷LPS(Q)是否為LPS(T)的子序列，來驗證查詢樹Q與XML文檔樹TR的匹配；如果標簽序列(LPS(Q))越長，匹配的時間將會越久；假設LPS(Q)={Q1?Q2…Qn},則T(LPS(Q))=n；其中T表示任務耗時，單位為一個時間單元，LPS(Q)代表一個任務；當LPS(Q1)={Na?Co?成都?Ci?Co?Com?Co?St?Co}的T(LPS(Q1))=11時，LPS(Q1)的任務耗時為11個時間單元；將每個小枝模式序列化為查詢序列并根據(jù)序列的長度計算任務耗時；對于m個獨立任務，按任務耗時均勻的分配到m個CPU上；用下列公式表示：

；

通過求s的值來比較任務分組的均勻程度，s越小，分組越均勻；其中為第i組的總耗時，為平均耗時，的計算公式如下；

；

將任務按耗時降序排列放入數(shù)組A中，數(shù)組A=[T₁,T₂,T₃……T_m……T_k-1,T_k……，T_n-1,T_n]，其中T₁≧T₂≧T_3?……T_m……≧T_k-1≧T_k……T_n-1≧T_n；第一方向定義為從數(shù)組下標0開始，從左至右；第二方向定義為從數(shù)組下標n開始，從右至左；第三方向定義為從數(shù)組下標k開始，從左至右；

第一步：按第一方向依次從數(shù)組A取任務放入第一個線程，直到滿足以下不等式關系：

如果等于，則直接將任務T放入第一個線程中；

第二步:計算和；比較T_k與Value的大小，如果Tk等于Value，則直接將T_k放入第一個線程中，否則按第二方向表示的范圍，在Tm與Tn?之間用二分查詢出最接近Value的數(shù)將其放入第一個線程中；

第三步：按第三方向依次從數(shù)組A取任務，放入第二個線程，重復第一步操作，直到所有任務都放入線程中為止，其中l(wèi)eft初始值為1，right初始值為n。