[發(fā)明專利]一種基于樹型結(jié)構(gòu)的號(hào)碼段匹配算法及其實(shí)現(xiàn)

無效

• 申請(qǐng)?zhí)枺?/td>: 201110282521.7
• 申請(qǐng)日: 2011-09-20
• 公開（公告）號(hào): CN103020060A
• 公開（公告）日: 2013-04-03
• 發(fā)明（設(shè)計(jì)）人: 寧學(xué)軍;蘇煥杰;黃興斌
• 申請(qǐng)（專利權(quán)）人: 佳都新太科技股份有限公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及通訊領(lǐng)域、電信業(yè)務(wù)領(lǐng)域，特別是涉及一種基于樹型結(jié)構(gòu)的號(hào)碼段匹配算法及其實(shí)現(xiàn)。

背景技術(shù)

隨著電信通訊技術(shù)的迅猛發(fā)展，國內(nèi)各大運(yùn)營(yíng)商經(jīng)過激烈的競(jìng)爭(zhēng)，發(fā)展為目前中國電信、中國聯(lián)通、中國移動(dòng)三大電信運(yùn)營(yíng)商，隨著3G技術(shù)的發(fā)展、成熟，國內(nèi)三大運(yùn)營(yíng)商都進(jìn)入了全業(yè)務(wù)運(yùn)營(yíng)的時(shí)代。隨著技術(shù)的更新?lián)Q代，業(yè)務(wù)也跟著發(fā)展和壯大，用戶數(shù)量也飛速地增長(zhǎng)。

在電信業(yè)務(wù)領(lǐng)域中，系統(tǒng)經(jīng)常會(huì)涉及到分析用戶號(hào)碼的網(wǎng)絡(luò)屬性、歸屬地以、用戶類型以及所屬群組等信息，從而根據(jù)號(hào)碼的不同屬性進(jìn)行不同的操作，比如進(jìn)行不同價(jià)格的計(jì)費(fèi)、播放不同的提示音、進(jìn)入訂購的特殊業(yè)務(wù)等等。對(duì)于省級(jí)或者全國級(jí)的應(yīng)用，甚至是跨運(yùn)營(yíng)商網(wǎng)絡(luò)的全國級(jí)應(yīng)用，系統(tǒng)可能涉及到三大運(yùn)營(yíng)商所有網(wǎng)絡(luò)類型下的所有用戶號(hào)碼，這些號(hào)碼的屬性中僅歸屬地一項(xiàng)，就是一個(gè)很大的數(shù)據(jù)量，如果采用簡(jiǎn)單地遍歷匹配，將會(huì)非常消耗系統(tǒng)性能。因此需要一種高性能的號(hào)碼段匹配算法，對(duì)于任意的一個(gè)號(hào)碼，可以快速定位到所屬的號(hào)碼段。基于樹型結(jié)構(gòu)的號(hào)碼段匹配算法，將每個(gè)號(hào)碼段轉(zhuǎn)變成樹結(jié)構(gòu)中的一個(gè)路徑，對(duì)于任意的一個(gè)真實(shí)號(hào)碼，通過樹中的路徑匹配便可快速定位到相應(yīng)的號(hào)碼段。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問題是提供一種基于樹型結(jié)構(gòu)的號(hào)碼段匹配算法及其實(shí)現(xiàn)，以加快用戶號(hào)碼屬性的分析速度，從而提高系統(tǒng)的性能。

為實(shí)現(xiàn)上述發(fā)明目的，本發(fā)明提供一種基于樹型結(jié)構(gòu)的號(hào)碼段匹配算法及其實(shí)現(xiàn)，包括樹型結(jié)構(gòu)和號(hào)碼段屬性。所述樹型結(jié)構(gòu)，由樹節(jié)點(diǎn)組成，樹節(jié)點(diǎn)分為支干和樹葉兩種類型，支干中包含一個(gè)指針數(shù)組，指向下一級(jí)的多個(gè)樹節(jié)點(diǎn)；樹葉為一個(gè)路徑的終點(diǎn)，包含了一個(gè)指向號(hào)碼段屬性的指針；所述號(hào)碼段屬性，記錄了該號(hào)碼段的相關(guān)屬性，包括號(hào)碼段、歸屬運(yùn)營(yíng)商、歸屬地、終端類型、擴(kuò)展屬性等；

所述樹型結(jié)構(gòu)，用于：將每一個(gè)號(hào)碼段對(duì)應(yīng)成樹中的一個(gè)路徑，該路徑從樹根節(jié)點(diǎn)開始，以一個(gè)樹葉節(jié)點(diǎn)為終結(jié)。號(hào)碼段中的第1位號(hào)碼對(duì)應(yīng)于樹根節(jié)點(diǎn)(也稱為第1級(jí)節(jié)點(diǎn))中指向下一級(jí)節(jié)點(diǎn)的指針數(shù)組的一個(gè)下標(biāo)，根據(jù)該下標(biāo)對(duì)應(yīng)的指針指向第2級(jí)節(jié)點(diǎn)，號(hào)碼段中的第2位號(hào)碼對(duì)應(yīng)于該第2級(jí)節(jié)點(diǎn)中指向下一級(jí)節(jié)點(diǎn)的指針數(shù)組的一個(gè)下標(biāo)，依次類推，號(hào)碼段中的最后一位號(hào)碼則對(duì)應(yīng)的指針則指向一個(gè)樹葉節(jié)點(diǎn)；

