基于改進CDC的實驗原始記錄匹配算法

蔡伊娜，陳新，覃志武，，王歆，包先雨，，彭錦學，林泳奇，李俊霖

1）深圳市檢驗檢疫科學研究院，廣東深圳 518045；2）深圳海關食品檢驗檢疫技術中心，廣東深圳 518045；3）深圳海關信息中心，廣東深圳518045

隨著實驗室檢測技術的精細化，如何從大量數據中提取有用信息成為實驗原始記錄文件處理研究的重點，字符串匹配是最常用的方法之一.經過幾十年的發(fā)展，字符串匹配已廣泛用于文本處理［1］、問答系統(tǒng)［2］和生物信息處理［3］等領域.

目前，實驗室用于檢測的設備普遍型號多，且存在檢測報告需人工錄入數據的現(xiàn)象，導致檢測時間長和易出現(xiàn)偶然性差錯等問題，難以滿足現(xiàn)代數字實驗室的建設和管理要求.字符串匹配作為文本處理的核心，直接影響數據采集效率.將高效的字符串匹配算法用于數字實驗室的數據處理中，是縮短檢測時間，減少偶然性差錯的有效途徑.實驗室檢測樣品時，檢測設備一般都會輸出一個或多個實驗原始記錄文件.在形成檢測報告前，需對該文件中的部分數據進行匹配和自動提取.由于該文件一般都具有固定的格式，針對此特點，現(xiàn)有的字符串匹配方法已有了一定的應用.但遇到實驗原始記錄中的大文件或多文件時，則存在計量大匹配速度慢和占用內存大等不足，難以滿足現(xiàn)代數字實驗室降本提效管理的需求.提高實驗原始記錄文件中的字符串匹配速度，減少內存占用量，在保證數據匹配準確性的前提下縮短檢測時間，這在當前檢測業(yè)務量日益增加的形勢下，解決實驗原始記錄文件高效匹配的問題刻不容緩.

字符串匹配即在任意一個長度為m的文本串T中，找出給定一組特定的字符串集合Pn（Pn的長度小于m）在T中的所有出現(xiàn)位置［4］.在實驗原始記錄文件中，數據匹配格式是以文本為主.根據模式串數目的多少，現(xiàn)有的針對文本文件的字符串匹配算法可分為單模式匹配算法和多模式匹配算法［5］兩類.隨著人們對單模式匹配的深入研究，現(xiàn)階段主要利用模式串具有前綴和后綴的特點來提升算法性能，如王東宏［6］基于后綴數組的單模式匹配建立的可驗證模式串匹配方法可靠性高，同時給出擴展方案實現(xiàn)多模式匹配提升了匹配速度.之后，又陸續(xù)出現(xiàn)了改進Trie 樹的Aho-Corasicsk（AC）優(yōu)化算法［1］、基于SHIFT 表的modified Wu-Manber（MWM）算法［7］、基于跳躍和確認機制的子集WM 算法［8］等多模式匹配算法.然而，無論是單模式還是多模式匹配算法都追求以1 個參數適用于所有目標文件，因此，不可避免地出現(xiàn)匹配速度低，預處理時間長和內存占用大等問題，難以滿足數字實驗室高效處理數據的需求.

字符串自適應匹配也是當前研究的一個重點.劉許剛等［9］設定出現(xiàn)頻率高且模式串中不包含的u為特殊字符對文本進行分段，但該方法在處理實驗原始記錄等無高頻字符的文件時，無法對目標文本進行分段.黃勇等［10］提出完成在當前窗口匹配后，通過提前預覽下一窗口基準字符的偏移信息，以期跳過盡可能多的窗口來進行下一輪匹配，但該算法對模式串具有依賴性，且性能不穩(wěn)定.

面對上述算法預處理時間長、內存占用大、分段困難和模式串依賴大等問題，董志鑫等［11］提出一種改進的多模式串匹配算法，通過基準長度分段和哈希（hash）算法跳過大量的字符，該方法雖提升了內存占用量，但精確度有所下降.TRIVEDI［12］提出一種優(yōu)化的Aho-Corasicsk算法，先將潛在的匹配模式串與輸入文本進行比較，多次嘗試實現(xiàn)匹配，該方法雖操作性佳，但存在內存占用量大、精確度低等問題.

