□ 徐碩 喬曉東 朱禮軍 張運良/中國科學技術信息研究所 北京 100038

薛春香/南京理工大學經濟管理學院 南京 210094

廣義后綴樹及其在漢語科技詞系統(tǒng)中的應用研究

□ 徐碩 喬曉東 朱禮軍 張運良/中國科學技術信息研究所 北京 100038

薛春香/南京理工大學經濟管理學院 南京 210094

科技詞匯知識是科技信息智能處理的基石，如何加速漢語科技詞系統(tǒng)的構建是目前研究的熱點問題之一?？紤]到中文術語構詞的特點，文章引入了一種靈活的數據結構——廣義后綴樹，從字面的角度提出了關系輔助構建、任務分配以及輸入提示等輔助工具，使得知識工程師的工作更加高效。

廣義后綴樹，漢語科技詞系統(tǒng)，關系構建，任務分配，輸入提示

1 引言

科技詞匯知識是科技信息智能處理的基石，長期以來，以科技類主題詞表為代表的科技詞匯知識體系存在著編制過程中知識丟失、維護機制落后、詞更新周期長、開放程度不夠、非面向機器使用等突出問題，難以滿足信息加工和軟件開發(fā)需求。為應對這一問題，07年在國家“十一五”科技支撐計劃課題資助下，中國科學技術信息研究所組織開展了漢語科技詞系統(tǒng)的研究和開發(fā)工作，并以新能源汽車領域為試點，進行了新能源汽車詞系統(tǒng)建設實踐，詳見文獻[1,2]或直接訪問詞系統(tǒng)管理加工平臺：http:// www.vocgrid.org/。

與英文不同，中文構詞有其自身的特點，陸汝占教授認為漢語是義符文字，詞語結構與意義以名詞為中心，構造方式為毗連組合，直接對應概念耦合，實體類分類由實體本質屬性標識[3]。比如對于圖1[3]中各種面包、糕餅和甜食的中英文表達，從字面上看英文表達幾乎沒有任何的相似性，但對中文表達就不同了，大部分都含有“面包”這兩個字，也就是說中文術語從字面上傳遞了很多有用信息。正因如此，本文主要從字面的角度討論漢語科技詞系統(tǒng)內容的輔助構建方法。

圖1 各種面包、糕餅和甜食中英文表達

2 廣義后綴樹簡介

盡管后綴樹概念的提出獨立于TRIE的概念，但為了更容易理解后綴樹，讓我們首先來解釋一下TRIE樹[4]?！癟RIE”這個單詞來自于“retrieval”，TRIE樹是一個簡單但實用的數據結構，通常用于實現字典查詢。TRIE樹的每條分支代表一則子串，樹的葉節(jié)點代表完整的字符串，和普通樹不同之處在于相同的字符串前綴共享同一條分支。

為敘述方便，首先給出后綴的定義。給定長度為n的字符串S=S1S2…Si…Sn#（#號表達字符串的結束），和整數i（1≤ i≤n），子串S[i: n]= SiSi+1…Sn#稱為字符串S的后綴，一般將空字符串（記為#）也算其后綴，通常稱子串S[i: n]為起始位置為i的后綴。后綴樹實際上是包含字符串所有后綴的壓縮TRIE樹[5]。

后綴樹是針對一個字符串構建的，而廣義后綴樹[5,6]是針對一個字符串集合構建的。比如在表1所示的字符串集合上構建的廣義后綴樹如圖2[6]所示。為了區(qū)分方便，表1中為每個字符串添加了一個不同的特殊字符#i，在廣義后綴樹的實際構建中只需一個特殊字符即可。

圖2 表1所示字符串集合上構建的廣義后綴樹

表1 8個字符串示例

構建后綴樹的第一個線性時間算法是由Weiner[7]于1973年提出的，另外一個不同但空間效率更高的算法是由McCreight[8]于1976年提出的。幾乎在20年之后，Ukkonen[9]給出了一個概念上完全不同的線性時間構建算法，該算法允許后綴樹的在線構建，而且更容易理解。盡管Ukkonen和McCreight的算法在高層組織上差別很大，但二者的聯(lián)系被Giegerich和 Kurtz[10]詳細解釋。

3 廣義后綴樹在漢語科技詞系統(tǒng)中的應用研究

本節(jié)主要考慮如何借助廣義后綴樹，輔助知識工程師完成詞系統(tǒng)中知識單元的構建。

3.1 關系輔助發(fā)現

