李 龍，李麗麗，高 玲

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

1 分詞詞典設(shè)計(jì)

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

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

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

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

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

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

1.3 索引矩陣確定

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

在《信息交換用漢字編碼字符集基本集》中，每個(gè)漢字均唯一對(duì)應(yīng)一個(gè)內(nèi)碼。而根據(jù)轉(zhuǎn)換公式:內(nèi)碼高位=區(qū)碼+A0H(H為十六進(jìn)制)，內(nèi)碼低位=位碼+A0H，可以很容易計(jì)算出一個(gè)漢字的區(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è)計(jì)

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

2.1 算法描述

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

4 結(jié)束語

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

［1] 胡青松，張 申.通用網(wǎng)絡(luò)輔助教學(xué)支撐平臺(tái)的研制［J] .電氣電子教學(xué)學(xué)報(bào)，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é)報(bào):哲學(xué)社會(huì)科學(xué)版，2011(05):3－6.

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

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

［8] 方光偉.基于Web的課程自動(dòng)答疑系統(tǒng)的設(shè)計(jì)與實(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ì)［J] .科技信息，2009(01):413－414.

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

［13] 文庭孝.漢語自動(dòng)分詞研究進(jìn)展.圖書情報(bào)［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.