而在數據分塊預處理研究中，傳統(tǒng)的內容可變長度分塊（content-defined chunking，CDC）算法用一個滑動窗口來劃分可變長度的數據塊，當滑動窗口的hash 值與一個基準值相匹配時就創(chuàng)建一個分塊，滑動窗口的大小是固定的，因此，CDC算法局限性主要體現(xiàn)在系統(tǒng)開銷大、耗時長和準確率低等問題［13］.李建江等［14］提出一種改進CDC的優(yōu)化算法，首先讓滑動窗口向前滑動，忽略窗口內指紋的計算和取值，直到該數據塊的長度等于設定的最小長度，之后比較滑動窗口指紋值，同時要保證該數據塊的最大長度小于設定的最大長度.若達到最大長度時，該數據塊仍不能滿足分塊條件，則在此位置強制分塊.但是，該算法因滑動窗口移動慢且匹配次數過多，分塊效率有待提升.此外，BJ?RNER等［15］提出local maximum chunking（LMC）算法，通過滑動窗口進行分塊，滑動窗口由左窗口、局部最大字節(jié)和右窗口3部分組成，但算法存在耗時長的缺陷.

1 原始記錄自動抓取

根據數字實驗室管理的要求，實驗室信息管理系統(tǒng)（lab information management system，LIMS）需要對檢測設備所輸出的實驗原始記錄文件實現(xiàn)自動抓取功能.本研究設計了基于柵欄因子的通用實驗原始記錄文件自動抓取技術（圖1）.針對實驗原始記錄文件“當日事當日畢”的管理要求，將時間設置為一個柵欄因子，通過比較文件創(chuàng)建時間和系統(tǒng)時間，初步過濾掉非當日實驗原始記錄文件.采用完全文件檢測（whole file detection，WFD）技術，以文件為顆粒度計算文件的hash 值作為另一個柵欄因子，過濾已讀取的文件，防止重復讀取文件［16］.

圖1 實驗原始記錄自動抓取流程圖Fig.1 Automatic capture process of experimental original records.

抓取步驟具體描述為

1）將實驗原始記錄文件保存在A文件夾中.

2）全部文件保存完畢后，啟動實驗原始記錄文件智能匹配軟件.

3）軟件自動讀取系統(tǒng)時間，并轉換為以8 位數字形式呈現(xiàn)的年月日格式，得到時間柵欄因子.

4）使用隊列結構實現(xiàn)廣度優(yōu)先遍歷，先從頭部取出母文件名打印并移除，然后把母文件夾下的子文件名添加到隊列.這樣，在遍歷的時候，文件名層級相同，從而實現(xiàn)了廣度優(yōu)先遍歷文件夾，獲取文件.

5）通過指定路徑文件所對應的File 對象，提取當前FileInfo 對象的創(chuàng)建時間，并將時間轉換為年月日格式.

6）比較文件的創(chuàng)建時間（年月日）與系統(tǒng)的時間柵欄因子是否為當日檢測所得的實驗原始記錄文件.若時間相同，按照步驟7）計算哈希值；否則，表示文件為非當日實驗原始記錄文件.

7）將整個文件作為一個顆粒度，利用SHA-2哈希算法計算文件的哈希值，得到哈希值柵欄因子.

8）比較文件哈希值與已儲存哈希值柵欄因子是否重復.其中，已儲存哈希值是指每次讀取文件所保存的文件哈希值.若重復，表示之前已讀取過該文件；若哈希值不重復，繼續(xù)下一步.

9）抓取文件并儲存哈希值.

10）通過文件搬運的方法，將非當日實驗原始記錄文件、重復文件和讀取過的文件剪切至B文件夾保存，以方便后續(xù)讀取新文件.

該文件抓取技術建立了文件創(chuàng)建時間初篩和文件哈希值精篩兩項柵欄.在初篩時，該技術能以低計算要求和低計算量的優(yōu)勢過濾全部非當日文件；在精篩時，通過計算文件整體哈希值準確過濾當日已讀取的文件.

2 匹配算法

字符串匹配算法分為預處理和匹配兩個過程.本研究首先通過改進CDC 算法對實驗原始記錄文件進行分塊預處理，再將數據塊哈希值、數據塊位地址和模式串等構建數據塊索引表，使數據塊與模式串之間形成映射關系，實現(xiàn)模式串在映射的數據塊中進行靈活的字符串匹配.通過引入可變長度分塊和建立映射關系，使字符串匹配的效率和效果得到優(yōu)化.