根據中文術語構詞特點，從字面的角度發(fā)現語義關系通常需要對術語列表進行排序，比如前端一致的正/倒排序，或后端一致的正/倒排序。但該方法只能發(fā)現具有共同前綴或共同后綴的術語間語義關系，對于“能源”與“新能源汽車”間的語義關系并不能發(fā)現，本小節(jié)提出的方法可發(fā)現具有共同子串的術語間語義關系，只要子串定義得當。

表2 10條新能源汽車領域術語示例

假設我們有一部收詞粒度通常比較細的詞典D，本節(jié)參考文獻[11-13]，首先給出幾個定義。語義知識庫中存在的詞匯為原子術語（Primitive Term，PT）；詞典D中不存在，但可由兩個或更多原子術語組合而成的詞匯稱為組合術語（Combined Term，CT）；原子術語與組合術語統(tǒng)稱為術語（Term）。

嚴格來說，就是給定一部詞典D = {PT1, PT2, …, PTK}，則D中每個元素都是一個原子術語，而符合下式定義的詞匯CT為組合術語：

CT=PTi1PTi2…PTin,CT∈D，PTij∈D，j=1,2,…,n, n≥2(3-1)

對于任意一個組合術語CT，由于構成它的原子術語的位置是確定的，因此每個組合術語都可以表示為一個由原子術語構成的字符串，即

CT=＜PTi1，PTi2，…，PTin＞.(3-2)

為一致起見，原子術語PT也可類似地表示為＜PT＞。表2給出了10條新能源汽車領域術語，并且將每條術語均表示成了原子術語構成的字符串，在這些字符串的基礎上，按照前文所述方法可構建如圖3所示的廣義后綴樹。

從圖3可以看出，含有原子術語“燃料”的術語ID集合{1, 3, 4, 5, 6}全部位于以節(jié)點1為根節(jié)點的子樹下，而含有“燃料汽車”的術語ID集合{3, 4, 5, 6}全部位于以節(jié)點2為根節(jié)點的子樹下。這樣只要深度優(yōu)先（DFS）遍歷圖3所示的廣義后綴樹，即可得到術語間的上下位關系、相關關系等。我們針對新能源汽車領域的術語已經構建了廣義后綴樹，并輸出了所有的遍歷結構給知識工程師，表3為部分結果展示。表3中每個區(qū)的開始為幾個術語所共同包含的原子術語子串，以及包含這個原子術語子串的術語數量，比如包含原子術語子串“動力電動汽車”的術語共有5條，其ID及相應的術語逐個列于其后。

3.2 任務分配

為了加快詞系統(tǒng)內容的協(xié)同構建，通常需要為每個用戶分配不同的加工任務。對任務的劃分通常有五種方式：按范圍分、按字順分、按關系類型分、按詞族分以及按分面分等。但如果構建圖3所示的廣義后綴樹，還可按原子術語進行任務劃分。比如可以將含有原子術語“燃料”的術語ID集合{1, 3, 4, 5, 6}分配給一個用戶來完成。

表3 新能源汽車領域術語的廣義后綴樹部分遍歷結果

3.3 輸入提示

在許多實際應用中，為了改善用戶體驗，提高用戶完成各種任務的速度，經常需要根據用戶的輸入給出一定的提示。比如我們在搜索引擎中輸入“新能”時，Google和百度通常會給出以“新能”為前綴的幾個用戶關鍵詞提示，分別見圖4中（a）和（b）。這一方面可以加快用戶的輸入速度，另一方面也可對那些不太清楚自己輸入什么關鍵詞的用戶起到提示的目的。然而，Google和百度提供的輸入提示，只能提示只輸入字符串為前綴的術語集合。如果用戶希望查找“完全混合動力系統(tǒng)”，但他/她記不清全稱了，可能只記得“混合動力系統(tǒng)”或“動力系統(tǒng)”，那么Google和百度的輸入提示就顯得有點蒼白無力了。

考慮表4所示的術語集合，此時原子術語為單個的漢字，它的廣義后綴樹如圖5所示。每個內部節(jié)點包括三個數組，分別用于記錄相應字符串出現于術語首部、中間及尾部的術語集合。比如節(jié)點1，字符串“燃料”出現在首部的術語ID集合為{1, 4}，出現在尾部的術語ID集合為{1}，出現在中間的術語ID集合為{}。有了這三個數組，我們就可以很輕松地完成各種輸入提示了。

4 結論

考慮到中文術語構詞的特點，本文主要從字面的角度考慮如何輔助漢語科技詞系統(tǒng)內容的構建。具體來說，通過引入了一種靈活的數據結構——廣義后綴樹，從字面的角度提出了關系輔助構建、任務分配以及輸入提示等輔助工具，使得知識工程師的工作更加高效。

