趙 迎，魯 陽(yáng)，凌 靜，江凌云

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

0 引 言

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

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

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

1 相關(guān)工作

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

(1)相似性算法。

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

(1)

其中，A、B為向量空間中的兩個(gè)向量。

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

(2)哈希算法。

哈希算法具有查找時(shí)間快的優(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

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

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

2 基于樹的匹配算法

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

2.1 正則表達(dá)式

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

常見的正則表達(dá)式符號(hào)及其含義如表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)的字符，“+”表示前面的符號(hào)集出現(xiàn)至少一次，所以整個(gè)表達(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).(國(guó)家|標(biāo)準(zhǔn)|注冊(cè)機(jī)構(gòu)|其他組織).…”，則可以使用正則表達(dá)式“[0-2]{1}\.((1?\d)|(2[0-3]))((\.\d+){4,})”。其中[0-2]{1}表示出現(xiàn)0,1,2數(shù)字中的一個(gè)，(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ù)，減少多余的無(wú)用匹配次數(shù)，通過(guò)分析思考和參考數(shù)據(jù)結(jié)構(gòu)樹模型，提出了基于樹的匹配算法。在單鏈表中查找元素的時(shí)間復(fù)雜度是O(n)，n是鏈表的長(zhǎng)度。二叉樹中查找元素的平均時(shí)間復(fù)雜度為O(logn)[14]，n是二叉樹的節(jié)點(diǎn)數(shù)。查找的次數(shù)大大減少，查找的次數(shù)是樹的高度(層數(shù))。如果使用線性結(jié)構(gòu)，那么平均匹配次數(shù)是n/2，最差匹配次數(shù)是n，n是匹配規(guī)則的個(gè)數(shù)。如果構(gòu)造出合理的樹形結(jié)構(gòu)的匹配規(guī)則樹，平均查找次數(shù)是m次，m是構(gòu)造的樹的高度，在n越大時(shí)，m遠(yuǎn)小于n，大大減少了無(wú)用的匹配次數(shù)，最大程度避免了冗余匹配。構(gòu)建的規(guī)則樹如圖1所示，由于版面限制，只畫出了規(guī)則樹的部分。查找算法的次數(shù)取決于樹的寬度和深度，樹太寬或者樹太深都不能達(dá)到很好的效果，結(jié)合實(shí)際情況，選擇合適的寬度將減小匹配次數(shù)。

圖1 樹形模型

2.3 優(yōu)先級(jí)排序

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

(3)

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

2.4 樹匹配算法流程

算法流程如圖2所示。

圖2 算法流程

具體步驟如下：

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

步驟2：對(duì)該層的規(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)識(shí)返回上一層。

3 原型系統(tǒng)

3.1 系統(tǒng)框架

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

圖3 系統(tǒng)框架

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

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

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

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

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

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

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

表3 測(cè)試樣本

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

圖4 計(jì)算時(shí)間累積分布

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

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