基于樹的物聯(lián)網(wǎng)標(biāo)識識別算法的研究

趙 迎，魯 陽，凌 靜，江凌云

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

物聯(lián)網(wǎng)從發(fā)展到現(xiàn)在，一直是在各自垂直領(lǐng)域內(nèi)構(gòu)建出封閉的，緊耦合的豎井式的系統(tǒng)，各個系統(tǒng)之間缺少統(tǒng)一的交互。這些系統(tǒng)具有不同的系統(tǒng)架構(gòu)和數(shù)據(jù)模型，系統(tǒng)之間的信息不能共享，互操作性成為了一個顯著問題[1]。為了解決異構(gòu)系統(tǒng)之間的交互，鄒俊偉提出了Restful的開放式架構(gòu)[2]，衍生出了基于SOA的解決方案[3-4]。識別給定物品標(biāo)識成為解決異構(gòu)平臺系統(tǒng)互通的首要問題。

國內(nèi)外不同地區(qū)不同組織提出了適用于自身服務(wù)類型的標(biāo)識符設(shè)計方案，以構(gòu)成完整的標(biāo)識體系。主流的有美國EPC global提出的EPC(electric product code)，日本uID中心提出的uCode(ubiquitous code)，韓國TTA(telecommunications technology association)提出的mRFID(mobile RFID code)和中國商務(wù)部提出的CPC(commerce product code)和Ecode(entity code)，以及ITU和ISO/IEC提出的OID等。每個體系都十分完整，具有良好的兼容性和可擴(kuò)展性，而且在所屬地區(qū)和所屬領(lǐng)域有著長久的發(fā)展和深厚的根基，沒有一方吞并另一方的可能。但在萬物互聯(lián)的物聯(lián)網(wǎng)時代，為打破信息壁壘，便于任何用戶都可以查詢或追蹤到任何種類任何形式的信息，減少物流、經(jīng)銷、管理等方面的成本，需要實(shí)現(xiàn)不同標(biāo)識體系間的互聯(lián)互通，最大程度地做到信息共享。

實(shí)現(xiàn)不同標(biāo)識體系間的互聯(lián)互通的最大問題在于各標(biāo)識體系使用的標(biāo)識的異構(gòu)性。為解決這個問題，文中提出了一種基于樹形結(jié)構(gòu)的匹配算法。使用Hash算法結(jié)合基于正則表達(dá)式的模糊匹配算法進(jìn)行匹配過程。提出樹型結(jié)構(gòu)的匹配模型，降低了匹配次數(shù)，提出同層優(yōu)先級排序的方法，使得信息量大的標(biāo)識規(guī)則優(yōu)先匹配，提高了匹配效率。由于每個標(biāo)識體系結(jié)構(gòu)完整，識別出標(biāo)識符對應(yīng)的體系后便可以快速完成物品信息的解析獲取。

1 相關(guān)工作

2014年G. Deng提出了一種基于特征提取機(jī)制的識別算法[5]。通過長度，單字節(jié)和擴(kuò)展規(guī)則實(shí)現(xiàn)標(biāo)識特征的提取。除了自定義的特征提取算法以外，還有字符串匹配算法。常見的字符串匹配方式有字符串相似性算法和哈希算法。

(1)相似性算法。

常用的相似性算法有余弦相似性算法，如式1：

(1)

其中，A、B為向量空間中的兩個向量。

當(dāng)使用它來做字符串相似性度量時，需要先將字符串向量化，通常使用詞袋模型[6]進(jìn)行向量化。例如：StringA=“apple”，StringB=“app”,詞包為{‘a(chǎn)’,‘e’,‘l’,‘p’}，若使用0,1判斷元素是否在詞包中，字符串可以轉(zhuǎn)化為：StringA=[1111]和StringB=[1001]。根據(jù)余弦公式，可以計算字符串相似性為0.707。其他相似算法包括歐氏距離算法、編輯距離算法、海明距離算法、Dice距離算法等。但這些算法都不適用于該場景，無法確定參考對象，也就無法計算相似度。

(2)哈希算法。

哈希算法具有查找時間快的優(yōu)點(diǎn)，常見的哈希算法有：BKDRHash、APHash、DJBHash、JSHash、RSHash。比如最常見的BKDRHash算法，公式見式2。

Hash[i] = Hash[i-1]*x+s[i]

(2)

其中，x是哈希種子，常取數(shù)為31、131、1 313、13 131、131 313等；Hash[0]=0，1

通過分析，字符串相似性算法在該場景下沒有對照對象，無法使用。哈希算法的前提是散列表存儲中已經(jīng)存有該字符串的Hash值，不能用于精確匹配。