2.1 基于改進CDC的分塊算法

CDC 算法是應用Rabin 指紋將文件分割成長度大小不一的分塊策略［16］，用一個固定大小的滑動窗口來劃分文件，當滑動窗口的Rabin 指紋值與期望值相匹配時，在該位置劃分一個分割點，重復這個過程，直至整個文件被劃分，最終文件將按照預先設定的分割點被切割成數據塊.

檢測設備輸出的實驗原始記錄文件有著固定文件格式的特點，因此，本研究通過改進傳統(tǒng)的CDC，設計一種適用于格式固定的文件分塊算法，流程圖如圖2.

圖2 基于改進CDC的分塊算法流程圖Fig.2 Flow chart of block division algorithm based on improved CDC.

基于改進CDC的分塊算法具體實現(xiàn)步驟為：

1）讀取已抓取的文件.

2）設定一個大小為w的滑動窗口，以行與行間距之和的高度為1個單元進行滑動，直至滑動窗口被數據裝載完畢.

3）設定滑動窗口內字節(jié)值大小范圍，在滑動窗口被數據裝載完后，比較滑動窗口字節(jié)大小是否在設定范圍內.若是，跳到步驟4）；否則，滑動1個單位并重復步驟2）.

4）計算窗口內的Rabin指紋值.

5）比較Rabin 指紋值與循序漸進表中預設的滑動窗口期望指紋值.若兩值相等，則繼續(xù)步驟6）；若兩值不相等，重復步驟2）滑動一個單位.

6）以滑動窗口下邊界作分割線，對文本進行分割.

7）判斷滑動窗口是否抵達文件結尾處，即文件是否分塊完畢.若是，則文件分塊完成；否則，滑動1個單位并重復步驟2）.

此過程中循序漸進表先設定模式串對應的期望指紋值，根據文本匹配的模式串種類和順序確定表格匹配順序.假設第1個模式串對應的期望指紋值為A，滑動窗口某位置D的Rabin 指紋值為f，當滑動窗口某位置時若fmodD=A，則將D的下邊界作為一個分割線，創(chuàng)建1個分塊，以此類推.從而使模式串在數據塊前段完成字符串匹配，減少了匹配其余文本的操作，從而提高了匹配速度.

與傳統(tǒng)的CDC 算法相比，基于改進CDC 的分塊算法有以下改進：①設定了以行與行間距之和作為滑動窗口的高度向下移動的1 個單位.傳統(tǒng)CDC算法以1個字符為單位向右移動，而本研究算法可大幅減少匹配次數，縮短了分塊時間.②規(guī)定了滑動窗口內字節(jié)大小的范圍，初步過濾掉大部分不符合分割條件的滑動窗口位置.傳統(tǒng)CDC 算法每滑動1 次滑動窗口，都需要計算1 次窗口的Rabin 指紋值，并與設定的期望值進行比較，而本研究可減少滑動窗口的Rabin 指紋值的計算次數，有效降低分塊算法的計算量.③制定了滑動窗口期望指紋值的循序漸進表.傳統(tǒng)CDC 算法由于設定固定期望值，易將待匹配數據分屬到2個數據塊中，導致匹配失敗，而本研究算法能更精準地劃分文本數據塊的大小，有效避免這種情況的發(fā)生.

2.2 基于數據塊索引的字符串匹配算法

實驗原始記錄文件具有文本串T大而模式串Pn少的特點，使用傳統(tǒng)的字符串匹配方法易出現(xiàn)模式串匹配次數多、匹配時間長和計算復雜度高等問題.本研究提出基于數據塊索引的字符串匹配優(yōu)化算法，在文件分塊后，將數據塊的Hash 值與模式串和數據塊位地址組成數據塊檢索表.接著，模式串通過數據塊索引表快速匹配到相應數據塊.最后，模式串利用單模式匹配暴力（brute-force，BF）算法與映射的數據塊進行字符串匹配，得到字符串匹配結果.數據塊索引表如表1.其中，數據塊索引表的每條記錄都以數據塊身份標識號（identity document，ID）作為主鍵；數據塊位地址表示數據實際的物理位置.數據塊索引表中還保存著數據塊Hash 值、對應的模式串.所有記錄根據數據塊ID存放在數據塊索引表中，以此來保證查找的速度，降低匹配所需時間.

