摘要：該文首先對(duì)撥號(hào)數(shù)圖匹配的規(guī)則語(yǔ)法進(jìn)行了分類講解，通過對(duì)規(guī)則語(yǔ)法的分析，給出了數(shù)圖匹配的算法分析，并以偽代碼的形式進(jìn)行了算法實(shí)現(xiàn)。整個(gè)算法過程包含規(guī)則預(yù)處理和撥號(hào)匹配兩個(gè)過程，該文對(duì)算法實(shí)現(xiàn)的流程圖進(jìn)行了詳細(xì)的描述。

關(guān)鍵詞：VoIP；數(shù)圖（digitmap）；超越匹配（over matched）

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）04-0807-04

Research & Efficient Implementation of Digitmap Matching Algorithm

WANG Xiao-lan

（Electromechanical Department， Suzhou Institute of Trade&Commerce， Suzhou 215009， China）

Abstract： The digitmap matching rules was classified and discussed in this paper. By analyzing the rules， the digitmap matching algorithm is illustrated and implemented in the form of pseudo-code. The whole process of algorithm holds two phases： rules preprocessing and digit matching. Further more， this paper described in details the flow chart of implementation of the algorithm.

Key words： VoIP； digitmap； over matched

網(wǎng)絡(luò)技術(shù)與多媒體技術(shù)的發(fā)展，促進(jìn)了通信技術(shù)的綜合化、數(shù)字化、智能化的發(fā)展，使得在單一網(wǎng)絡(luò)平臺(tái)上實(shí)現(xiàn)語(yǔ)音、數(shù)據(jù)、圖像等多種業(yè)務(wù)成為可能，其中IP語(yǔ)音技術(shù)（VoIP）已經(jīng)被廣泛應(yīng)用于通信領(lǐng)域，IP話機(jī)、VoIP網(wǎng)關(guān)、PBX設(shè)備等，也逐步地得到商業(yè)化[1]。

在傳統(tǒng)的公共交換電話網(wǎng)PSTN中，電話撥號(hào)是通過電流傳到局端設(shè)備進(jìn)行匹配的，VOIP網(wǎng)關(guān)則同時(shí)充當(dāng)了IP網(wǎng)絡(luò)的終端設(shè)備和普通話機(jī)的局端設(shè)備。如圖1所示，VOIP網(wǎng)關(guān)1接收電話機(jī)1的撥號(hào)，收集號(hào)碼，并于配置的數(shù)圖（digitmap）規(guī)則進(jìn)行匹配，匹配成功后，就會(huì)通過VOIP語(yǔ)音信令的方式上報(bào)呼叫請(qǐng)求，服務(wù)器通過對(duì)號(hào)碼的分析，將呼叫請(qǐng)求轉(zhuǎn)到被叫網(wǎng)關(guān)2，電話機(jī)2振鈴，用戶2摘機(jī)，IP電話接通。所以VOIP網(wǎng)關(guān)需要實(shí)現(xiàn)號(hào)碼收集過程中的數(shù)圖匹配算法，該文首先對(duì)數(shù)圖規(guī)則進(jìn)行了描述，基于該數(shù)圖規(guī)則，對(duì)數(shù)圖匹配算法的兩個(gè)過程進(jìn)行了理論分析，并給出了實(shí)現(xiàn)的思路。算法的實(shí)現(xiàn)過程包括對(duì)數(shù)圖規(guī)則的預(yù)處理過程和號(hào)碼收集的匹配過程。

1 數(shù)圖規(guī)則

數(shù)圖的設(shè)置需要遵循規(guī)則，如表1所示[2]。

表1 數(shù)圖規(guī)則語(yǔ)法描述

