張志強(qiáng)，張?zhí)t,2，董 巒,3

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

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

張志強(qiáng)1，張?zhí)t1,2，董 巒1,3

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

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

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

0 引 言

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

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

1 拼音分詞理論

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

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

圖1 拼音分詞網(wǎng)格

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

(1)

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

和音字轉(zhuǎn)換相比，漢字到拼音轉(zhuǎn)換過程比較簡(jiǎn)單，所以大規(guī)模獲取拼音漢字轉(zhuǎn)換的語料也較為容易。利用大規(guī)模拼音分詞語料單獨(dú)訓(xùn)練拼音分詞模型，同時(shí)利用這個(gè)模型對(duì)音字轉(zhuǎn)換模型的訓(xùn)練語料和測(cè)試語料進(jìn)行重新切分。訓(xùn)練與測(cè)試均采用相同的系統(tǒng)處理，這樣可以盡量彌補(bǔ)切分錯(cuò)誤帶來的影響。

2 詞樹理論

(2)

其中，

(3)

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

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

圖2 詞樹

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

3 求解P(W)的過程

(4)

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

(5)

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

(6)

(7)

P(W1)=C(W1)/N

(8)

(9)

(10)

其中，N為訓(xùn)練語料總詞數(shù)；α、β為兩個(gè)經(jīng)驗(yàn)數(shù)據(jù)。實(shí)驗(yàn)表明:α取10-11、β取10-3是一組合適取值。

4 對(duì)詞樹的剪枝處理

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

(1)不會(huì)發(fā)生錯(cuò)誤剪枝;

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

為了實(shí)現(xiàn)剪枝功能，定義如下的數(shù)據(jù)結(jié)構(gòu)，用來記錄相關(guān)信息[16]：

#define ITM 16

struct tab

{

node *point； /*指向葉子節(jié)點(diǎn)*/

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

float loggl； /*從根到葉的概率乘積的對(duì)數(shù)值*/

}path [ITM]；

整個(gè)搜索算法都包含剪枝技術(shù)，描述如下[17]：

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

(2)生成詞樹的第一層上節(jié)點(diǎn)；

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

(4)按照可能的詞進(jìn)行組合,按照1～4字詞的規(guī)模生長(zhǎng)；

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

(6)進(jìn)行循環(huán)處理；

(7)生長(zhǎng)；

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

(9)按步驟(4)-(5)行算法擴(kuò)展后一層節(jié)點(diǎn)；

(10)剪枝；

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

(12)當(dāng)?shù)诙l的log_gl比第一條小2(小100倍)時(shí)，亦剪去；

(13)判結(jié)束；

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

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

(16)輸出期望路徑;

(17)轉(zhuǎn)(20)；

(18)}

(19)否則轉(zhuǎn)(6)；

(20)結(jié)束。

系統(tǒng)任何時(shí)候最多保留8條路徑。

5 對(duì)常用詞的處理

在不同領(lǐng)域有著不同的常用詞。例如，計(jì)算機(jī)領(lǐng)域的常用詞如圖3所示。

計(jì)算機(jī)常用詞中央處理單元、主板、隨機(jī)存儲(chǔ)器(內(nèi)存)、只讀存儲(chǔ)、監(jiān)視器、鍵盤、鼠標(biāo)、芯片、光盤驅(qū)動(dòng)器(光驅(qū))、硬盤、軟盤、光盤刻錄機(jī)、集線器、調(diào)制解調(diào)器、即插即用、不間斷電源、基本輸入輸出系統(tǒng)、安裝、卸載、向?qū)?、操作系統(tǒng)

圖3 計(jì)算機(jī)常用詞表

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

6 對(duì)多音字的處理

漢語中不僅含有大量同音字，而且含有不少多音字[18]，如：“長(zhǎng)”，有時(shí)念chang(如“長(zhǎng)度”)，有時(shí)念zhang(如“長(zhǎng)大”)；“落”，有時(shí)念luo(如“落后”)，有時(shí)念“l(fā)a”(如“落下”)，等等。在音字轉(zhuǎn)換中，如果不解決這個(gè)問題，有時(shí)會(huì)造成不可逆轉(zhuǎn)的錯(cuò)誤，不僅出錯(cuò)音節(jié)所對(duì)應(yīng)的漢字會(huì)出錯(cuò)，而且還會(huì)影響前后一大串，從而對(duì)整句造成災(zāi)難性的后果[19]。如：音節(jié)串“wo men dou shi zhong guo ren”，得到的正確結(jié)果是:“我們都是中國人”。此句第3個(gè)音節(jié)“dou”是多音字,如果變?yōu)椤癲u”，那么由于該音節(jié)錯(cuò)了，破壞了句中相關(guān)詞之間的連接關(guān)系[20],于是產(chǎn)生如下錯(cuò)誤結(jié)果:“我們毒誓種過任”。

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

