基于逆波兰记号电信计费话单过滤算法设计

　摘  要： 运用逆波兰记号和堆栈技术，基于ANSIC/C++开发环境，设计了计费预处理的话单过滤系统，给出了过滤表达式的形式定义、物理存储形式和语义定义以及表达式形式定义和物理存储的转换算法。

　　网计费账系统是电信重要系统之一，系统设计运行准确性和操作简单方便至极关心运营商的利益，为计费准确性在设计系统是必须要多加几个环节来保障系统安全无误。

　　计费的原始数据要经历话单采集、分捡、预处理、划价、入库、合账等系列过程，最终形成客户缴费账单。其中，预处理环节是对话单准确性进行校验最重要的步骤。该环节的主要功能是对各种错误识别并进行异常处理，同时生成标准化帐单数据作为计费的依据。因此设计一个高效、灵活的话单过滤算法是计费预处理系统的一项重要工作。

　　1  功能需求分析

　　算法的实现必须要考虑到特定业务需求的逻辑性和相关性。电信计费话单过滤的功能需求有以下几个方面：（1）可以分别根据通话记录各信息要素以及其组合实现过滤。如主叫和被叫电话以及主被叫电话组合的号码段，通话开始、结束时间及通话时长，出中继和入中继号码等；（2）可以根据通话记录信息要素的业务逻辑和相关性实现过滤。（3）可以通过图形界面向导配置话单过滤条件。

　　2  现行方法的弊端

　　目前，话单过滤功能的实现主要采用以下几种方式：

　　（1）将话单文件导入数据库系统中进行手工SQL命令过滤。该方法人工干预较多，难以避免人为错误。该方法难以应用。（2）根据需要手工修改应用程序。该方法直接在程序中修改过滤判断条件，程序工作量大、改动频繁，而且不能表述话单的业务逻辑关系。（3）根据简单表格形成过滤条件。该方法避免了手工出错的可能性，但表格中表达式之间仅存在简单的“与”“或”的关系，条件优先级无法实现，因而也不能完全表述复杂的逻辑关系。

　　3  基于逆波兰记号的过滤算法设计

　　3.1 过滤条件的形式定义

　　过滤条件是一个记号系统，其定义应当符合程序设计语言的需要，包括一组完整的文法规则。现将话单过滤条件定义为文法G={Vn，Vt，P，S}，Vn为非终结符号集；Vt为终结符号集；P为产生式（规则）集；S为识别符号或开始符号。

　　过滤算法成为非线性规划领域研究的热点。过滤算法的特点是不需要罚因子和效益函数，它利用一种称之为“滤子”的集合来协调可行性和最优性，从而保证全局收敛性。过滤算法是一种迭代算法。该算法将非线性优化问题转化为一个双目标优化问题，即分别最小化可行性违法度和目标函数值。其中又偏重于改善可行性。在每一个迭代点都通过某种方法（信赖域，SQP等）获得一个尝试步，若该尝试步至少能改善可行性和最优性两者之一，则判定该尝试步能被滤子接受，接下来再考察其充分下降性。

　　3.2 过滤条件的物理存储表示

　　物理存储器是指实际存在的具体的存储器芯片。如主板上装插的内存条和装载有系统BIOS的ROM芯片，显示卡上的显示RAM芯片和装载显示BIOS的ROM芯片，以及各种适配卡上的RAM芯片和ROM芯片等都是物理存储器。

　　话单过滤条件形式定义为一个中缀逻辑表达式，这种方式对最终用户来说是个易于理解和符合阅读或操作习惯的表达方式，但在算法处理中需要进行算符优先级的判定工作。逆波兰记号又叫后缀表示法，这种表示方法将运算对象写在前面，把运算符写在后面，只需要利用一个堆栈就可完全对输入串进行解析。3.1节中的示例表达式用逆波兰记号可表示为：A，字串，>，E，字串，≤，∩，M，字串，=，∪。通过采用逆波兰记号，合理规避了算符优先级别的判别功能，有利于程序设计的简化。[!--empirenews.page--]

　　3.3 过滤条件语义的定义

　　语义定义是和功能需求紧密联系的，并可以根据需求的变化进行调整和扩充。文法G中各终结符号语义见表1。

　　例如话单过滤表达式（（（A>4224000）∩（A≤6899123））∪（N=1）），其语义为主叫号码段在4224000和6899123之间，或者主被叫归属相同计费区。

　　3.4 过滤条件形式定义和物理存储的相互转换

　　话单过滤条件的形式定义和物理表述分别采用中缀法和后缀法，前者直接面向最终用户，后者是针对设计人员算法实现的需要，因此必须采用合理的机制进行相互转换。这里需要解决两个问题：一是要设计一个最终用户可理解的图形界面向导、采用中缀法来配置过滤表达式；二是设计一个依据中缀式形成后缀式的算法。在本文中作如下定义：

　　3.4.1 过滤表达式的用户配置

　　这里预定义关系表T_EXPRESS，其结构见表2。该表用于存储所有话单过滤条件的原子表达式和组合表达式。基于该表，设计相关的图形配置界面向导是很容易达到用户配置过滤表达式要求的。

　　3.3节中话单过滤表达式在表中存储方式见表3，记录序号5指示的组合表达式就是该过滤条件表达式的入口。

　　3.4.2 中缀式向后缀式转换算法

　　实现中缀表达式向后缀表达式的转换可采用递归算法，伪C语言代码如下：

　　String GetSuffixExpress（int seq） {

　　Billing_Record_Express=GetBillingRecordExpress（seq）；

　　If Billing_Record_Express.ftype=原子表达式

　　Return Billing_Record_Express.felement + ″，″+

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

　　Else //组合表达式

　　Return  GetSuffixExpress（int（Billing_Record_

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

　　（Billing_Record_Express.fvalue）） + ″，″+

　　Billing_Record_Express.foperate；

　　}[!--empirenews.page--]

　　3.5 话单过滤表达式运算算法的实现

　　话单过滤表达式最终将形成布尔值结果真或假，由此来判定该张话单是否被系统过滤。算法分为语法分析、业务逻辑处理两个部分。语法分析是利用堆栈运算分解出原子表达式的过程；业务逻辑处理是针对原子表达式的语义作出相应的业务处理并求得该原子表达式的布尔值。以下是算法的伪C语言代码：

　　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）；

　　}

　　在设计和开发湖南电信本地网计费系统过程中，运用逆波兰记号和堆栈技术，基于ANSI C/C++开发环境成功完成了计费预处理的话单过滤系统。本算法稍加修改和扩充就可以应用到大部分涉及格式化文本和数据库记录过滤的应用中。