基于逆波蘭記號電信計費話單過濾算法設(shè)計

　摘 要： 運用逆波蘭記號和堆棧技術(shù)，基于ANSIC/C++開發(fā)環(huán)境，設(shè)計了計費預(yù)處理的話單過濾系統(tǒng)，給出了過濾表達(dá)式的形式定義、物理存儲形式和語義定義以及表達(dá)式形式定義和物理存儲的轉(zhuǎn)換算法。

　　網(wǎng)計費賬系統(tǒng)是電信重要系統(tǒng)之一，系統(tǒng)設(shè)計運行準(zhǔn)確性和操作簡單方便至極關(guān)心運營商的利益，為計費準(zhǔn)確性在設(shè)計系統(tǒng)是必須要多加幾個環(huán)節(jié)來保障系統(tǒng)安全無誤。

　　計費的原始數(shù)據(jù)要經(jīng)歷話單采集、分撿、預(yù)處理、劃價、入庫、合賬等系列過程，最終形成客戶繳費賬單。其中，預(yù)處理環(huán)節(jié)是對話單準(zhǔn)確性進(jìn)行校驗最重要的步驟。該環(huán)節(jié)的主要功能是對各種錯誤識別并進(jìn)行異常處理，同時生成標(biāo)準(zhǔn)化帳單數(shù)據(jù)作為計費的依據(jù)。因此設(shè)計一個高效、靈活的話單過濾算法是計費預(yù)處理系統(tǒng)的一項重要工作。

　　1 功能需求分析

　　算法的實現(xiàn)必須要考慮到特定業(yè)務(wù)需求的邏輯性和相關(guān)性。電信計費話單過濾的功能需求有以下幾個方面：（1）可以分別根據(jù)通話記錄各信息要素以及其組合實現(xiàn)過濾。如主叫和被叫電話以及主被叫電話組合的號碼段，通話開始、結(jié)束時間及通話時長，出中繼和入中繼號碼等；（2）可以根據(jù)通話記錄信息要素的業(yè)務(wù)邏輯和相關(guān)性實現(xiàn)過濾。（3）可以通過圖形界面向?qū)渲迷拞芜^濾條件。

　　2 現(xiàn)行方法的弊端

　　目前，話單過濾功能的實現(xiàn)主要采用以下幾種方式：

　?。?）將話單文件導(dǎo)入數(shù)據(jù)庫系統(tǒng)中進(jìn)行手工SQL命令過濾。該方法人工干預(yù)較多，難以避免人為錯誤。該方法難以應(yīng)用。（2）根據(jù)需要手工修改應(yīng)用程序。該方法直接在程序中修改過濾判斷條件，程序工作量大、改動頻繁，而且不能表述話單的業(yè)務(wù)邏輯關(guān)系。（3）根據(jù)簡單表格形成過濾條件。該方法避免了手工出錯的可能性，但表格中表達(dá)式之間僅存在簡單的“與”“或”的關(guān)系，條件優(yōu)先級無法實現(xiàn)，因而也不能完全表述復(fù)雜的邏輯關(guān)系。

　　3 基于逆波蘭記號的過濾算法設(shè)計

　　3.1 過濾條件的形式定義

　　過濾條件是一個記號系統(tǒng)，其定義應(yīng)當(dāng)符合程序設(shè)計語言的需要，包括一組完整的文法規(guī)則?，F(xiàn)將話單過濾條件定義為文法G={Vn，Vt，P，S}，Vn為非終結(jié)符號集；Vt為終結(jié)符號集；P為產(chǎn)生式（規(guī)則）集；S為識別符號或開始符號。

　　過濾算法成為非線性規(guī)劃領(lǐng)域研究的熱點。過濾算法的特點是不需要罰因子和效益函數(shù)，它利用一種稱之為“濾子”的集合來協(xié)調(diào)可行性和最優(yōu)性，從而保證全局收斂性。過濾算法是一種迭代算法。該算法將非線性優(yōu)化問題轉(zhuǎn)化為一個雙目標(biāo)優(yōu)化問題，即分別最小化可行性違法度和目標(biāo)函數(shù)值。其中又偏重于改善可行性。在每一個迭代點都通過某種方法（信賴域，SQP等）獲得一個嘗試步，若該嘗試步至少能改善可行性和最優(yōu)性兩者之一，則判定該嘗試步能被濾子接受，接下來再考察其充分下降性。

　　3.2 過濾條件的物理存儲表示

　　物理存儲器是指實際存在的具體的存儲器芯片。如主板上裝插的內(nèi)存條和裝載有系統(tǒng)BIOS的ROM芯片，顯示卡上的顯示RAM芯片和裝載顯示BIOS的ROM芯片，以及各種適配卡上的RAM芯片和ROM芯片等都是物理存儲器。

　　話單過濾條件形式定義為一個中綴邏輯表達(dá)式，這種方式對最終用戶來說是個易于理解和符合閱讀或操作習(xí)慣的表達(dá)方式，但在算法處理中需要進(jìn)行算符優(yōu)先級的判定工作。逆波蘭記號又叫后綴表示法，這種表示方法將運算對象寫在前面，把運算符寫在后面，只需要利用一個堆棧就可完全對輸入串進(jìn)行解析。3.1節(jié)中的示例表達(dá)式用逆波蘭記號可表示為：A，字串，>，E，字串，≤，∩，M，字串，=，∪。通過采用逆波蘭記號，合理規(guī)避了算符優(yōu)先級別的判別功能，有利于程序設(shè)計的簡化。