對此，文中提出了一種基于樹的匹配算法。在樹形匹配領(lǐng)域，尤濤根據(jù)概率疊加的思想構(gòu)建前件發(fā)生樹，大大提高了搜索效率[7]。趙艷妮提出了一種基于有效路徑權(quán)重的樹匹配算法，提高了XML文檔的搜索效率[8]。鄭津楊提出判決樹和自動機(jī)相結(jié)合的方法對RFID進(jìn)行分類[9]。張慧穎提出了一種基于DOM子樹的數(shù)據(jù)抽取方法，提高了準(zhǔn)確度[10]。

2 基于樹的匹配算法

文中提出了基于樹形結(jié)構(gòu)的匹配算法，該算法使用Hash算法和基于正則表達(dá)式的模糊匹配算法?；跇涞钠ヅ渌惴ò旅鎺讉€步驟。首先用Hash算法快速檢測當(dāng)前的標(biāo)識是否已經(jīng)存儲在數(shù)據(jù)庫中，如果存在返回標(biāo)識對應(yīng)結(jié)果，否則進(jìn)入樹形匹配過程；接著構(gòu)建合理的樹形模型，減少樹的匹配高度，以減少冗余匹配次數(shù)；在此基礎(chǔ)上使用基于正則表達(dá)式的模糊匹配算法，需要將特定的物聯(lián)網(wǎng)物品標(biāo)識特征進(jìn)行分析，提取特征抽象成正則表達(dá)式范式；最后對同層次的規(guī)則進(jìn)行信息量優(yōu)先排序，使用下文提出的匹配流程進(jìn)行匹配。

2.1 正則表達(dá)式

