一種基于詞樹的高效解碼算法

張志強，張太紅,2，董 巒,3

(1.新疆農業大學 計算機與信息工程學院，新疆 烏魯木齊 830052；2.中國農業大學 信息與電氣工程學院，北京 100083;3.河海大學 計算機與信息工程學院，江蘇 南京 210098)

一種基于詞樹的高效解碼算法

張志強1，張太紅1,2，董 巒1,3

(1.新疆農業大學 計算機與信息工程學院，新疆 烏魯木齊 830052；2.中國農業大學 信息與電氣工程學院，北京 100083;3.河海大學 計算機與信息工程學院，江蘇 南京 210098)

音字轉換是漢語言信息處理的一個重要方面，在語音識別、漢語拼音輸入等方面都有廣泛的應用。為了找到一種行之有效的音字轉換解碼算法，在研究拼音分詞與詞樹理論并分析詞樹求解過程的基礎上，提出了基于語言模型實現音字轉換的高效解碼算法。該算法采用零概率重估、路徑剪枝和多音字處理等多項技術，通過對詞樹進行的剪枝處理、對常用詞的處理以及對解碼過程中所產生多音字的處理，實現了普遍意義上的音字轉換。為驗證所提算法的有效性和可行性，基于新疆維吾爾自治區科技計劃項目《多語種民族特色文化信息資源處理及共享服務平臺》所提供的三組數據進行了對比實驗。實驗結果表明，提出的新算法取得了97.78%的轉換準確率，優于其他傳統算法。

拼音分詞；詞樹；語言模型；n-gram模型；音字轉換

0 引 言

語言模型(Language Model，LM)[1]是語音識別系統(Speech Recognition System，SRS)[2]的一個重要組成部分。語言模型，一般分為以統計為基礎的統計語言模型(Statistical Language Model，SLM)和以規則為基礎的規則語言模型(Rule-based Language Model，RLM)。在現有條件下，SLM處于主流地位，通過對大量語料統計[3]，獲得詞與詞之間的連接信息，為評價一個詞串是否有意義提供依據。

n-gram語言模型是統計語言模型中比較典型的模型[4]，它的結構簡單，易于構建和應用。但是，應用n-gram語言模型時，需要解決訓練語料稀疏而引起的零概率問題[5]。為了解決該問題，提出了一種基于詞樹的音字轉換算法，通過拼音分詞，對詞樹進行搜索和剪枝，對常用詞以及對多音字進行處理。

1 拼音分詞理論

為了提供更為準確的詞特征,在此利用拼音分詞。拼音分詞的任務就是把通過鍵盤輸入的漢語拼音串,切分成拼音詞單元。例如“zhong guo ren min yin hang”可以切分為“zhong guo/ ren min /yin hang”。

拼音分詞采用的是Trigram模型并且采用絕對平滑(Absolute Smoothing)算法。和漢語分詞過程相似,構造的拼音網格如圖1所示。

圖1 拼音分詞網格

拼音分詞就是指在圖1的網格中搜索出最優切分路徑。在Trigram模型中，可尋找滿足式(1)的切分:

(1)

其中，p(pi|pi-2pi-1)表示拼音串中首個拼音詞出現的概率。

和音字轉換相比，漢字到拼音轉換過程比較簡單，所以大規模獲取拼音漢字轉換的語料也較為容易。利用大規模拼音分詞語料單獨訓練拼音分詞模型，同時利用這個模型對音字轉換模型的訓練語料和測試語料進行重新切分。訓練與測試均采用相同的系統處理，這樣可以盡量彌補切分錯誤帶來的影響。

2 詞樹理論

(2)

其中，

(3)

其中，dhz(Sj)表示與S相對應可能漢字的集合。

由于在漢語中存在著許許多多的同音字詞，求解式(2)的過程是在一個比較繁瑣的詞樹上進行的,詞樹的路徑數量因S的不同而不同。例如，當S=“zhong guo ren min yin hang”時，它產生的詞樹可能如圖2所示。

