何曉明 洪親 蔡堅勇 林鴻

摘要：相似字符串的模糊查詢是信息檢索的重要組成部分,一直是人們研究的熱點。目前基于關鍵詞的查詢技術都是前綴匹配,無法查找到與搜索字符串相似的結果。該文提出一種基于n-gram的中英文字符串分割技術的算法,該技術主要是對字符串進行中英文識別，然后基于n-gram按照指定長度進行分割，該技術是實現基于關鍵詞的模糊查詢技術的基礎。該技術在數據清洗以及學位論文TMLC系統和垃圾郵件過濾等方面也有重要的應用前景。

關鍵詞:模糊查詢; n-gram;字符串分割;編輯距離;數據挖掘

中圖分類號：TP391文獻標識碼：A文章編號：1009-3044(2012)23-5530-04

Implementation of Algorithm Based on n-gram Chinese-English String Segmentation

HE Xiao-ming，HONG Qin，CAI Jian-yong，LIN Hong

(College of Photonic and Electronic Engineering of Fujian Normal University Cangshan Campus, Fuzhou 350007, China)

Abstract: Similar string of fuzzy query is an important part of the information retrieval, has been the hotspot of the research. The keyword search technology is the prefix matching, unable to find similar results with the search string. This paper presents a n-gram based in the Chi? nese-English string segmentation algorithm, the technique is mainly to string recognition based on n-gram in Chinese-English, then in ac? cordance with the specified length of segmentation, the technique is realized based on keywords fuzzy query technology based. The tech? nology in data cleaning and dissertations TMLC system and spam filtering has important application prospect.

Key words: fuzzy query; n-gram; string segmentation; edit distance; data mining

自從改革開放以來，中國與世界各國的聯系一步一步地加強。這種不斷加強的聯系表現在信息的表達形式上是凸顯的。在日常生活查找信息時，我們很容易看到一些中英文混合使用的表達方式。比如：中國各省人均GDP，windows操作系統，3G手機，3D電影，做CT，ICU病房等。面對這樣一個新形勢的信息爆炸時代，如何從互聯網的海量信息中快速準確地找到我們所需的信息成為一個難題[1]。

在信息爆炸時代里，搜索引擎已經成為千千萬萬網民上網的必備工具。但是隨著信息量的不斷增長，人們在在進行查詢的時候,有可能輸入錯誤的信息（比如錯誤的字母，錯誤的數字，錯誤的同音漢字）。在這些一種情況下,用戶可能就無法得到想要的查詢結果。盡管目前已經有些搜索引擎中加入了“您是否要找***”等類似的功能[2],但這依然無法快速準確的滿足用戶的查詢要求。

因此,如何從海量的中英文數據中查找出與查詢字符串相類似的查詢結果,是該文努力研究的方向。目前，已經有人提出了基于n-gram的字符串分割的算法實現[3]。該算法只針對英文字符串，能解決在英文信息檢索中基于關鍵詞的查詢技術前綴精確匹配問題[4],也就是檢索結果是“錯誤的輸入,錯誤的輸出”,還能解決用戶因記憶模糊或誤輸入單詞中的個別字母,甚至在數據庫中可能存在某些不正確的數據即“臟數據”的這些情況下可能無法得到用戶所期待的查詢結果[5]。已有的算法針對的是英文數據，對中英文這樣的數據束手無策。為此，該文提出一種改進的解決方法,首先對關鍵詞進行中英文識別,然后根據指定長度對字符串進行分割。綜上所述，該文對基于關鍵詞的傳統查詢方法和基于n-gram的字符串分割的算法進行了分析，提出了基于n-gram的中英文字符串分割的算法。

1基于關鍵詞的查詢

1.1傳統的查詢方法

隨著網絡通信的快速發(fā)展,信息爆炸已經成為一個不可避免的趨勢。當人們面對如此巨大的信息量時如何從互聯網的海量信息中快速準確地找到我們所需的信息成為一個難題。此時，搜索引擎已經成為千千萬萬網民上網的必備工具?；ヂ摼W上已有的搜索引擎可分為兩種：目錄式搜索引擎和基于關鍵詞的搜索引擎，后者處于主流地位[6]。基于關鍵詞查詢一般都是精確匹配，其不足之處是：當檢索者因為記憶錯誤或操作錯誤而輸入錯誤查找信息，甚至因為數據庫本來已存有錯誤的信息，而無法找到想要的信息。為此該文對原有算法進行了改進，提出了基于n-gram的中英文字符串分割的算法實現，可對中英文信息實現基于關鍵詞的模糊搜索。