[規(guī)則＼&說明＼&舉例＼&舉例說明＼&數(shù)字（Digit）＼&一個(gè)從0到9的數(shù)字＼&95538＼&只有收集到95538才能成功匹配＼&雙音頻（DTMF）＼&一個(gè)數(shù)字、計(jì)時(shí)器或符號(hào)A，B，C，D，#或*＼&*95538A#＼&只有收集到*95538A#才能成功匹配＼&通配符（Wildcard）＼&符號(hào)x可以匹配任何數(shù)字（0到9）＼&12xxxx＼&可以匹配12開頭的6位號(hào)碼，如123987或124568等＼&序列（Range）＼&一個(gè)或幾個(gè)DTMF符號(hào)包含在方括號(hào)[ ]中，取其中一個(gè)＼&12[389]＼&可以匹配123，128或129＼&區(qū)域（Subrange）＼&兩個(gè)數(shù)字被連字符 "-" 隔開，表示可以取自該范圍內(nèi)的一個(gè)數(shù)字＼&12[3-5]＼&“-”需要跟”[ ]”結(jié)合使用，可以匹配123，124或125＼&點(diǎn)（Dot）＼&“ . ”表示前面的數(shù)字等可以出現(xiàn)任意次數(shù)，包括“0”次＼&123.＼&可以匹配12，123，1234，12335等＼&計(jì)時(shí)器（Timer）＼&符號(hào)T 匹配一個(gè)計(jì)時(shí)器的時(shí)長(zhǎng)＼&123T＼&匹配到123后，會(huì)啟動(dòng)T定時(shí)器＼&分隔符（Seperator）＼&“|”，用于分隔多個(gè)數(shù)圖規(guī)則＼&123|95538

|021xxxxx#＼&數(shù)圖組包含123，95538和021xxxxx#三個(gè)數(shù)圖規(guī)則＼&]

2 數(shù)圖規(guī)則的預(yù)處理

在收集號(hào)碼，進(jìn)行數(shù)圖匹配之前，首先需要對(duì)設(shè)置的數(shù)圖組進(jìn)行預(yù)處理，從而能夠在匹配時(shí)高效執(zhí)行。以下通過偽代碼結(jié)合流程圖的方式描述處理的過程。

定義需要的結(jié)構(gòu)參數(shù)：

struct DMAP_RULE

{

struct DMAP_SUBRULE

{

UINT32 token；

BOOL required；

BOOL timer；

}subrules[MAX_SUBRULES]；

int subrules_num；

BOOL valid；

BOOL timer；

}rules[MAX_RULES]；

DMAP_RULE指單個(gè)規(guī)則，一個(gè)數(shù)圖組可以配置多個(gè)規(guī)則，每個(gè)規(guī)則包含多個(gè)子規(guī)則DMAP_SUBRULE以及子規(guī)則數(shù)量、是否有效和是否開啟定時(shí)器三個(gè)屬性。子規(guī)則DMAP_SUBRULE是對(duì)單個(gè)規(guī)則串進(jìn)行分析后建立的，是關(guān)鍵所在，每個(gè)子規(guī)則包含以32位bit標(biāo)示的標(biāo)記，以及是否必須（subrules.required）和是否有定時(shí)器（subrules.timer）兩個(gè)屬性。

圖2描述的就是對(duì)一個(gè)數(shù)圖規(guī)則組進(jìn)行預(yù)處理的流程，預(yù)處理的目的就是將數(shù)圖規(guī)則組轉(zhuǎn)換為rules結(jié)構(gòu)，用于數(shù)圖匹配。以下對(duì)該預(yù)處理流程進(jìn)行分步解析。

1）每個(gè)數(shù)圖規(guī)則由‘|’分隔，對(duì)每個(gè)數(shù)圖規(guī)則進(jìn)行遍歷；

2）對(duì)當(dāng)前數(shù)圖規(guī)則中字符串（子規(guī)則）進(jìn)行遍歷；

3）當(dāng)前子規(guī)則如果為“+#*0123456789ABCD”中某個(gè)字符，則設(shè)置rules[i].subrules[j].token對(duì)應(yīng)bit為1，設(shè)置rules[i].subrules[j].required為1，設(shè)置rules[i].subrules[j].timer為0，跳到（2）繼續(xù)匹配下一子規(guī)則；否則進(jìn)入步驟（4）；

4）當(dāng)前子規(guī)則如果為‘X’，則設(shè)置rules[i].subrules[j].token為0x3FF，即0-9bit為1，說明可以匹配0-9內(nèi)的數(shù)字，設(shè)置rules[i].subrules[j].required為1，設(shè)置rules[i].subrules[j].timer為0，跳到（2）繼續(xù)匹配下一子規(guī)則；否則進(jìn)入步驟（5）；

5）當(dāng)前子規(guī)則如果為‘[’，則查找是否有‘]’對(duì)應(yīng)，沒有則說規(guī)則錯(cuò)誤，直接退出；否則進(jìn)入步驟（6）；如果不是‘[’，則跳到步驟（10）；

6）遍歷“[]”內(nèi)每個(gè)字符（注意，“[]”內(nèi)屬于一個(gè)子規(guī)則），遍歷結(jié)束則跳到（2）繼續(xù)匹配；

7）“[]”內(nèi)當(dāng)前字符如果為‘T’，則設(shè)置rules[i].subrules[j-1].timer為1（注意‘T’的屬性會(huì)加在前一規(guī)則上），rules[i].timer為1，跳到（6）；

8）“[]”內(nèi)當(dāng)前字符如果為‘-’，則設(shè)置rules[i].subrules[j].token在‘-’區(qū)間內(nèi)的bit為1，比如[3-5]Vjafp6p7Hwx2WVJ4a5PM8g==，則設(shè)置bit3、4、5為1，設(shè)置rules[i].subrules[j].required為1，設(shè)置rules[i].subrules[j].timer為0，跳到（6）繼續(xù)遍歷；否則進(jìn)入步驟（9）；

9）其他情況則設(shè)置相應(yīng)bit為1，設(shè)置rules[i].subrules[j].required為1，設(shè)置rules[i].subrules[j].timer為0，跳到（6）繼續(xù)遍歷；

10）當(dāng)前子規(guī)則如果為‘T’，則設(shè)置rules[i].subrules[j-1].timer為1（注意‘T’的屬性會(huì)加在前一規(guī)則上），rules[i].timer為1，該規(guī)則處理結(jié)束，跳到（1）處理下一規(guī)則；否則跳到（11）；

11）當(dāng)前子規(guī)則如果為‘.’，則是上一子規(guī)則的0次或多次的重復(fù)，則將rules[i].subrules[j].required設(shè)置為0，跳到（2）；

3 數(shù)圖匹配

在收集號(hào)碼時(shí)，預(yù)處理生成的rules就被用于對(duì)所撥的號(hào)碼串進(jìn)行匹配，匹配的總體過程是對(duì)每個(gè)有效的數(shù)圖規(guī)則進(jìn)行匹配，rules[i].valid初始為1，匹配不成功則置rules[i].valid為0，說明該規(guī)則失效，下次撥號(hào)就不參加匹配。圖3描述的是撥號(hào)數(shù)圖匹配的流程圖，具體步驟如圖3。

1）每收到一個(gè)撥號(hào)數(shù)字，則串在digits尾部；

2）遍歷rules中的每個(gè)規(guī)則，檢查rules[i].valid如果為1（該規(guī)則有效），則跳到（3），否則跳回步驟（1），匹配下一規(guī)則；

3）同時(shí)遍歷digits和rules[i].subrules，遍歷結(jié)束，如果當(dāng)前digits長(zhǎng)度已超出當(dāng)前規(guī)則的子規(guī)則數(shù)，則為超越匹配，這種情況下該規(guī)則將置為無(wú)效；否則該規(guī)則有效，并跳回（1）；

4）檢查rules[i].subrules[j].token相應(yīng)bit位如果為1，則說明匹配上，跳到（5）；否則該規(guī)則無(wú)效，并跳回（1）；

5）檢查rules[i].subrules[j].required如果為0，則說明該規(guī)則后面跟的是‘.’，可以匹配0個(gè)或多個(gè)當(dāng)前子規(guī)則，所以跳到（3），繼續(xù)用下一個(gè)digits[k]匹配當(dāng)前規(guī)則；否則跳到（6）；

6）檢查rules[i].subrules[j].timer如果為1，則設(shè)置該規(guī)則有效，并開啟定時(shí)器，跳回（1）；否則跳回（3）繼續(xù)匹配子規(guī)則，直到匹配結(jié)束。

4 結(jié)束語(yǔ)

本文基于數(shù)圖規(guī)則的語(yǔ)法，對(duì)數(shù)圖匹配算法進(jìn)行了研究，并采用偽代碼結(jié)合流程圖的形式給出了實(shí)現(xiàn)原理，整個(gè)過程包含規(guī)則預(yù)處理和撥號(hào)時(shí)匹配兩個(gè)過程。該匹配算法可用于帶voip的網(wǎng)關(guān)、IPPBX和IPTV機(jī)頂盒等設(shè)備上，具有很好的實(shí)用價(jià)值。

參考文獻(xiàn)：

[1]卜巍.VoIP的原理、標(biāo)準(zhǔn)和技術(shù)淺析[J].計(jì)算機(jī)與網(wǎng)絡(luò)，2004（12）.

[2] 百度文庫(kù)[EB/OL].http：//wenku.baidu.com/view/7981cc492e3f5727a5e962b8.html.