圖2 詞樹

式(2)的求解就是在圖2中找出一條使P(W)最大的路經。

3 求解P(W)的過程

(4)

如果有非常多的語料作保證,那么可以根據最大似然度規則得到：

(5)

實際應用n-gram模型時，n一般取得很小，目前最常用的是n=3，稱3元模型。這時式(4)和式(5)可以分別寫成：

(6)

(7)

P(W1)=C(W1)/N

(8)

(9)

(10)

其中，N為訓練語料總詞數；α、β為兩個經驗數據。實驗表明:α取10-11、β取10-3是一組合適取值。

4 對詞樹的剪枝處理

如果在圖1的詞樹中求解式(2)，隨著音節串S的增長，路徑數目將會迅速膨脹，當音節數目大于10的時候，路徑數目將會達到上千條，如果不增加剪枝技術，時間復雜度和空間復雜度是無法容忍的[13]。利用剪枝技術，把路徑搜索限制在有限的范圍內，是整個算法不可缺少的部分[14]。在上千條路徑中，期望(正確)的路徑只有一條，其他都是多余的，所以理想的剪枝技術應當是：

(1)不會發生錯誤剪枝;

(2)盡量多地剪去不是所期望的路徑[15]。

為了實現剪枝功能，定義如下的數據結構，用來記錄相關信息[16]：

#define ITM 16

struct tab

{

node *point； /*指向葉子節點*/

int d； /*路徑達到拼音串的具體位置*/

float loggl； /*從根到葉的概率乘積的對數值*/

}path [ITM]；

整個搜索算法都包含剪枝技術，描述如下[17]：

(1)path[]對路徑初始化；

(2)生成詞樹的第一層上節點；

(3)從S取出S1～Sl(l最大為4)；

(4)按照可能的詞進行組合,按照1～4字詞的規模生長；

(5)取6條概率較大的路徑并且將它們存入path[],并且先按d進行排序,后按照log_gl進行排序；

(6)進行循環處理；

(7)生長；

(8)從path[]中取出d最小的路徑,并取出Sd～Sd+1(l最大為4)；

(9)按步驟(4)-(5)行算法擴展后一層節點；

(10)剪枝；

(11)對于相同的d,保留概率大的兩條路徑，其他全部剪去；

(12)當第二條的log_gl比第一條小2(小100倍)時，亦剪去；

(13)判結束；

(14)若所有路徑到達t(詞串尾)；

(15)則{期望路徑=argmaxpath[]log_gl;

(16)輸出期望路徑;

(17)轉(20)；

(18)}

(19)否則轉(6)；

(20)結束。

系統任何時候最多保留8條路徑。

5 對常用詞的處理

在不同領域有著不同的常用詞。例如，計算機領域的常用詞如圖3所示。

計算機常用詞中央處理單元、主板、隨機存儲器(內存)、只讀存儲、監視器、鍵盤、鼠標、芯片、光盤驅動器(光驅)、硬盤、軟盤、光盤刻錄機、集線器、調制解調器、即插即用、不間斷電源、基本輸入輸出系統、安裝、卸載、向導、操作系統

圖3 計算機常用詞表

為了提高音字轉換速度，可以建立一個或多個常用詞表。例如對有關計算機的語音進行音字轉換解碼，可以關聯計算機常用詞表。一旦通過前面的解碼處理得到“中央”二字，可以查詢計算機常用詞表，那么“中央處理器”的概率肯定是很大的。通過此方法，在一定程度上可以有效提高解碼的速度。

6 對多音字的處理