正則表達(dá)式起源于1951年，當(dāng)時美國數(shù)學(xué)家Stephen Cole Kleene用他的數(shù)學(xué)符號描述正則代數(shù)集。這些集合產(chǎn)生于理論計算機(jī)科學(xué)，自動機(jī)理論(計算模型)的子領(lǐng)域以及形式語言的描述和分類。它是提供給計算機(jī)操作和檢驗(yàn)所要抽取的字符串?dāng)?shù)據(jù)的一種強(qiáng)大的工具，是一串由特定意義的字符組成的字符串，表示某種匹配的規(guī)則[11]。正則表達(dá)式能夠應(yīng)用在Linux、Windows等多種操作系統(tǒng)中，幾乎所有的語言(如PHP、C#、Java)等都支持它。正則表達(dá)式用于匹配是非常有效的。丁麟軒提出了一種基于并行字符串索引的多步長正則表達(dá)式匹配算法[12]，減少了開銷，提高了吞吐率。李璋提出一種基于分布式存儲的正則表達(dá)式匹配并行算法，提高了算法實(shí)時性[13]。

常見的正則表達(dá)式符號及其含義如表1所示。

表1 常見的正則表達(dá)式字符

文中給出Handle、doi、OID編碼使用正則表達(dá)式的示例。如下：

(1)匹配Handle碼，Handle編碼規(guī)范是“Handle前綴/Handle后綴”，則可以使用正則表達(dá)式“([a-zA-Z0-9\.]+)/([a-zA-Z0-9\.]+)”。其中“[a-zA-Z0-9\.]”表示包含小寫字母、大寫字母、數(shù)字和.在內(nèi)的字符，“+”表示前面的符號集出現(xiàn)至少一次，所以整個表達(dá)式就是在/前后可以包含至少出現(xiàn)一次的包含字母、數(shù)字和.的字符。

(2)匹配Handle碼體系下的doi編碼，doi編碼規(guī)范是“doi前綴(10.*) /doi后綴”，則可以使用正則表達(dá)式“10\.(\d+)/([0-9a-zA-Z]+)”。其中(\d+)表示至少出現(xiàn)一位數(shù)字，([0-9a-zA-Z]+)表示字符(字母或數(shù)字)至少出現(xiàn)一次。

(3)匹配OID編碼，OID編碼規(guī)范是“(ITU-T|ISO|Joint-ISO-ITU-T).(國家|標(biāo)準(zhǔn)|注冊機(jī)構(gòu)|其他組織).…”，則可以使用正則表達(dá)式“[0-2]{1}\.((1?\d)|(2[0-3]))((\.\d+){4,})”。其中[0-2]{1}表示出現(xiàn)0,1,2數(shù)字中的一個，(1?\d)表示數(shù)字0到19，(2[0-3])表示數(shù)字20到23，所以((1?\d)|(2[0-3]))表示0-23。(\.\d+)表示.至少一位數(shù)字，{4,}表示表達(dá)式(\.\d+)至少出現(xiàn)4次。

2.2 樹形匹配模型

為了優(yōu)化匹配的次數(shù)，減少多余的無用匹配次數(shù)，通過分析思考和參考數(shù)據(jù)結(jié)構(gòu)樹模型，提出了基于樹的匹配算法。在單鏈表中查找元素的時間復(fù)雜度是O(n)，n是鏈表的長度。二叉樹中查找元素的平均時間復(fù)雜度為O(logn)[14]，n是二叉樹的節(jié)點(diǎn)數(shù)。查找的次數(shù)大大減少，查找的次數(shù)是樹的高度(層數(shù))。如果使用線性結(jié)構(gòu)，那么平均匹配次數(shù)是n/2，最差匹配次數(shù)是n，n是匹配規(guī)則的個數(shù)。如果構(gòu)造出合理的樹形結(jié)構(gòu)的匹配規(guī)則樹，平均查找次數(shù)是m次，m是構(gòu)造的樹的高度，在n越大時，m遠(yuǎn)小于n，大大減少了無用的匹配次數(shù)，最大程度避免了冗余匹配。構(gòu)建的規(guī)則樹如圖1所示，由于版面限制，只畫出了規(guī)則樹的部分。查找算法的次數(shù)取決于樹的寬度和深度，樹太寬或者樹太深都不能達(dá)到很好的效果，結(jié)合實(shí)際情況，選擇合適的寬度將減小匹配次數(shù)。

圖1 樹形模型

2.3 優(yōu)先級排序

為了進(jìn)一步提高匹配效率，該方法使用了優(yōu)先級思想。不同類型的物聯(lián)網(wǎng)物品標(biāo)識具有不同的特征，例如，不同種類的物聯(lián)網(wǎng)標(biāo)識符的長度不同，或者標(biāo)識含有特殊符號?！耙?guī)則”用于間接描述物聯(lián)網(wǎng)物品標(biāo)識的特征。一個物聯(lián)網(wǎng)物品標(biāo)識的每個特征是指一個“規(guī)則”。如果一種物聯(lián)網(wǎng)物品標(biāo)識具有一個特定的特征，則可以說這種物聯(lián)網(wǎng)物品標(biāo)識服從與之對應(yīng)的“規(guī)則”。如果不是，則這種物聯(lián)網(wǎng)物品標(biāo)識不符合“規(guī)則”。例如，如果一個“規(guī)則”被定義為一個特定物聯(lián)網(wǎng)物品標(biāo)識的第一個字符為“A”，則一個輸入字符串“Abcefg”完全服從上述“規(guī)則”。否則，如果物聯(lián)網(wǎng)物品標(biāo)識以“B”開始，那么物聯(lián)網(wǎng)物品標(biāo)識顯然不遵守“規(guī)則”。由于不同物聯(lián)網(wǎng)物品標(biāo)識之間的先驗(yàn)概率差異以及不同“規(guī)則”范圍的差異，規(guī)則匹配中包含的信息各不相同。例如，如果所有物聯(lián)網(wǎng)標(biāo)識符都遵守一個特定的“規(guī)則”，則該“規(guī)則”的匹配不能提供任何信息，因?yàn)槭孪纫呀?jīng)知道匹配結(jié)果。為了評估包含在“規(guī)則”匹配中的信息，令w為上述信息，然后根據(jù)經(jīng)典信息論[15]，如式3：

(3)

其中，p為給定物品標(biāo)識服從規(guī)則的概率，q為不符合規(guī)則的概率，p+q=1。

2.4 樹匹配算法流程

算法流程如圖2所示。

圖2 算法流程

具體步驟如下：

步驟1：從root入口進(jìn)入規(guī)則樹，首先通過Hash映射算法，檢查數(shù)據(jù)庫中是否已經(jīng)包含該標(biāo)識，若存在，則直接返回結(jié)果，若無則進(jìn)入步驟2。

步驟2：對該層的規(guī)則進(jìn)行信息量大小的排序，信息量定義規(guī)則如上，信息量大的規(guī)則優(yōu)先匹配。

步驟3：依次匹配排序好的規(guī)則序列，若匹配成功，則標(biāo)記當(dāng)前成功規(guī)則且記為rule1，若遍歷全部規(guī)則都沒有匹配成功，則返回匹配失敗。

步驟4：進(jìn)入rule1的子規(guī)則樹中，重復(fù)執(zhí)行步驟2、步驟3，循環(huán)迭代，若最終匹配成功，返回匹配結(jié)果，若失敗則將該標(biāo)識返回上一層。

3 原型系統(tǒng)

3.1 系統(tǒng)框架