7 實(shí)驗(yàn)測(cè)試

7.1 實(shí)驗(yàn)設(shè)備

實(shí)驗(yàn)設(shè)備配置見表1。

表1 實(shí)驗(yàn)設(shè)備配置表

7.2 詞 庫

詞量有50 000條,0～39號(hào)是常用的全角符號(hào),40～50 000號(hào)是漢字詞條,長(zhǎng)度為1～4字,以2字詞居多。

7.3 語言模型

由2億字的中文語料訓(xùn)練形成,含有50本電子書、2年的人民日?qǐng)?bào),內(nèi)容涵蓋范圍非常廣,包含外交、政治、經(jīng)濟(jì)、文化、民生等眾多領(lǐng)域。

7.4 測(cè)試集

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

7.5 測(cè)試結(jié)果

(1)準(zhǔn)確性。

句數(shù):2 000；字?jǐn)?shù):20 000；錯(cuò)字:444；準(zhǔn)確率:97.78 %。

(2)轉(zhuǎn)換速度。

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

表2 核心配置

這個(gè)核心配置只能算是計(jì)算機(jī)的中等配置水平，因此導(dǎo)致計(jì)算機(jī)的運(yùn)算速度不夠高，如果提高計(jì)算機(jī)配置，音字轉(zhuǎn)換的速度勢(shì)必大大提高。

8 結(jié)束語

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

[1] 陳雅蘭,胡小華,涂新輝,等.基于位置語言模型的中文信息檢索系統(tǒng)的研究[J].計(jì)算機(jī)科學(xué),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] 任光輝，茅旭初．多約束條件的全球定位系統(tǒng)單頻單歷元短基線定向技術(shù)與實(shí)現(xiàn)[J]．上海交通大學(xué)學(xué)報(bào)，2014，48(3):335-340．

[4] 李春生.一種體現(xiàn)長(zhǎng)距離依賴關(guān)系的語言模型[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ì)算工具[J].電腦知識(shí)與技術(shù),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].微電子學(xué)與計(jì)算機(jī),2009(9):78-81.

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

[11] 姜 維,關(guān) 毅,王曉龍,等.基于支持向量機(jī)的音字轉(zhuǎn)換模型[J].中文信息學(xué)報(bào),2007,21(2):100-105.

[12] 章 森.基于混合字詞網(wǎng)格的漢語音字轉(zhuǎn)換問題的求解[J].計(jì)算機(jī)學(xué)報(bào),2007,30(7):1145-1153.

[13] 李明琴,王作英,陸 大.語音識(shí)別音字轉(zhuǎn)換中的快速容錯(cuò)算法[J].中文信息學(xué)報(bào),2002,16(5):38-43.

[14] 張瑞強(qiáng).關(guān)于漢語音字轉(zhuǎn)換中語言模型零概率的問題[J].電子學(xué)報(bào),1998,26(8):43-46.

[15] 趙以寶,孫圣和.一種基于單字統(tǒng)計(jì)二元文法的自組詞音字轉(zhuǎn)換算法[J].電子學(xué)報(bào),1998,26(10):55-59.

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

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

[18] 梅 勇,徐秉錚.一種基于馬爾可夫模型的漢語語音識(shí)別后處理中的音字轉(zhuǎn)換方法[J].中文信息學(xué)報(bào),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].中國空間科學(xué)技術(shù)，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 網(wǎng)絡(luò)出版時(shí)間：2017-07-05

新疆維吾爾自治區(qū)科技計(jì)劃項(xiàng)目(2015X0106)

張志強(qiáng)(1986-)，男，碩士研究生，研究方向?yàn)閿?shù)據(jù)庫技術(shù)；張?zhí)t，博士，教授，碩士生導(dǎo)師，通訊作者，研究方向?yàn)閿?shù)據(jù)庫技術(shù)、農(nóng)業(yè)信息化技術(shù)。

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