基于職業(yè)院校數(shù)據(jù)與指標(biāo)匹配的編輯距離算法的應(yīng)用研究

李華君　郭晟君

摘? ?要：隨著互聯(lián)網(wǎng)的迅速發(fā)展，數(shù)據(jù)越來越多，分析數(shù)據(jù)愈發(fā)困難。為給山西省職業(yè)教育大數(shù)據(jù)分析與決策平臺(tái)提供大量且準(zhǔn)確的數(shù)據(jù)，首先要將不同文本中的數(shù)據(jù)進(jìn)行整理，其次將數(shù)據(jù)名稱與已經(jīng)命名好的指標(biāo)進(jìn)行匹配，進(jìn)而實(shí)現(xiàn)數(shù)據(jù)與指標(biāo)的匹配?；诖?，本文采用了編輯距離算法，該算法以單個(gè)字符為單位進(jìn)行編輯距離測(cè)算，通過計(jì)算從原字符串轉(zhuǎn)換到目標(biāo)字符串所需插入、刪除和替換的數(shù)目，得到原字符串與目標(biāo)字符串的相似度，進(jìn)行字符串之間的匹配，進(jìn)而解決了數(shù)據(jù)與指標(biāo)匹配的問題。

關(guān)鍵詞：數(shù)據(jù)分析? 指標(biāo)匹配? 編輯距離? 相似度

中圖分類號(hào)：G64? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1674-098X（2019）10（c）-0255-02

為給山西省職業(yè)教育大數(shù)據(jù)分析與決策平臺(tái)提供大量且準(zhǔn)確的數(shù)據(jù)，必須通過調(diào)研采集信息或梳理年報(bào)等方式提取學(xué)校信息，由于學(xué)校無指標(biāo)名稱且各個(gè)學(xué)校信息不同，所以梳理出來的數(shù)據(jù)名稱各式各樣，例如：就文本中關(guān)于指標(biāo)“享受國(guó)家助學(xué)金人次”就有“享受國(guó)家助學(xué)金人數(shù)”、“國(guó)家助學(xué)金受助學(xué)生人數(shù)”、“中職學(xué)生國(guó)家助學(xué)金受助人數(shù)”、“享受國(guó)家助學(xué)金學(xué)生人數(shù)”等4種叫法。對(duì)于人工梳理信息，不僅要整理出原始數(shù)據(jù)，還要將數(shù)據(jù)填到相應(yīng)的指標(biāo)，此外還要進(jìn)行多次的重復(fù)檢查工作，大大降低了工作效率。采用編輯距離的算法通過算出指標(biāo)字符串與數(shù)據(jù)名稱字符串的相似度，將相似度高的數(shù)據(jù)名稱被指標(biāo)替代，并把數(shù)據(jù)提取出來，放在相應(yīng)的指標(biāo)下，這樣就實(shí)現(xiàn)了數(shù)據(jù)與指標(biāo)的匹配。

1? 編輯距離的概念

編輯距離，又稱Levenshtein距離，是指兩個(gè)字串之間，由一個(gè)字符串轉(zhuǎn)成另一個(gè)字符串所需的最少編輯操作次數(shù)，如果它們的距離越大，說明它們?cè)绞遣煌聪嗨贫仍降停?/p>

許可的編輯操作只有三種：插入、刪除和替換。

2? 編輯距離算法

創(chuàng)建一個(gè)矩陣，假設(shè)有兩個(gè)字符串A和B，我們的字符串的長(zhǎng)度分別是m和n，矩陣的維度就是（m+1）*（n+1），給矩陣第一行和第一列分別以0開始，以1遞增的方式賦值，如表1所示，通過計(jì)算規(guī)則：

3? 數(shù)據(jù)與指標(biāo)匹配思想的設(shè)計(jì)

（1）人工提取內(nèi)容。