漢語中不僅含有大量同音字，而且含有不少多音字[18]，如：“長”，有時念chang(如“長度”)，有時念zhang(如“長大”)；“落”，有時念luo(如“落后”)，有時念“la”(如“落下”)，等等。在音字轉換中，如果不解決這個問題，有時會造成不可逆轉的錯誤，不僅出錯音節所對應的漢字會出錯，而且還會影響前后一大串，從而對整句造成災難性的后果[19]。如：音節串“wo men dou shi zhong guo ren”，得到的正確結果是:“我們都是中國人”。此句第3個音節“dou”是多音字,如果變為“du”，那么由于該音節錯了，破壞了句中相關詞之間的連接關系[20],于是產生如下錯誤結果:“我們毒誓種過任”。

對多音字處理的方法是：在解碼的同時給多音字增加一個候選項。其中，如果把“dou”念成“du”，系統除了按照原來的音節串進行檢索外，還會自動將“du”替換成“dou”再次檢索一遍詞樹，重復檢索的范圍是Si-3～Si+3(i是多音字的下標)。根據從語言模型中詞的先后連接信息所得概率，系統會自動判別應該取“dou”這個讀音，還是取“du”這個讀音，以便獲得正確的結果，所以具有對多音字的容錯能力，實際操作表明，這是一種非常有效的方法。

7 實驗測試

7.1 實驗設備

實驗設備配置見表1。

表1 實驗設備配置表

7.2 詞 庫

詞量有50 000條,0～39號是常用的全角符號,40～50 000號是漢字詞條,長度為1～4字,以2字詞居多。

7.3 語言模型

由2億字的中文語料訓練形成,含有50本電子書、2年的人民日報,內容涵蓋范圍非常廣,包含外交、政治、經濟、文化、民生等眾多領域。

7.4 測試集

新疆維吾爾自治區科技計劃項目《多語種民族特色文化信息資源處理及共享服務平臺》提供的3組數據,共2 000句,內容包含政治、外交、體育、民俗、文化和日常生活等方面。

7.5 測試結果

(1)準確性。

句數:2 000；字數:20 000；錯字:444；準確率:97.78 %。

(2)轉換速度。

4.4字/s,所使用電腦核心部件配置見表2。

表2 核心配置

這個核心配置只能算是計算機的中等配置水平，因此導致計算機的運算速度不夠高，如果提高計算機配置，音字轉換的速度勢必大大提高。

8 結束語

音字轉換包括兩個重要指標：準確率和轉換速度。準確率與零概率重估算法、剪枝技術、多音字處理等因素存在著密切的聯系。在諸多因素中，零概率重估算法是最重要的一項?；谝陨显颍岢隽艘哉Z言模型為基礎的音字轉換算法，并將算法應用于仿真系統。對詞樹進行搜索和剪枝，隨后對常用詞、多音字進行處理，得到的準確率達到97.78%。仿真實驗表明：該算法具有很好的有效性和可行性。引入α、β兩個參數來計算概率并處理零概率事件，使轉換速度達到4.4字/s，滿足了實時處理要求。若能提高計算機性能，則可以達到更為理想的效果。

[1] 陳雅蘭,胡小華,涂新輝,等.基于位置語言模型的中文信息檢索系統的研究[J].計算機科學,2015,42(7):265-269.

[2] Aubert X L.One pass cross word decoding for large vocabularies based on a lexical tree search organization[C]//Proc. of Eurospeech’99.[s.l.]:[s.n.],1999:1559-1562.

[3] 任光輝，茅旭初．多約束條件的全球定位系統單頻單歷元短基線定向技術與實現[J]．上海交通大學學報，2014，48(3):335-340．

[4] 李春生.一種體現長距離依賴關系的語言模型[J].科技視界,2014(5):55-56.

[5] Bacchiani M,Ostendorf M.Joint lexicon,acoustic unit inventory and model design[J].Speech Communication,1999,29(2):99-114.

[6] 艾山·吾買爾,早克熱·卡德爾,買合木提·買買提，等.基于C#的語言模型計算工具[J].電腦知識與技術,2013(33):7590-7592.

[7] Chao Y R.Tone contour[EB/OL].1979.http://en.wikipe-dia.org/wiki/Tone_contour/.