1.2基于n-gram的字符串分割技術的查詢方法

該查詢方法可以避免基于關鍵詞查詢技術的完全匹配的問題。當用戶在操作失誤或記憶不清時輸入有誤的查詢信息時,利用基于n-gram的中英文字符串分割技術的查詢方法，用戶將可以找到自己需要的信息。現將顯示基于關鍵詞查詢的主要流程圖（如圖1）[7]和基于n-gram的字符串分割技術查詢的主要流程圖（如圖2）。

其中，分割后的字符串可通過編輯距離[8]，余弦相似度[9]，Jaccard系數[10]來計算字符串的相似程度，進行數據清洗實現模糊搜素。

現在以基于編輯距離的查詢技術舉例。先定義編輯距離，將子串r1轉換成r2所需要的字符編輯操作(刪除、插入、替換)的次數定義為r1和r2之間的編輯距離，寫作ED(r1,r2)。

比如當我們輸入查詢子串“做CT”且設定檢索出的結果與輸入查詢子串允許一個字符不同(即編輯距離ED = 1)時,那么我們可能得到的結果是“*做CT”、“做*CT”、“做C*T”、“做CT*”、“做*T”、“做C*”,其中*表示可以是空或任意一個英文字符。我們還可以假設編輯距離ED=2，那么我們可能得到的結果是“做**”、“**CT”、“做C**”等結果，其中*表示可以是空或任意一個英文字符，兩個連續(xù)*才可以表示一個漢字。這樣的話,即使用戶在輸入一個錯誤的查詢漢字或英文,或者輸入兩個錯誤的英文查詢子串，或者存儲數據庫中存在的某種程度有錯誤的記錄,也都可以作為查詢結果返回給用戶,而這些記錄很有可能就是用戶所需要的結果。

因此,這種新的查詢技術應用在中英文混合表達的信息中，將幫助人們更加快速準確找到他們所需的結果。而要實現上面所述的這種中英文模糊查詢,首先將整個數據集進行字符串分割,創(chuàng)建倒排索引[11],然后再對用戶輸入的查詢字符串進行字符串分割,最后把分割后的子串與倒排索引中的字符串片段進行模糊匹配[12],將候選結果與輸入字符串按照編輯距離進行匹配后得到最后結果。

可見,中英文字符串的分割技術是中英文信息實現基于關鍵詞的模糊搜索的基礎。

2基于n-gram的中英文字符串分割技術

2.1 n-gram

n-gram[13]的定義: Z是一個字符串。|Z|表示Z的長度, Z[ i]是Z中第i個字母/漢字( i從1開始) , Z[ i, j ]是Z中從第i個到第j個字母/漢字, n是一個整數。

A( Z, n)表示字符串Z中所有的n-gram的集合,如Z = windows操作系統, n = 4,則A( Z, n) = { (1,wind) , (2,indo) , (3,ndow) , (4, dows) , (5,ows操) , (6,ws操作) , (7,s操作系) , (8,操作系統)}。在本算法中，字符串中的數字和空格也將分割，而中文標點符號將剔除處理，不考慮其作為分割的字符。

2.2算法的實現

該算法根據指定的長度和n-gram的規(guī)則進行字符串分割，其流程圖如圖3所示。該算法的主要函數如下：（1）isAChinaFont(參量cn)

這個函數是用來識別輸入的字符是不是中文字符,cn表示輸入的字符。

（2）StringLen_Function(參量cPtr)

這個函數是先調用函數（1）對字符串中的字符進行識別，后統計字符串的字符個數，cPtr表示需要分割字符串。

（3）FormatNum_Function(參量cPtr,參量iSegmentationLen)

這個函數是先調用函數（2）求得源文件中一行字符串的字符個數，后根據分割長度算出該行字符串能分割成幾個字符串片段。cPtr表示需要分割字符串，iSegmentationLen表示分割長度。

（4）GetSegmentationString_Function(參量cPtr,參量iSegmentationLen,參量iFormatNum)

這個函數利用函數（1）（2）從一行字符串中取出我們分割的字符串。cPtr表示需要分割的字符串，iSegmentationLen表示分割長度，iFormatNum表示需要分割第幾個字符。

（5）WriteID_Function(參量fp,參量cPtr,參量iLineNum)

