一種網絡課程答疑系統分詞器的設計

李 龍，李麗麗，高 玲

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

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

1 分詞詞典設計

1.1 內容設計

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

1.2 結構設計

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

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

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

1.3 索引矩陣確定

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

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

2 查詢算法設計

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

2.1 算法描述

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

定義首子串:對于漢字字符串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實現了兩個中文分詞器。一個是采用基于整詞二分的分詞詞典機制，另一個是采用上述方法。詞典中的詞條采用《漢語寶典》中的全部詞語，并在Pentium 43.0，1 024M內存的情況下，進行了實驗，實驗結果如表1。

表1 系統測試結果Tab.1 System test results

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

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

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

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

4 結束語

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

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

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

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

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

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

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

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

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

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

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

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

［12] 康文寧，楊志強.相似度計算在智能答疑系統中的研究及應用［J] .計算機技術與發展，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] 嚴蔚敏，吳偉民.數據結構(C語言版)［M] .北京:清華大學出版社，2003.