基于職業院校數據與指標匹配的編輯距離算法的應用研究

李華君　郭晟君

摘? ?要：隨著互聯網的迅速發展，數據越來越多，分析數據愈發困難。為給山西省職業教育大數據分析與決策平臺提供大量且準確的數據，首先要將不同文本中的數據進行整理，其次將數據名稱與已經命名好的指標進行匹配，進而實現數據與指標的匹配。基于此，本文采用了編輯距離算法，該算法以單個字符為單位進行編輯距離測算，通過計算從原字符串轉換到目標字符串所需插入、刪除和替換的數目，得到原字符串與目標字符串的相似度，進行字符串之間的匹配，進而解決了數據與指標匹配的問題。

關鍵詞：數據分析? 指標匹配? 編輯距離? 相似度

中圖分類號：G64? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1674-098X（2019）10（c）-0255-02

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

1? 編輯距離的概念

編輯距離，又稱Levenshtein距離，是指兩個字串之間，由一個字符串轉成另一個字符串所需的最少編輯操作次數，如果它們的距離越大，說明它們越是不同（即相似度越低）。

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

2? 編輯距離算法

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

3? 數據與指標匹配思想的設計

（1）人工提取內容。

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

（2）將字符串分為單個字符。

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

（3）數據名稱與指標匹配。

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

（4）數據與指標匹配。

4? 實驗結果及分析

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

測試的數據名稱共有50個，指標共有24個，本文對于相似度的閾值設置為0.65，當前相似度正好為0.65即認為這兩個語句相似，相似度越接近1，表示這兩個語句越相似。

由實驗結果表明，編輯距離算法的準確率可以達到79.5%，充分說明了編輯距離算法可以在匹配指標上應用，可大大減少人的工作量。

5? 結語

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

參考文獻

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

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

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