所述號(hào)碼段屬性，用于：記錄了該號(hào)碼段的相關(guān)屬性，包括號(hào)碼段、歸屬運(yùn)營(yíng)商、歸屬地、終端類型、擴(kuò)展屬性等。

本發(fā)明還提供一種基于樹型結(jié)構(gòu)的號(hào)碼段匹配算法及其實(shí)現(xiàn)，包括：

樹節(jié)點(diǎn)中使用一個(gè)無符號(hào)字符變量記錄節(jié)點(diǎn)的類型，0表示支干，1表示樹葉；樹節(jié)點(diǎn)中采用聯(lián)合(union)的方式來保存支干對(duì)應(yīng)的下一級(jí)節(jié)點(diǎn)指針數(shù)組或者樹葉對(duì)應(yīng)的號(hào)碼段屬性指針。

本發(fā)明還提供一種基于樹型結(jié)構(gòu)的號(hào)碼段匹配算法及其實(shí)現(xiàn)，包括：

所述樹干節(jié)點(diǎn)中的指針數(shù)組，其長(zhǎng)度為17，號(hào)碼‘0’-‘9’分別對(duì)應(yīng)數(shù)組下標(biāo)1-10，特殊號(hào)碼‘a(chǎn)’、‘b’、‘c’、‘d’則分別對(duì)應(yīng)數(shù)組下標(biāo)的11、12、13、14，特殊號(hào)碼‘*’、‘+’則分別對(duì)應(yīng)數(shù)組下標(biāo)的15、16。當(dāng)一個(gè)樹干同時(shí)也是一個(gè)樹葉時(shí)，使用指針數(shù)組中下標(biāo)為0的指針，指向一個(gè)樹葉節(jié)點(diǎn)。根據(jù)其它特殊的號(hào)碼需求，數(shù)組長(zhǎng)度可進(jìn)行靈活擴(kuò)展。

優(yōu)選的有，上述方法中，還包括：所述的號(hào)碼段路徑匹配過程中，如果匹配到某一級(jí)節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)非葉節(jié)點(diǎn)并且沒有對(duì)應(yīng)的下一級(jí)節(jié)點(diǎn)，則回退至上一級(jí)節(jié)點(diǎn)，檢查上一級(jí)節(jié)點(diǎn)的指針數(shù)組中下標(biāo)為0的指針是否指向了一個(gè)樹葉節(jié)點(diǎn)，如果是，則匹配路徑成功；如果不是，則繼續(xù)回退上一級(jí)節(jié)點(diǎn)，直到匹配成功或者到達(dá)根節(jié)點(diǎn)，到達(dá)根節(jié)點(diǎn)時(shí)認(rèn)為匹配失敗，沒有對(duì)應(yīng)的號(hào)碼段信息。

本發(fā)明還提供一種基于樹型結(jié)構(gòu)的號(hào)碼段匹配算法及其實(shí)現(xiàn)，包括：

采用鎖的機(jī)制，對(duì)于號(hào)碼段數(shù)據(jù)的增、刪、查操作都使用了鎖，從而支持多線程的操作，保證在多線程環(huán)境下的安全使用。。

由上述方案可以看出，本發(fā)明中每一個(gè)號(hào)碼段對(duì)應(yīng)為樹型結(jié)構(gòu)中的一個(gè)路徑，一個(gè)號(hào)碼的匹配過程最多為該號(hào)碼長(zhǎng)度的2倍次操作，從而減少了號(hào)碼匹配的操作，可以作為一種高性能的號(hào)碼段匹配算法。

附圖說明

為了更清楚地說明本發(fā)明實(shí)施例或現(xiàn)有技術(shù)中的技術(shù)方案，下面將對(duì)實(shí)施例或現(xiàn)有技術(shù)描述中所需要使用的附圖作簡(jiǎn)單的介紹，顯而易見地，下面描述中的附圖僅僅是本發(fā)明的一些實(shí)施例，對(duì)于本領(lǐng)域普通技術(shù)人員來講，在不付出創(chuàng)造性勞動(dòng)性的前提下，還可以根據(jù)這些附圖獲得其他的附圖。

圖1為本發(fā)明實(shí)現(xiàn)中系統(tǒng)結(jié)構(gòu)示意圖；

圖2為本發(fā)明實(shí)施例一中樹型結(jié)構(gòu)數(shù)據(jù)示意圖。

具體實(shí)施方式