一種網(wǎng)絡(luò)課程答疑系統(tǒng)分詞器的設(shè)計

李 龍，李麗麗，高 玲

(1.東北石油大學(xué) 計算機與信息技術(shù)學(xué)院，黑龍江 大慶163318;2.大慶油田圖書館，黑龍江大慶163453)

在互聯(lián)網(wǎng)技術(shù)廣泛應(yīng)用的今天，傳統(tǒng)教學(xué)的弊端越來越凸顯。將網(wǎng)絡(luò)技術(shù)應(yīng)用到教學(xué)，不僅能降低學(xué)習(xí)的門檻［1]，還能突破時空的限制［2－5]，提高教學(xué)效果。答疑系統(tǒng)作為網(wǎng)絡(luò)課程幫助學(xué)生解答疑惑的平臺，它替代傳統(tǒng)答疑中教師的角色，直接與學(xué)生交流［6]。根據(jù)該原理，出現(xiàn)了一些基于WEB的答疑系統(tǒng)的研究［7－10]。但是，由于計算機很難真正理解學(xué)生提交的問題的含義，因此問題－解答庫中即使有該問題的答案，也往往找不出來。針對此問題，文獻(xiàn)［11] 提出了對需求進(jìn)行智能化展示的方法，文獻(xiàn)［12] 提出了基于所提問題與題庫問題進(jìn)行相似度計算的辦法，在一定程度上改進(jìn)了答案匹配的效果。相信相似匹配問題庫中的問題和學(xué)生提交的問題切成一個個詞語，然后將切分后的詞語作為最基本的單元，執(zhí)行相應(yīng)的算法。該算法的前提是分詞?，F(xiàn)有的分詞算法可分為3大類［13]，分詞詞典的設(shè)計與查詢算法是一大關(guān)鍵?，F(xiàn)有的分詞詞典設(shè)計方法有［14]:基于整詞二分的分詞詞典機制、基于Trie索引樹的分詞詞典機制［15]、基于逐字二分的分詞詞典機制?；谡~二分的詞典機制速度較慢，基于Trie索引樹的分詞詞典機制，速度較快，但詞典結(jié)構(gòu)復(fù)雜，難以維護(hù)。第3種方法是前兩種機制的折中，匹配效率提高有限，為了最大限度提高匹配效率，本文設(shè)計一種新的分詞詞典和查詢算法，來滿足網(wǎng)絡(luò)課程答疑系統(tǒng)的需要。

1 分詞詞典設(shè)計

1.1 內(nèi)容設(shè)計

對于網(wǎng)絡(luò)課程答疑系統(tǒng)，用戶輸入的語句中非常有可能出現(xiàn)一些頻率較低的專業(yè)單詞，但絕大部分是使用頻率較高的常用單詞。因此，分詞詞典應(yīng)該對應(yīng)包括專業(yè)詞典和基礎(chǔ)詞典兩部分。

1.2 結(jié)構(gòu)設(shè)計

將基礎(chǔ)詞典和專業(yè)詞典中單詞均按拼音排序，則排列后遵循如下:每個詞典中的單詞均按首字不同排列，首字相同的單詞按次字不同排列，次字相同的單詞按第三個字不同進(jìn)行排列，依次類推。于是，首字相同的單詞必定連續(xù)排在一起，首字相同且次字相同的單詞也必定連續(xù)排在一起。因此，考慮采用Hash方法設(shè)計分詞詞典數(shù)據(jù)結(jié)構(gòu)(見圖1)。其中，數(shù)據(jù)區(qū)域采用順序表存儲所有單詞，單詞按拼音排序;索引區(qū)域由一個二維矩陣構(gòu)成，包含特定首字和特定次字在數(shù)據(jù)區(qū)域存儲的起始位置信息，行對應(yīng)首字，列對應(yīng)次字。

Lijo至Lijp是數(shù)據(jù)區(qū)域中首字為第i個字、次字為第j個字的全部單詞。Cij是首字為漢字中第i個字，次字為漢字中第j個字組成的單詞對應(yīng)的索引，其結(jié)構(gòu)形式包括BeginPos和EndPos。