這個函數作用是如果從目標文件查到有一段字符串符合我們分割之后的字符串，我們將ID寫入到這個字符串中。fp表示目標文件，cPtr表示原來的字符串+插入ID =現在這個字符串，iLineNum表示要修改第幾行。

（6）ChechInsert_Function(參量cPtr,參量iSegmentationLen,參量id)

這個函數是用來判斷是否可以插入ID，因為有的分割字符串的ID已經存在于目標文件中，我們就不需要再插入ID。cPtr表示分割好的字符串，iSegmentationLen表示分割長度，id表示行號。

（7）Search_Function(參量Dest_fp,參量cPtr,參量iSegmentationLen,參量id)

這個函數是利用函數（1）（5）（6）查找分割的字符片段在不同行是否有重復，如不重復則寫入到輸出文件；如果在不同行重復則在該行的文本后加上當前的行號輸出；如果在同行重復則不改變原先的輸出。Dest_fp表示目標文件，cPtr表示分割完成的字符串，iSegmentation表示分割長度，id表示行號。

以下是本算法的實現過程：

If源文件存在

打開目標文件，沒有則新建一個

獲取分割長度

識別字符串中的字符，按照指定長度分割

取出一行字符串中分割的字符串片段，并寫入ID存入目標文件（重復字符串片段只保存一次）

利用Search_Function（）函數

Else退出程序

2.3實驗結果與分析

本實驗在運行環(huán)境為Intel(R) Core(TM)2 Duo CPU T5450 @1.66GHZ 1.66GHZ,1.50G內存的Windows XP系統通過對包含不同記錄數的文該文件，設定不同的分割長度進行分割，程序運行時間比較如圖4所示：

說明：橫軸1,2,3分別表示文該文件中的記錄數為10,25,50。

本算法的時間復雜度為（n/2）,其中n表示文件中的記錄數。該算法分割時間與記錄數成線性增長，有較理想的效率。

3結論

隨著信息的爆炸式增長，基于關鍵詞搜索已經不能滿足人們的需求，對模糊搜索的需求越來越迫切。該文提出了基于n-gram的中英文字符串分割算法，不僅僅能滿足英文的字符串分割，還能滿足中文、中英文，以及混有數字的字符串分割，是實現模糊搜索的一項重要技術。該技術的實現除了在模糊搜索有重要的應用，還在學位論文TMLC系統[14]和垃圾郵件過濾[15]也有重要的應用前景。

參考文獻：

[1]周景.淺談互聯網信息檢索[J].信息與電腦:理論版, 2011 (12).

[2]劉竟.近十年我國搜索引擎研究的可視化分析[J].圖書情報研究, 2011(4).

[3]李文.基于n-gram的字符串分割技術的算法實現[J].計算機與現代化, 2010(9).

[4] Kukich K. Techniques for automatically correcting words intext [J]. ACM Comput. Surv. , 1992,24 (4):377-439.

[5] Ji Shengyue,Li Guoliang,Li Chen, et al. Efficient interactive fuzzy keyword search [C] . InternationalWorld Wide Web Conference,2009: 371-380.

[6] Behm Alexander, Ji Shengyue,Li Chen, et al. Space-constrained gram-based indexing for efficient approximate string search[C].ICDE, 2009: 604-615.

[7]沈文婷.數據庫關鍵字查詢清理技術研究[J].電腦知識與技術, 2011(34).

[8] L i C, Lu J, Lu Y. Efficient merging and filtering algorithms for approximate string searches [C] .ICDE,2008:257-266.

[9] Wang J, Li G, Feng J. Fast-join: An efficient method for fuzzy token matching based string similarity join[C] .ICDE, 2011: 458-469.

[10]潘磊.基于權重的Jaccard相似度度量的實體識別方法[J].北京交通大學學報, 2009(6).

[11] Jiannan Wang, Guoliang Li, Jianhua Feng : Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints. [J]. PVLDB 2010 PVLDB 3 (1) :1219-1230.

[12] ChaudhuriS, GantiV, Kaushik R. Aprimitive operator for similarity joins in data cleaning[C] .ICDE,2006.

[13] Wagner R A, FischerM J. The string2to2string correction problem[J]. ACM, 1974, 21 (1) : 168-173.

[14]張旻浩.國內外學術不端文獻檢測系統平臺的比較研究[J].中國科技期刊研究, 2011(4).

[15]常凱.基于TF*IDF垃圾郵件過濾改進算法的研究[J].電腦知識與技術, 2010(25).