1997年11月
大 連 理 工 大 學 學 報
Journa l of Da l ian Un ivers ity of Technology
Vol. 37, NO. 6
Nov. 1 9 9 7
壹種機器翻譯系統用詞典的設計及其結構
X
黃德根 簡幼良 蒙家玉
( 大連理工大學計算機科學與工程系 116024 )
摘要 提出了機器翻譯系統的詞典設計目標, 討論了大型動態詞典文件的
組織方法. 根據漢語詞分布不均勻的特點, 提出壹種擴充的B+ 樹索引詞典
文件結構, 並給出該詞典的查詢算法及詞典結構的評估. 實踐證明該詞典
結構達到了機器翻譯系統的要求, 其結構是合理的.
關鍵詞: 人工智能; 信息處理?詞典結構; 機器翻譯; 電子詞典
在機器翻譯系統中, 詞典占據極其重要的地位. 機器翻譯的各個過程, 從自動分詞、語法
分析、語義分析到譯語生成等均需要頻繁地訪問詞典. 詞典結構及詞條中所包含的信息量直
接影響整個機器翻譯系統的效率. 詞典的組織既要考慮到漢語分詞, 又要照顧到分析與生
成; 既要考慮節省空間, 又要照顧系統的運行速度. 因此, 詞典的設計對機器翻譯系統至關
重要, 越來越受到人們的重視〔1、2〕. 本文闡述壹種面向機器翻譯系統的詞典設計及其結構.
1 設計目標
詞典是壹種特定類型的數據庫; 與壹般數據庫文件相似, 詞典的組織與設計必須針對實
際系統的要求, 采取相應的文件組織方法. 在制定詞典的組織結構時, 著重考慮了如下幾個
問題.
1. 1 詞條信息豐富、數據項不定長
考慮到詞典必須為機器翻譯的各個過程所利用, 在詞典中收錄了如下信息: 詞法信息、
語法信息、概念信息、***起關系及譯語信息等. 其中只有詞法信息和概念信息為定長字段, 其
他均為不定長字段. 另外, 壹個單詞可能有多種詞性, 每種詞性下又可能有多個概念屬性.
壹個單詞下的所有詞性的內容都包括在同壹詞條中.
詞條內的信息結構如圖1所示. 其中, 記錄的關鍵字由單詞的漢字內碼組成, 如果單詞長
小於固定長度時, 不足部分填入空格; 基本信息由單詞的頻度信息、詞法信息組成, 二者以固
定長度存儲. 品詞屬性為變長字段, 存儲了該品詞下所有的語法信息、概念分類信息、***起信
圖1 詞條信息結構
息及相應的譯語; 如果壹個單詞有多個品詞屬性
時, 品詞之間通過指針連接在壹起, 指針為- 1表
示該品詞屬性為最後壹個節點.
1. 2 大規模動態特性
包括兩方面的內容: 壹是要求詞典具有較大
的容量, 能容納至少6萬條單詞, 並能擴充到10萬
條左右. 由於每條詞所包含的信息從幾十個字節
到數百個字節不等, 存儲詞典信息的空間至少為
幾兆字節, 信息量較大. 二是要求詞典具有動態
修改特性; 詞典生成後, 在操作中可“動態地”進行維護, 即根據用戶的需要, 可對詞典進行
插入、刪除、修改操作.
1. 3 快速查詢
查詢算法和存儲介質是制約詞典訪問速度的兩個主要因素, 其中查詢算法決定了單詞的
查找速度; 而存儲介質決定數據的存取時間. 在算法確定情況下, 若能改變詞典的存儲介質,
將詞典存放到速度較快的介質上, 則可縮短數據存取時間, 提高詞典的查詢速度.
壹般來說, 詞典數據文件連同索引文件壹起存放在外存上, 每次查詞典時要訪問若幹次
外存; 盡管外存的存取速度已經有很大提高, 但速度仍以毫秒為單位, 遠遠低於以納秒為單
位的內存存取速度. 在系統運行時, 若能將外存上的詞典文件壹次全部裝入內存, 則查詢時
訪問外存的次數為零, 詞典的速度就能得到很大提高. 因此, 設計中還要考慮目錄區和數據
區空間的比例, 以使詞典大小控制在合理的範圍內, 便於實現詞典常駐內存.
2 詞典的索引結構
大型動態數據文件壹般采用B+ 樹結構〔3〕, 但是, 完全的B+ 樹結構具有級數太多、索引區
大、空間利用率低的缺點. 為此, 本詞典采用壹種變形的B+ 樹索引文件結構: (1) 樹的級數
限制在3級. (2) 根結點至少有2個孩子. (3) 樹中所有葉子都在同壹級上. (4) 每個結點擁有
的孩子數沒有限制. 其具體實現是: 將整個詞典數據區劃分成許多定長的數據塊(1 024字
節) , 對應每個數據塊有唯壹的塊號, 數據塊中的單詞按詞條內碼的增序順序存放. 索引區采
用分類技術, 分成主、次兩級索引, 其中主索引以表示漢字區間的單漢字為關鍵字, 將單詞按
區間分成若幹大類, 大類中的所有詞條其首字均在同壹漢字區間內; 次索引以數據塊中最後
壹個詞條的內碼為關鍵字, 記錄單詞所在的塊號.
在主索引中, 詞條內碼有如下順序關系:
大類1詞條的首字< 大類2詞條的首字< ?< 大類n 詞條的首字
詞典的索引邏輯結構見圖2. 主索引和次索引中的目錄項均按漢字內碼的增序順序排列,
每個大類(主索引的壹個目錄項) 中含有若幹個數據塊, 塊的個數由區間內包含的詞條數而
定. 在具體實現時, 先掃描整個文本詞典文件, 對單詞總數及首字相同的詞條進行統計; 在
分類數固定的情況下, 計算出每壹分類區間的起始漢字內碼和終止漢字內碼, 使各分類區間
內的詞條數相近.
第6期 黃德根等: 壹種機器翻譯系統用詞典的設計及其結構715
圖2 詞典索引結構
3 查找算法及詞典結構的評估
3. 1 查找算法
基於上述結構的詞典, 其查找算法可描述如下. 其中, K 代表詞條的漢字內碼, S 為詞
條首字內碼.
(1) 根據S 值, 訪問主索引, 查找單詞K 所屬的分類區間, 獲得相應的次索引指針P 及
該分類區間內包含的數據塊個數.
(2) 以指向次索引的指針P , 訪問詞典的次索引, 按二分法查找單詞K 所在的具體塊號
B.
(3) 若塊B 已經讀入內存, 則轉到(4) ; 否則, 根據塊大小及塊號B 計算塊的磁盤物理地
址(即文件指針= 數據區起始地址+ 塊號B ×塊大小) , 將整個數據塊壹次讀入內存.
(4) 對塊內詞條按順序查詢, 若塊內有詞條K , 則查找成功, 返回相應的單詞信息; 若查
找失敗, 返回空信息, 表示該詞典中沒有詞條K.
3. 2 詞典結構的評估
3. 2. 1 空間效率 本詞典實際登錄的漢語詞有6萬余條, 且詞條信息不定長, 最長可達1 024
字節(即整個數據塊為壹條詞) , 生成程序最後統計得到的詞典信息總量為4 819 352字節, 平
均每條約占80字節. 實際生成的二進制詞典文件將整個詞典分成20個大類, ***5 883個數據
塊; 詞典實際大小為6 083 102字節. 詞典各部分占用的空間為: 主索引占80字節(20×4) , 次
索引占58 830字節(5 883×10) , 數據塊占6 024 192字節(5 883×1 024). 其中, 實際數據塊所
占用的空間比詞典信息所需的磁盤空間多出1 204 840字節, 是為方便詞典擴充, 沒有將數據
塊填滿, 預留出20% 的空間作為登錄新單詞使用的緣故.
兩級索引目錄區僅用58 910字節的磁盤空間, 約占詞典信息總量的1. 18% , 小於80×86
中壹個數據段所允許的最大空間(64 KB) , 可以將其放到內存中去, 減少訪問磁盤的次數, 提
高查詢速度. 而采用壹級索引、對半檢索的詞典結構, 即使按最長單詞為4個字計算, 其索引
區也要占60 000×(4×2+ 4) = 720 000字節. 其中, 壹條單詞占壹個目錄項, 每個目錄項由表
示單詞漢字內碼的關鍵字(4×2字節) 和文件指針(4字節的長整型數) 組成. 可見, 完全采用
索引方式的詞典, 索引區占用空間很大, 不適合常駐內存.
716 大連理工大學學報 第37卷
3. 2. 2 算法復雜度 考慮壹般情況, 設詞典有N 條單詞, 分成M 個分類區間, 每個數據塊
平均可存放L 條單詞, 則每類平均有N ?M 條單詞、需要N ?(M ×L ) 個數據塊. 對任壹詞條
K , 訪問主索引區的平均查找次數為進行M ?2 次整型數的比較, 相當於比較了M ?8 次單詞
( 設詞長為4個漢字) , 訪問次索引區的平均次數為log2 (N ?M ) , 因此確定單詞K 所在數據塊
的平均查找次數為M ?8+ log2 (N ?M ). 由於主、次索引區常駐內存, 訪問索引區是在內存中
進行的, 實際所需時間很少.
按上述詞典規模: N = 60 000, M = 20, 查找存放單詞K 的數據塊平均需要進行14次內
存字符串的比較. 另外, 由數據塊號到獲得單詞K 所有義項信息最多需要訪問外存1次, 平
均進行4次字符串比較(塊內查詢). 因此, 查找壹詞條信息最多需要訪問1次外存(可能為0
次) , 平均需要進行18次字符串(8字節長) 比較.
3. 2. 3 可維護性 對詞典進行更新操作會引起詞典數據發生變化, 並可能引發大量的磁盤
文件操作. 在本詞典中, 數據以塊為單位存儲. 當刪除壹條單詞時, 只需將單詞從所屬的數
據塊中刪除, 之後將該數據塊重新寫入數據區; 既不會發生磁盤數據的大量移動, 也不會引
起索引區的變更. 當登錄新詞時, 若數據塊有足夠的空間, 則登錄操作僅在數據塊內進行;
若數據塊沒有剩余空間, 則進行塊分裂, 將原來的塊壹分為二, 前壹塊仍存放在原來的位置,
後壹塊需重新申請壹個數據塊空間, 並分配塊號, 放在數據區末尾, 相應地, 在索引區插入
壹個索引項. 由此可見, 無論是刪除操作, 還是登錄新單詞, 均不會引起數據的大量移動, 對
詞典的更新都是在局部範圍內進行, 讀寫磁盤各為1次.
4 結束語
詞典是機器翻譯中的重要組成部分. 實際設計中既要考慮合理的空間開銷, 又要考慮詞
典數據的訪問速度; 二者很難兼顧. 本文用統計方法對漢語詞進行分類, 克服了壹般Hash 方
法中由於漢語詞分布不均勻所引起的壹系列問題. 如數據塊的負載相差很大, 容易導致數據
塊溢出; 當發生溢出時, 訪問磁盤的次數增加, 降低了詞典的訪問速度等. 索引區和數據區
的大小比例協調, 空間利用率高, 為實現整個詞典裝入內存創造了條件. 從分詞階段的實際
效果來看, 詞典常駐內存後, 其分詞速度提高了10倍以上, 大大提高了整個機器翻譯系統的
效率.
Lex icon des ign and organ iza t ion of dict ionary of
mach ine tran sla t ion system
Huang Degen, J ian You liang, M eng J iayu
( Dep t. of Comput. Sci. and Eng. , Dalian U niv. of Techno l. , Ch ina )
Abstract The design goals of dict ionary u sed in m ach ine t ran slat ion system are p ropo sed.
The o rgan izat ion m ethod of large2scale dynam ic dict ionary f ile is discu ssed too. A cco rding to
the featu re of Ch inese wo rds’ non2equal dist ribu t ion, the paper p resen t s a k ind of st ructu re
of dict ionary based on ex tended b inary t ree index and a search algo rithm. F inally, the au2
tho rs summ arize the eff iciency of the dict ionary st ructu re.
Key Words: art if icial in telligence; info rm at ion p rocess? lex icon o rgan izat ion; m ach ine
t ran slat ion; elect ron ic dict ionary