基于逆波蘭記號(hào)電信計(jì)費(fèi)話單過(guò)濾算法設(shè)計(jì)

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

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

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

　　1  功能需求分析

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

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

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

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

　　3  基于逆波蘭記號(hào)的過(guò)濾算法設(shè)計(jì)

　　3.1 過(guò)濾條件的形式定義

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

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

　　3.2 過(guò)濾條件的物理存儲(chǔ)表示

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

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

　　3.3 過(guò)濾條件語(yǔ)義的定義

　　語(yǔ)義定義是和功能需求緊密聯(lián)系的，并可以根據(jù)需求的變化進(jìn)行調(diào)整和擴(kuò)充。文法G中各終結(jié)符號(hào)語(yǔ)義見(jiàn)表1。

　　例如話單過(guò)濾表達(dá)式（（（A>4224000）∩（A≤6899123））∪（N=1）），其語(yǔ)義為主叫號(hào)碼段在4224000和6899123之間，或者主被叫歸屬相同計(jì)費(fèi)區(qū)。

　　3.4 過(guò)濾條件形式定義和物理存儲(chǔ)的相互轉(zhuǎn)換

　　話單過(guò)濾條件的形式定義和物理表述分別采用中綴法和后綴法，前者直接面向最終用戶，后者是針對(duì)設(shè)計(jì)人員算法實(shí)現(xiàn)的需要，因此必須采用合理的機(jī)制進(jìn)行相互轉(zhuǎn)換。這里需要解決兩個(gè)問(wèn)題：一是要設(shè)計(jì)一個(gè)最終用戶可理解的圖形界面向?qū)А⒉捎弥芯Y法來(lái)配置過(guò)濾表達(dá)式；二是設(shè)計(jì)一個(gè)依據(jù)中綴式形成后綴式的算法。在本文中作如下定義：

　　3.4.1 過(guò)濾表達(dá)式的用戶配置

　　這里預(yù)定義關(guān)系表T_EXPRESS，其結(jié)構(gòu)見(jiàn)表2。該表用于存儲(chǔ)所有話單過(guò)濾條件的原子表達(dá)式和組合表達(dá)式?；谠摫?，設(shè)計(jì)相關(guān)的圖形配置界面向?qū)呛苋菀走_(dá)到用戶配置過(guò)濾表達(dá)式要求的。

　　3.3節(jié)中話單過(guò)濾表達(dá)式在表中存儲(chǔ)方式見(jiàn)表3，記錄序號(hào)5指示的組合表達(dá)式就是該過(guò)濾條件表達(dá)式的入口。

　　3.4.2 中綴式向后綴式轉(zhuǎn)換算法

　　實(shí)現(xiàn)中綴表達(dá)式向后綴表達(dá)式的轉(zhuǎn)換可采用遞歸算法，偽C語(yǔ)言代碼如下：

　　String GetSuffixExpress（int seq） {

　　Billing_Record_Express=GetBillingRecordExpress（seq）；

　　If Billing_Record_Express.ftype=原子表達(dá)式

　　Return Billing_Record_Express.felement + ″，″+

　　Billing_Record_Express.fvalue +″，″+ Billing_Record_Express.foperate；

　　Else //組合表達(dá)式

　　Return  GetSuffixExpress（int（Billing_Record_

　　Express.felement）） + ″，″+ GetSuffixExpress（int

　?。˙illing_Record_Express.fvalue）） + ″，″+

　　Billing_Record_Express.foperate；

　　}[!--empirenews.page--]

　　3.5 話單過(guò)濾表達(dá)式運(yùn)算算法的實(shí)現(xiàn)

　　話單過(guò)濾表達(dá)式最終將形成布爾值結(jié)果真或假，由此來(lái)判定該張?jiān)拞问欠癖幌到y(tǒng)過(guò)濾。算法分為語(yǔ)法分析、業(yè)務(wù)邏輯處理兩個(gè)部分。語(yǔ)法分析是利用堆棧運(yùn)算分解出原子表達(dá)式的過(guò)程；業(yè)務(wù)邏輯處理是針對(duì)原子表達(dá)式的語(yǔ)義作出相應(yīng)的業(yè)務(wù)處理并求得該原子表達(dá)式的布爾值。以下是算法的偽C語(yǔ)言代碼：

　　STACK stack；

　　Bool result；

　　String suffixexpress；

　　Bool SyntaxAnlysis（suffixexpress）{

　　SETNULL（stack）；

　　Terminalsymb=GetNextTerminalsymb（suffixexpress）；

　　While （！IsNull（Terminalsymb）） {

　　Switch（Terminalsymb）{

　　Case A to N     PUSH（stack，Terminalsymbol）；

　　Case > to =

　　POP（stack，value）；

　　POP（stack，factor_code）；

　　Comparesymb=Terminalsymb；

　　Result=LogicProcess（factor_code,Com

　　paresymbol，value）；

　　PUSH（stack，result）

　　Case  ∪，∩

　　POP（stack，result1）；

　　POP（stack，result2）；

　　Logicalsymb=Terminalsymb；

　　Result=BoolProcess（result1，Logicalsymbol，result2）；

　　PUSH（stack，result）；

　　}

　　Terminalsymbol=GetNextTerminalsymbol（suffixexpress）；

　　}

　　return TOP（stack）；

　　}

　　在設(shè)計(jì)和開(kāi)發(fā)湖南電信本地網(wǎng)計(jì)費(fèi)系統(tǒng)過(guò)程中，運(yùn)用逆波蘭記號(hào)和堆棧技術(shù)，基于ANSI C/C++開(kāi)發(fā)環(huán)境成功完成了計(jì)費(fèi)預(yù)處理的話單過(guò)濾系統(tǒng)。本算法稍加修改和擴(kuò)充就可以應(yīng)用到大部分涉及格式化文本和數(shù)據(jù)庫(kù)記錄過(guò)濾的應(yīng)用中。