其中，BeginPos指示全部首字為第i個字、次字為第j個字組成的單詞在數(shù)據(jù)區(qū)域中開始存儲位置，EndPos指示在數(shù)據(jù)區(qū)域中結(jié)束存儲位置。

1.3 索引矩陣確定

由于索引矩陣每一維均關(guān)聯(lián)所有的漢字，因此它應(yīng)該是一個方陣，且每一維的長度為漢字的個數(shù)。漢字的具體個數(shù)目前尚不清楚，一種說法是90 000多個，而《信息交換用漢字編碼字符集基本集》GB2312－80中收錄漢字6 763個，以此為標(biāo)準(zhǔn)構(gòu)造分詞詞典，可以取索引矩陣為6 763*6 763的方陣。

在《信息交換用漢字編碼字符集基本集》中，每個漢字均唯一對應(yīng)一個內(nèi)碼。而根據(jù)轉(zhuǎn)換公式:內(nèi)碼高位=區(qū)碼+A0H(H為十六進(jìn)制)，內(nèi)碼低位=位碼+A0H，可以很容易計算出一個漢字的區(qū)位碼，再將區(qū)位碼轉(zhuǎn)換為十進(jìn)制，即將最終得到的十進(jìn)制數(shù)字作為該漢字在矩陣中的下標(biāo)。用單詞首字內(nèi)碼轉(zhuǎn)換得到的十進(jìn)制數(shù)作為它在索引矩陣中第一維的下標(biāo)，用次字內(nèi)碼轉(zhuǎn)換得到的十進(jìn)制數(shù)作為它在索引矩陣中第二維的下標(biāo)。

2 查詢算法設(shè)計

由于語句中常用單詞出現(xiàn)的概率，遠(yuǎn)比專業(yè)單詞出現(xiàn)的概率大，因此，在分詞詞典中搜索時，應(yīng)該先搜索基礎(chǔ)詞典，后搜索專業(yè)詞典，如果在基礎(chǔ)詞典中搜索出單詞，則不繼續(xù)搜索專業(yè)詞典。

2.1 算法描述

無論是專業(yè)詞典，還是基礎(chǔ)詞典，均采用如下算法進(jìn)行搜索。

定義首子串:對于漢字字符串T的長度不小于S的長度，若T和S從第一個字符一直到S的最后一個字符都相同，則稱S是T的首子串。

算法描述:設(shè)輸入字符串 T=(a1a2…ai…an)，其中 n為字符串的長度(n＞1)，ai(i=1，2，…，n)表示字符串T的第i個字符。

計算漢字a1的內(nèi)碼i，計算漢字a2的內(nèi)碼j，獲得詞典索引矩陣中的第i行第j列的元素Cij。

如果Cij的第一個字段BeginPos的值≠－1，進(jìn)入(3)，否則說明詞典中不存在單詞(a1)，將(a1)加入到臨時集合M中，進(jìn)入(5)。

如果Cij的第二個字段EndPos的值≠－1，令k=Beginpos，進(jìn)入(4)，否則說明詞典中存在(a1)這個單詞，但不存在(a1a2)這個單詞，將(a1)加入到臨時集合M中，進(jìn)入(5)。

如果L［k] 是T的首子串，則字符串T中包含單詞 L［k] ，將 L［k] 加入到臨時集合 M 中，k=k+1 200。若k＞EndPos，則轉(zhuǎn)至(6)，否則轉(zhuǎn)至(4)

將M中長度最大的詞語作為搜索結(jié)果，結(jié)束搜索。

3 實驗結(jié)果與分析

用VS.NET 2005實現(xiàn)了兩個中文分詞器。一個是采用基于整詞二分的分詞詞典機制，另一個是采用上述方法。詞典中的詞條采用《漢語寶典》中的全部詞語，并在Pentium 43.0，1 024M內(nèi)存的情況下，進(jìn)行了實驗，實驗結(jié)果如表1。

表1 系統(tǒng)測試結(jié)果Tab.1 System test results

從實驗結(jié)果看，詞典結(jié)構(gòu)及相應(yīng)查詢機制對單詞查詢時間有很大影響。不采用索引逐字匹配，速度將會很慢。二者時間比為:186 455/752≈247.94