由于數(shù)據(jù)是在文章中大篇幅存在，目前也沒有最準(zhǔn)確的提取“內(nèi)容+數(shù)據(jù)”的方法，為保證數(shù)據(jù)的準(zhǔn)確性和內(nèi)容的完整性，由人工按照原文檔內(nèi)容將數(shù)據(jù)整理成Excel表格，如圖2所示（以“資助情況”為例）。

（2）將字符串分為單個(gè)字符。

將表2中數(shù)據(jù)名稱每一格的文字提取出來，將單個(gè)字符依次按照順序排列到矩陣中，便于數(shù)據(jù)名稱（原字符串）與指標(biāo)（目標(biāo)字符串）匹配。

（3）數(shù)據(jù)名稱與指標(biāo)匹配。

數(shù)據(jù)名稱（原字符串）與每個(gè)指標(biāo)（目標(biāo)字符串）通過編輯距離算法進(jìn)行匹配，計(jì)算相似度，相似度越接近1，表示相似度越大，通過對(duì)比相似度，數(shù)據(jù)名稱可直接被相似度最高的指標(biāo)所替代。

（4）數(shù)據(jù)與指標(biāo)匹配。

4? 實(shí)驗(yàn)結(jié)果及分析

本文隨機(jī)選取了幾篇職業(yè)院校的年報(bào)，將同一版塊的內(nèi)容提取出來（以“資助情況”為主要板塊），共提取出50個(gè)數(shù)據(jù)名稱，按照人工匹配指標(biāo)的方式和上述方法（編輯距離算法）分別對(duì)50個(gè)樣本進(jìn)行測(cè)試，測(cè)試結(jié)果如圖7所示（每個(gè)數(shù)據(jù)名稱不一定都有對(duì)應(yīng)的指標(biāo)，所以存在數(shù)據(jù)名稱匹配不到指標(biāo)的情況），實(shí)驗(yàn)主要是通過測(cè)試編輯距離算法的準(zhǔn)確率，得到編輯距離算法是否可大量減少人的工作量的結(jié)論。其中準(zhǔn)確率計(jì)算方法為：

測(cè)試的數(shù)據(jù)名稱共有50個(gè)，指標(biāo)共有24個(gè)，本文對(duì)于相似度的閾值設(shè)置為0.65，當(dāng)前相似度正好為0.65即認(rèn)為這兩個(gè)語句相似，相似度越接近1，表示這兩個(gè)語句越相似。

由實(shí)驗(yàn)結(jié)果表明，編輯距離算法的準(zhǔn)確率可以達(dá)到79.5%，充分說明了編輯距離算法可以在匹配指標(biāo)上應(yīng)用，可大大減少人的工作量。

5? 結(jié)語

本文論述了基于職業(yè)院校數(shù)據(jù)與指標(biāo)匹配的編輯距離算法的應(yīng)用研究，通過匹配數(shù)據(jù)名稱與指標(biāo)，進(jìn)而得到數(shù)據(jù)與指標(biāo)的匹配。根據(jù)實(shí)驗(yàn)結(jié)果，得出編輯距離算法在指標(biāo)匹配上應(yīng)用的結(jié)論，可大量減少人的工作量。但是該算法還有不足之處，由于是對(duì)中文語句進(jìn)行相似度比較，同義近義字可能會(huì)導(dǎo)致算法有大的誤差，這時(shí)仍需要人工進(jìn)行分辨，也是下一步研究的重點(diǎn)方向。

參考文獻(xiàn)

[1] 王芳，王繼榮，楊曉東，等.基于中文文本的編輯距離算法的改進(jìn)[J].青島大學(xué)學(xué)報(bào)：自然科學(xué)版，2017，30（3）：60-63.

[2] 邵清，葉琨.基于編輯距離和相似度改進(jìn)的漢字字符串匹配[J].電子科技，2016，29（9）：7-11.

[3] 姜華，韓安琪，王美佳，等.基于改進(jìn)編輯距離的字符串相似度求解算法[J].計(jì)算機(jī)工程，2014，40（1）：222-227.