圖3 表2所示術語集合的廣義后綴樹

圖4 輸入提示的成功案例

表4 5條新能源汽車領域術語示例

圖5 表4所示術語集合的廣義后綴樹

[1]朱禮軍,喬曉東,張運良.漢語科技詞系統(tǒng)建設實踐——以新能源汽車領域為例[J].情報學報,2010,29(4):723-731.

[2]喬曉東,張運良,朱禮軍.漢語科技詞系統(tǒng)建設與應用進展[J].情報學報,2010,29(5):978-986.

[3]陸汝占.關于漢語語義概念的一點思考[M]//朱小健,張全,陳小盟.HNC與語言學研究(第4輯),北京:北京師范大學出版社.

[4]KNUTH D E. The Art of Computer Programming. vol. 3, Sorting and Searching [M]. Addison-Wesley, 1972.

[5]GUSFIELD D. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology [M]. USA: Cambridge University Press, 1997.

[6]XU S, QIAO X-D, ZHU L-J, et al. Deep Analysis on Mining Frequent & Maximal Reference Sequences with Generalized Suffix Tree [J]. Journal of Computational Information Systems, 2010, 6(7): 2187-2197.

[7]WEINER P. Linear Pattern Matching Algorithms [C]// Proceedings of the 14th Annual Symposium on Switching and Automata Theory, 1973: 1-11.

[8]MCCREIGHT E M. A Space-Economical Suffix Tree Construction Algorithm [J]. Journal of the ACM, 1976, 23(2): 262-272.

[9]UKKONEN E. On-line Construction of Suffix Trees [J]. Algorithmica, 1995, 14(3): 249-260.

[10]GIEGERICH R, KURTZ S. From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction [J]. Algorithmica, 1997, 19(3): 331-353.

[11]夏天.漢語詞語語義相似度計算研究[J].計算機工程,2007,33(6):191-194.

[12]王文榮.詞匯知識系統(tǒng)動態(tài)構建方法研究與工具實現[D].中國科學技術信息研究所,2008:58-75.

[13]徐碩,朱禮軍,喬曉東,等.基于雙序列比對的中文術語語義相似度計算的新方法[J].情報學報,2010,29(4):701-708.

Generalized Suffix Trees with Its Applications in Chinese Scientific Technical Vocabulary System

Xu Shuo, Qiao Xiaodong, Zhu Lijun, Zhang Yunliang/Institute of Scientific and Technical Information of China, Beijing, 100038
Xue Chunxiang/Nanjing University of Science and Technology, School of Economics and Management, Nanjing, 210094

The scientific and technical words are basis of the scientific and technical information processing. Currently, there are extensive attentions on how to speed up constructing the Chinese scientific and technical vocabulary system. Due to the characteristics of word formation for Chinese terms, a flexible data structure, generalized suffix tree, is introduced. Based on the generalized suffix tree, the paper proposes some assistant tools for relationship construction, task allocation, input prompt, and so on from the viewpoint of literal meaning, which enables knowledge engineers to be much more efficient.

Generalized suffix tree, Chinese Scientific and Technical Vocabulary System, Relationship construction, Task allocation, Input prompt

10.3772/j.issn.1673—2286.2013.04.005

徐碩（1979-），男，博士，中國科學技術信息研究所信息技術支持中心副研究員。研究方向：數據挖掘、信息抽取、生物信息等。E-mail: xush@istic. ac.cn

喬曉東（1965-），男，研究員，碩士生導師，中國科學技術信息研究所總工程師，中國互聯(lián)網協(xié)會理事，中國情報學會計算機應用分會副主任委員，CILIP會員，研究方向：為信息資源管理工作和信息服務。E-mail: qiaox@istic.ac.cn

朱禮軍（1973-），男，研究員，碩士生導師，中國科學技術信息研究所信息技術支持中心副主任。研究方向：Semantic Web、Web Service和知識技術在科技信息服務、電子政務/商務中的應用以及知識組織系統(tǒng)的集成與服務體系。E-mail: zhulj@istic.ac.cn

張運良（1979-），男，博士，中國科學技術信息研究所信息技術支持中心副研究員。研究方向：文本自動分類，概念層次網絡，知識組織。E-mail: zhangyl@istic.ac.cn

薛春香（1979-），女，博士，南京理工大學經濟管理學院副教授。研究方向：智能信息組織，知識組織系統(tǒng)構建。E-mail: xuechunxiang@gmail.com

2012-11-01 ）