從理論上，二者時間相差的應(yīng)該更多，本文的方法應(yīng)該更快。

《漢語寶典》共收錄雙字詞語381 290條，收錄漢字20 973個［6]。采用整詞二分法查找一個特定的多字詞，從第一個單詞到最后一個單詞依次進(jìn)行比較，假設(shè)每個單字出現(xiàn)的概率相等，則查找首字需要比較的次數(shù)為而平均包含特定首字的詞語有381 290/20 973≈18個，即查找該首字之后不同的次字平均要比較18次。因此，查找首字和次字平均需要比較190 645.5+18=190 663.5次。采用本文詞典結(jié)構(gòu)和搜索方法，查找某特定詞語的首字和次字只需要計算漢字內(nèi)碼2次。二者查詢次數(shù)比為:90 663.5/2=95 331.75。

可以看出，理論時間比為95 331.75，實際時間比為247.94。通過分析程序，得知兩種算法都需要加載詞庫，加載詞庫需要耗費大量時間，該時間是算作總時間之內(nèi)的，因此實際時間比減小了。

4 結(jié)束語

本文所給出的一種新的詞典設(shè)計方法和查詢算法，大大降低了算法的時間復(fù)雜度。但算法的實際運行時間并沒有如時間復(fù)雜度預(yù)計減少的那么多，但可以研究詞庫加載算法，進(jìn)一步提高詞語的實際查詢速度。

［1] 胡青松，張 申.通用網(wǎng)絡(luò)輔助教學(xué)支撐平臺的研制［J] .電氣電子教學(xué)學(xué)報，2008(03):74－76.

［2] 張 瑋.基于網(wǎng)絡(luò)交互的學(xué)習(xí)共同體研究［J] .軟件導(dǎo)刊(教育技術(shù))，2011(09):25 －28.

［3] 桑新民.現(xiàn)在教育技術(shù)學(xué)基礎(chǔ)理論創(chuàng)新研究［J] .中國電化教育，2003(9):56－59.

［4] 韓海英.基于網(wǎng)絡(luò)化教學(xué)環(huán)境的教師角色重塑［J] .教育革新，2009(01):21－22.

［5] 姜大仲，王新秀，崔善珠.發(fā)展終身學(xué)習(xí)型城市網(wǎng)絡(luò)的戰(zhàn)略［J] .高等函授學(xué)報:哲學(xué)社會科學(xué)版，2011(05):3－6.

［6] 武法提.網(wǎng)絡(luò)教育應(yīng)用［M] .北京:高等教育出版社，2003.

［7] 姜良華.網(wǎng)絡(luò)輔助答疑系統(tǒng)的設(shè)計與實現(xiàn)［J] .電腦知識與技術(shù)，2011(26):6451－6452.

［8] 方光偉.基于Web的課程自動答疑系統(tǒng)的設(shè)計與實現(xiàn)［J] .科技信息，2011(16):197－198.

［9] 王 薇，朱 鳳，李 歡.基于Web的課程答疑系統(tǒng)的研究［J] .中國成人教育，2008(22):159－160.

［10] 蔡冠群，張業(yè)睿，袁曉斌.構(gòu)筑基于Web的遠(yuǎn)程答疑系統(tǒng)［J] .信息技術(shù)教育，2006(03):75－76.

［11] 朱云霞，周海峰.基于WEB的智能答疑系統(tǒng)的研究與設(shè)計［J] .科技信息，2009(01):413－414.

［12] 康文寧，楊志強.相似度計算在智能答疑系統(tǒng)中的研究及應(yīng)用［J] .計算機技術(shù)與發(fā)展，2010(2):71－74.

［13] 文庭孝.漢語自動分詞研究進(jìn)展.圖書情報［J] ，2005(5):54－62.

［14] YOU C H，KOH S N，RAHARDJA S.An invertible frequency eigendomain transformation for maskingbased subspace speech enhancement［J] .IEEE Signal Processing Letters，2005，12(6):461 －464.

［15] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)［M] .北京:清華大學(xué)出版社，2003.