[8] Cremelie N, Martens J P. In search of pronunciation rules[C]//Proceedings of the ESCA tutorial and workshop on modeling pronunciation variations for automatic speech recognition.[s.l.]:[s.n.],1998:23-27.

[9] 何 莉,林鴻飛.分布式檢索中基于主題的語言模型集合選擇策略[J].微電子學與計算機,2009(9):78-81.

[10] 劉海娟,張佳驥,陳 勇.語言模型在話題跟蹤中的應用[J].無線電工程,2008,38(9):20-23.

[11] 姜 維,關 毅,王曉龍,等.基于支持向量機的音字轉換模型[J].中文信息學報,2007,21(2):100-105.

[12] 章 森.基于混合字詞網格的漢語音字轉換問題的求解[J].計算機學報,2007,30(7):1145-1153.

[13] 李明琴,王作英,陸 大.語音識別音字轉換中的快速容錯算法[J].中文信息學報,2002,16(5):38-43.

[14] 張瑞強.關于漢語音字轉換中語言模型零概率的問題[J].電子學報,1998,26(8):43-46.

[15] 趙以寶,孫圣和.一種基于單字統計二元文法的自組詞音字轉換算法[J].電子學報,1998,26(10):55-59.

[16] 章 森,宗成慶,陳肇雄,等.語句拼音-漢字轉換的智能處理機制分析[J].中文信息學報,1998,12(2):37-43.

[17] 梅 勇,王群生,徐秉錚.將詞類信息融入三元文法統計模型的漢語音字轉換方法[J].電子科學學刊,1998,20(5):625-630.

[18] 梅 勇,徐秉錚.一種基于馬爾可夫模型的漢語語音識別后處理中的音字轉換方法[J].中文信息學報,1997,11(4):66-72.

[19] Downey S,Wiseman R.Dynamic and static improvements to lexical baseforms[C]//Proceedings of the workshop on modeling pronunciation variations.[s.l.]:[s.n.],1998:157-162.

[20] 龐春雷，趙修斌，盧艷娥，等．短基線約束條件下的整周模糊度二維搜索算法[J].中國空間科學技術，2012，32(3):43-48．

An Efficient Decoding Algorithm Based on Word Tree

ZHANG Zhi-qiang1，ZHANG Tai-hong1,2，DONG Luan1,3

(1.College of Computer & Information Engineering,Xinjiang Agricultural University,Urumqi 830052,China;2.College of Information and Electrical Engineering,China Agricultural University,Beijing 100083,China;3.College of Computer and Information Engineering,Hohai University,Nanjing 210098,China)

Phonetic conversion is an important aspect of Chinese language information processing,which has been widely used in speech recognition,Chinese Pinyin input and so on.In order to find an effective syllable-to-character decoding algorithm,an efficient decoding algorithm is proposed based on the study of phonetic word segmentation,the word tree theory and the analysis of word tree solving.It uses zero probability reassessment,path pruning,processing of polyphonic words to realize the syllable-to-character conversion generally by pruning of word tree,processing of common words and processing of polyphonic words in the decoding process.In order to verify the validity and feasibility of the proposed algorithm,the contrast experiments on three sets of data provided by Xinjiang Uygur Autonomous Region Science and Technology Program,Multilingual Ethnic Cultural Information Resource Processing and Sharing Service Platform,have been conducted.The experimental results show that it has achieved 97.78% conversion accuracy,which is superior to other traditional algorithms.

phonetic word segmentation;lexicon tree;language model;n-gram model;Pinyin-Chinese character transform

2016-07-26

2016-10-27 網絡出版時間：2017-07-05

新疆維吾爾自治區科技計劃項目(2015X0106)

張志強(1986-)，男，碩士研究生，研究方向為數據庫技術；張太紅，博士，教授，碩士生導師，通訊作者，研究方向為數據庫技術、農業信息化技術。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170705.1650.026.html

TP391.1

A

1673-629X(2017)08-0043-04

10.3969/j.issn.1673-629X.2017.08.009