表1 數據塊索引表Table 1 Block index table

模式串與數據塊的相互匹配可根據模式串的長短選擇適合的單模式匹配算法，以提高匹配效率.當模式串匹配的文本位置較集中時，可將文本劃在一個數據塊中，將單模式匹配算法轉化為多模式進行精準匹配，從而減少分塊數量，避免出現(xiàn)過小分塊.通過建立模式串與數據塊之間對應的映射關系，成功構建靈活多變的模式串匹配算法.該算法不僅可提高字符串匹配效率，還可適用于不同的實驗原始記錄文件.

3 實驗與結果分析

3.1 實驗環(huán)境

實驗硬件環(huán)境為：處理器Intel?Core ?i7-2670QM CPU@2.20 GHz，4 核；軟件環(huán)境為：Ubuntu 16.04（64 bit）、C 語言、GNU C 編譯器version 5.4.0.通過內存占用量實驗［10］和計算分塊吞吐量對基于改進CDC 的分塊算法進行測試.實驗所用儀器和實驗原始記錄文件均由深圳海關實驗室提供，實驗運行時間單位為ms.

3.2 內存占用量實驗

因本研究關注的是匹配性能，所以實驗比較了分別采用基于改進CDC 的分塊算法、優(yōu)化Aho-Corasick 算法［12］和DKR 算法［11］時所用的內存占用量.實驗使用安捷倫液相色譜儀1290Q（D030202）輸出的實驗原始記錄文件，模式串個數分別為100、200、400、800 和1 600，單個模式串長度在2～10.使用最大駐留集的大小來表示程序運行中內存占用量，實驗結果如圖3.

圖3 不同模式串個數對應算法內存占用量Fig.3 The memory consumption under DKR(triangle),optimized Aho-Corasick(cicle),and our algrithm(square).

由圖3可見，當模式串個數較少時，基于改進CDC 的分塊算法在內存占用量方面比優(yōu)化Aho-Corasick和DKR算法有明顯優(yōu)勢.對于模式串匹配個數不多的實驗原始記錄文件來說，在實際運用中基于改進CDC 的分塊算法在內存占用量上更具優(yōu)勢，能夠降低對設備的硬件要求.

3.3 分塊吞吐量實驗

分塊吞吐量（chunking throughput）是通過將數據大小除以處理的數據量和分塊文件所消耗的時間量來計算的，即

其中，因為本研究關注的是分塊性能，所以此時的分塊時間不包括數據讀取時間.

為分析本實驗在分塊方面的性能，比較基于改進CDC 的分塊算法、LMC 算法和傳統(tǒng)CDC 算法的分塊吞吐量.LMC算法使用固定的對稱窗口和文件的字節(jié)值來檢測切割點，規(guī)避了傳統(tǒng)CDC 算法存在的計算量大的問題.根據深圳海關實驗室提供的原始記錄文件份數的不同，實驗共進行8 組測試，選擇實驗原始記錄文件數據集共4個.為避免因偶然性導致的異常結果，每組匹配測試分別進行10次，并以10 次實驗結果的平均值作為最終的分塊吞吐量.

由圖4可見，本研究提出的基于改進CDC的分塊算法的分塊吞吐量明顯高于傳統(tǒng)CDC 算法和LMC算法.

圖4 三種算法分塊吞吐量對比Fig.4 Comparison of block throughput of CDC(blank),LMC(forward slash),and our algorithm(backslash).

結論

提出基于改進CDC 的實驗原始記錄匹配算法首先對實驗原始記錄文件進行抓取，然后改進現(xiàn)有CDC算法實現(xiàn)文本分塊，再通過數據塊索引表建立模式串與數據塊的映射關系，形成了高效靈活的字符串匹配優(yōu)化算法.該算法在模式串個數較少時，內存占用量少.而在分塊吞吐量方面，與DKR 算法和傳統(tǒng)CDC 算法相比，本研究提出的算法提升較為明顯.因此，該算法可廣泛應用于數字實驗室中的實驗原始記錄快速處理.