圖3是異構(gòu)物品標(biāo)識識別系統(tǒng)的實(shí)現(xiàn)框架，包括客戶端(client)和服務(wù)端(server)。

圖3 系統(tǒng)框架

客戶端的體系結(jié)構(gòu)由三部分組成：用戶界面，程序和數(shù)據(jù)接口。用戶界面呈現(xiàn)查詢請求的結(jié)果，并為用戶輸入提供文本輸入窗口。程序部分是處理后端傳送的數(shù)據(jù)，為了顯示給用戶界面，進(jìn)行一定的預(yù)處理，并提高用戶體驗(yàn)和結(jié)果的準(zhǔn)確性。

服務(wù)端的體系結(jié)構(gòu)由三部分組成：識別核心服務(wù)，特征提取模塊，數(shù)據(jù)庫。識別核心服務(wù)是整個體系的核心部分，包含匹配樹模型的構(gòu)建和匹配算法。特征提取模塊是為識別核心服務(wù)提供支持，負(fù)責(zé)將規(guī)則的特征提取出來，構(gòu)建正則表達(dá)式，以及對規(guī)則的信息量進(jìn)行優(yōu)先級排序。數(shù)據(jù)庫是存放信息數(shù)據(jù)，可以將已匹配的標(biāo)識進(jìn)行緩存，利用Hash算法可以快速檢測待輸入的數(shù)據(jù)是否已經(jīng)存儲在數(shù)據(jù)庫中，如果有，將結(jié)果直接返回。

3.2 實(shí)驗(yàn)環(huán)境

文中設(shè)計并實(shí)施了一些實(shí)驗(yàn)來檢驗(yàn)系統(tǒng)的性能。實(shí)驗(yàn)設(shè)置如表2所示。臺式機(jī)作為服務(wù)器，而Lenovo Y580筆記本作為客戶端，其中安裝了Chrome瀏覽器?？蛻舳撕头?wù)器通過有線局域網(wǎng)連接。

3.3 實(shí)驗(yàn)結(jié)果

在這個原型系統(tǒng)中，引入了100個物聯(lián)網(wǎng)物品標(biāo)識標(biāo)準(zhǔn)，從以下兩個方面評估該系統(tǒng)的性能：識別率和識別速度。識別率是在物聯(lián)網(wǎng)物品標(biāo)識中成功識別的物聯(lián)網(wǎng)物品標(biāo)識的百分比;識別速度意味著花費(fèi)在識別一個給定物聯(lián)網(wǎng)物品所花費(fèi)的時間。從100個標(biāo)準(zhǔn)中隨機(jī)生成了15 000個實(shí)際的物品標(biāo)識并將其提供給原型系統(tǒng)，實(shí)驗(yàn)樣例如表3所示。綜合識別率接近100%，表明原型算法有效。經(jīng)過分析，EPC子類出現(xiàn)了極其相似的數(shù)據(jù)樣本，需要進(jìn)一步提取特征，構(gòu)建模型。

表2 實(shí)驗(yàn)配置

表3 測試樣本

此外，計算時間通過以下方式獲得。首先，隨機(jī)選擇30個不同的物聯(lián)網(wǎng)物品標(biāo)識標(biāo)準(zhǔn)，然后生成每個標(biāo)準(zhǔn)的3個特定物聯(lián)網(wǎng)物品標(biāo)識；接下來，將這些生成的物聯(lián)網(wǎng)物品標(biāo)識逐個輸入系統(tǒng)，并記錄從開始到結(jié)果出現(xiàn)的時間。計算每個物聯(lián)網(wǎng)物品標(biāo)識標(biāo)準(zhǔn)的平均計算時間，并繪制累積分布概率圖(見圖4)?？梢钥闯?，平均計算時間約為280 ms，盡管計算時間需要進(jìn)一步減少，但這是可以接受的。

圖4 計算時間累積分布

4 結(jié)束語

如何識別給定物品標(biāo)識的類型是物聯(lián)網(wǎng)異構(gòu)解析系統(tǒng)的一個關(guān)鍵點(diǎn)。針對這個問題，提出了一種基于樹的匹配算法的物品標(biāo)識識別系統(tǒng)。首先對物聯(lián)網(wǎng)標(biāo)識標(biāo)準(zhǔn)進(jìn)行分析，提取出標(biāo)準(zhǔn)的特征，將特征抽象成范式。接著構(gòu)建樹形匹配模型，降低匹配的冗余度，然后對每一層使用信息量優(yōu)先級排序，最后使用樹形匹配算法進(jìn)行匹配識別?；谏鲜鏊惴?gòu)建了原型系統(tǒng)，實(shí)驗(yàn)結(jié)果表明該系統(tǒng)不僅識別率高，而且速度快。