李 龍，李麗麗，高 玲

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

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

1 分詞詞典設計

1.1 內容設計

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

1.2 結構設計

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

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

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

1.3 索引矩陣確定

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

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

2 查詢算法設計

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

2.1 算法描述

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

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

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

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

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

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

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

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

3 實驗結果與分析

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

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

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

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

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

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

4 結束語

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

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

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

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

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

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

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

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

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

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

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

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

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

［13] 文庭孝.漢語自動分詞研究進展.圖書情報［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] 嚴蔚敏，吳偉民.數(shù)據(jù)結構(C語言版)［M] .北京:清華大學出版社，2003.