一種基于組合ash索引的分詞機(jī)制

0分詞方式的選擇中國(guó)的自動(dòng)分詞是中文信息處理的前提，在中文信息處理的各個(gè)領(lǐng)域得到了廣泛應(yīng)用。由于漢語(yǔ)書面語(yǔ)不像西方文字那樣詞與詞之間有特定的分隔標(biāo)記,而是連續(xù)的漢字串,如何自動(dòng)識(shí)別詞邊界,將漢字串切分為正確詞串的漢語(yǔ)自動(dòng)分詞問(wèn)題無(wú)疑是實(shí)現(xiàn)中文信息處理中各項(xiàng)任務(wù)的首要問(wèn)題。因此,漢語(yǔ)分詞的任務(wù)就是將句子中的詞自動(dòng)切分出來(lái),即通過(guò)計(jì)算機(jī)程序識(shí)別出句子中的詞,并用分詞標(biāo)志符號(hào)分隔開。從計(jì)算機(jī)處理過(guò)程上看,分詞系統(tǒng)的輸入是連續(xù)的字符串(C1C2C3C4……Cn),輸出是漢語(yǔ)的詞串(W1W2W3……Wm)。這里,Wi可以是單字詞也可以是多字詞。目前對(duì)漢語(yǔ)分詞方法的研究主要有三個(gè)方面,一是基于詞表的分詞,這是一種有著廣泛應(yīng)用的機(jī)械分詞方法,該方法依據(jù)一個(gè)分詞詞表和一個(gè)基本的切分評(píng)估原則,即“長(zhǎng)詞優(yōu)先”原則來(lái)進(jìn)行分詞。這種切分方法,需要最少的語(yǔ)言資源,程序?qū)崿F(xiàn)簡(jiǎn)單,開發(fā)周期短,是一個(gè)簡(jiǎn)單實(shí)用的方法。二是基于統(tǒng)計(jì)語(yǔ)言模型(SLM)的分詞,該方法首先切分出與詞表匹配的所有可能的詞,這種切分方法稱為“全切分”,運(yùn)用統(tǒng)計(jì)語(yǔ)言模型和決策算法決定最優(yōu)的切分結(jié)果。這類方法的優(yōu)點(diǎn)是可以發(fā)現(xiàn)所有的切分歧義,但是解決歧義的方法很大程度上取決于統(tǒng)計(jì)語(yǔ)言模型的精度和決策算法,需要大量的標(biāo)注語(yǔ)料,并且分詞速度也因搜索空間的增大而有所緩慢。三是基于人工智能技術(shù)的分詞,分詞過(guò)程是對(duì)人腦思維方式的模擬,試圖用數(shù)字模型來(lái)逼近人們對(duì)語(yǔ)言認(rèn)識(shí)的過(guò)程,理論上是最理想的分詞方法。由于漢語(yǔ)自然語(yǔ)言復(fù)雜靈活,知識(shí)表示困難,基于人工智能的中文自動(dòng)分詞技術(shù)還處于起步階段。根據(jù)具體應(yīng)用領(lǐng)域的不同需求,分詞系統(tǒng)常在分詞精度和速度上做出選擇,要提高速度,就要適當(dāng)放棄精度的追求,縮減詞典,減少匹配次數(shù)。而要提高切分精度,就得舍棄速度,無(wú)限擴(kuò)充詞典,匹配次數(shù)也會(huì)無(wú)限增加。本文研究的出發(fā)點(diǎn)在于保持基于詞典的現(xiàn)有分詞精度上,提高分詞的速度,在第1節(jié)介紹幾種基于詞典的常用中文自動(dòng)分詞算法,第2節(jié)提出了一種新的分詞詞典機(jī)制并設(shè)計(jì)出相應(yīng)的分詞算法——組合Hash索引分詞算法,第3節(jié)給出對(duì)比實(shí)驗(yàn)結(jié)果,第4節(jié)是結(jié)束語(yǔ)。1基于字典的分詞算法的總結(jié)1.1配合算法dmm最大匹配算法(MaximumMatchingMethod,簡(jiǎn)稱MM法)是一種廣泛應(yīng)用的機(jī)械分詞方法,按其匹配的方向分為正向最大匹配法(MMB)和逆向最大匹配(RMMB)。該算法的基本思想是:事先給定一個(gè)最大可能詞的長(zhǎng)度MAX,分詞時(shí)首先取出長(zhǎng)度為MAX的待分詞的漢字串S,若該字串與詞庫(kù)中的詞匹配成功,則該字串是詞,否則按正向或逆向取MAX-1的子串繼續(xù)進(jìn)行匹配,直到子串為空。最大匹配算法通常采用整詞二分的匹配策略,因此有詞典構(gòu)造簡(jiǎn)單,易于實(shí)現(xiàn)等特點(diǎn),但其MAX值需事先確定,若MAX設(shè)置過(guò)大,造成大量無(wú)用的匹配過(guò)程,若MAX過(guò)小,則無(wú)法覆蓋所有可能長(zhǎng)度的詞。算法依托的詞典主要由兩部分組成,首字散列表和正文詞典。結(jié)構(gòu)如圖1所示:1.2根控制至中心基于TRIE索引樹的逐字匹配算法可以避免上述算法中最大詞長(zhǎng)的缺點(diǎn),通常該算法是建立在樹型詞典機(jī)制上,匹配的過(guò)程是從索引樹的根結(jié)點(diǎn)依次同步匹配待查詞中的每個(gè)字,可以看成是對(duì)樹某一分枝的遍歷。因此,采用該算法的分詞速度優(yōu)于上一種方法,但樹的構(gòu)造和維護(hù)比較復(fù)雜。詞典結(jié)構(gòu)主要有兩部分:根結(jié)點(diǎn)和其余結(jié)點(diǎn)。根結(jié)點(diǎn)是一個(gè)首字散列表,同整詞二分中的首字散列表類似,唯一的區(qū)別是指針域少了一個(gè),只含首項(xiàng)入口指針,用來(lái)指明所有次字的入口地址;其余結(jié)點(diǎn)由許多有序的TRIE索引樹結(jié)點(diǎn)組成,如圖2所示:1.3最大匹配實(shí)驗(yàn)詞典逐字二分匹配算法是前兩種算法的結(jié)合,它吸取最大匹配算法詞典結(jié)構(gòu)簡(jiǎn)單、TRIE索引樹算法查詢速度快的優(yōu)點(diǎn)。因此詞典結(jié)構(gòu)和最大匹配詞典構(gòu)造機(jī)制相似,區(qū)別在于詞典正文前增加了多級(jí)索引。匹配過(guò)程類似TRIE索引樹進(jìn)行逐字匹配,在性能上和TRIE索引樹相近。另外,在文獻(xiàn)中提出的雙字哈希算法,結(jié)合了整詞二分,TRIE索引樹的優(yōu)點(diǎn),通過(guò)二級(jí)哈希索引表實(shí)現(xiàn)逐字匹配,降低了詞典組織的復(fù)雜度,提高了分詞的速度,但哈希表的構(gòu)建過(guò)程和維護(hù)仍然比較復(fù)雜。2組合hish索引分詞算法,現(xiàn)代分詞算法中常用的分詞算法分詞設(shè)計(jì)三從上一節(jié)的介紹可以看出TRIE索引樹的詞典機(jī)制有較好的查詞效率,但數(shù)據(jù)結(jié)構(gòu)比較復(fù)雜,樹的構(gòu)造和維護(hù)比較繁瑣,為了最大限度提高匹配的時(shí)間效率,簡(jiǎn)化詞典構(gòu)造難度,以下提出一種新的分詞詞典機(jī)制,并設(shè)計(jì)出相應(yīng)的分詞算法——組合Hash索引分詞算法。2.1索引表的構(gòu)造Hash算法通過(guò)散列函數(shù)直接確定數(shù)據(jù)項(xiàng)的位置,在理想狀況下,查找操作的運(yùn)行時(shí)間可以達(dá)到常數(shù)時(shí)間的目標(biāo)。其性能的優(yōu)劣取決于選擇合適的散列函數(shù),常用的散列函數(shù)有相除散列法、平方取中散列法、相乘散列法等。然而,這幾種散列函數(shù)通常是以整數(shù)值作為關(guān)鍵字,在本文中,關(guān)鍵字是漢字字符串,因此須要設(shè)計(jì)以漢字字符串為關(guān)鍵字的散列函數(shù)。在索引表的構(gòu)造過(guò)程中,采用了.NET內(nèi)置的Hashtable類,Hashtable由包含集合元素的存儲(chǔ)桶組成。存儲(chǔ)桶是Hashtable中各元素的虛擬子組,與大多數(shù)集合中進(jìn)行的搜索和檢索相比,它可令搜索和檢索更簡(jiǎn)單、更快速。每一存儲(chǔ)桶都與一個(gè)哈希代碼關(guān)聯(lián),該哈希代碼是使用哈希函數(shù)生成的并基于該元素的鍵。當(dāng)把某個(gè)元素添加到Hashtable時(shí),將根據(jù)鍵的哈希代碼將該元素放入存儲(chǔ)桶中。該鍵的后續(xù)查找將使用鍵的哈希代碼只在一個(gè)特定存儲(chǔ)桶中搜索,這將大大減少為查找一個(gè)元素所需的鍵的比較次數(shù)。2.2定義及數(shù)據(jù)結(jié)構(gòu)根據(jù)學(xué)者的統(tǒng)計(jì),一字詞和二字詞的出現(xiàn)頻率約占總詞數(shù)的94%,三字以上約占6%。若以字串的前兩字為關(guān)鍵字建立Hash索引表,多數(shù)詞用一次匹配就能切分出來(lái),在前兩字確定的情況下,用二分法查找剩余字的平均匹配次數(shù)小于2次,根據(jù)這樣的特點(diǎn),我們?cè)趫D2的基礎(chǔ)上把詞典聚合成兩個(gè)部分,由圖2中的部分合并生成以詞前兩字為關(guān)鍵字的Hash索引表,由圖2中部分合并生成一維結(jié)點(diǎn)數(shù)組。如圖3所示。為了敘述的方便,首先給出定義:定義:給定字串a(chǎn)0a1a2a3a4……an,ai表示第i個(gè)字符,稱為第i字,a0至ai-1間的字符被稱為ai的前綴字符,ai-1是ai的第一前綴,ai-2是ai的第二前綴,依此類推;ai+1至an間的字符被稱為ai的后綴字符,ai+1是ai的第一后綴,ai+2是ai的第二后綴,依此類推。主要數(shù)據(jù)結(jié)構(gòu):1)Hash索引結(jié)點(diǎn)①關(guān)鍵字:由二字以上詞的首字和次字組合而成,如“中國(guó)”、“中國(guó)菜”、“中國(guó)畫”、“中國(guó)人”、“中國(guó)人民”的索引結(jié)點(diǎn)關(guān)鍵字是“中國(guó)”。關(guān)鍵字是唯一的。②詞標(biāo)志:標(biāo)志關(guān)鍵字是否是詞,-1表示非詞,0表示是詞。③第三字首指針:指明以關(guān)鍵字為前綴的所有第三字在剩余結(jié)點(diǎn)數(shù)組中的索引起始位置,當(dāng)值為-1時(shí)表示關(guān)鍵字沒(méi)有后綴。④第三字尾指針:指明以關(guān)鍵字為前綴的所有第三字在剩余結(jié)點(diǎn)數(shù)組中的索引結(jié)束位置。2)剩余字串?dāng)?shù)組結(jié)點(diǎn):①關(guān)鍵字:去除詞前兩字的其它字,如“中國(guó)菜”,關(guān)鍵字是“菜”。②詞標(biāo)志:當(dāng)值為-1時(shí)表示非詞,當(dāng)值i>=1時(shí)表示是詞且關(guān)鍵字是詞中的第i個(gè)字符。③第一后綴首指針:指明以當(dāng)前關(guān)鍵字為第一前綴的所有字首索引位置,當(dāng)值等于-1時(shí)表示到達(dá)詞尾。④第一后綴尾指針:指明以當(dāng)前關(guān)鍵字為第一前綴的所有字尾索引位置。2.3查詢strtem的方法輸入:連續(xù)的字符串Str=c1c2c3……cn,N是字符串長(zhǎng)度。輸出:是漢語(yǔ)的詞串W=(w1w2w3……wk),K是詞個(gè)數(shù)。變量說(shuō)明:intT:查詢指針,指向新詞的識(shí)別的起始位置,初始值為0;intM:移動(dòng)指針,指向待匹配字位置,初始值為T;intWordFlag:表示到第幾個(gè)字成詞;intStart:后綴入口指針;intEnd:后綴尾指針;stringSubstr:從待查詞中截取的子串。算法描述:(1)若查詢指針T小于N,反復(fù)執(zhí)行以下過(guò)程;(2)初始化WordFlag為1,移動(dòng)指針M為T;(3)若入口指針為-1,返回長(zhǎng)度為WordFlag的詞到W中,增加分詞標(biāo)記,查詢指針T向后移動(dòng)m,跳(2);(4)每次以M為基準(zhǔn)起點(diǎn)取長(zhǎng)度為1的子串strtem,strtem追加到Substr中;(5)若M=T,判斷strtem是否為非漢字編碼,識(shí)別長(zhǎng)度為L(zhǎng)的英文詞、數(shù)字、和標(biāo)點(diǎn)符號(hào)等非漢字字符,查詢指針下移L,跳(2);(6)否則若M=T+1,在hash索引表中查詢strtem,若匹配成功,返回后綴首尾指針Start、End,WordFlag置為2,跳(8);(7)若M>T+1,在(Start,End)之間進(jìn)行二分查詢,跳(8);(8)二分查詢成功,得到下一后綴的入口指針和尾指針,若詞標(biāo)志不為-1,詞標(biāo)志賦予WordFlag,否則二分查詢失敗,返回長(zhǎng)度為WordFlag的詞到W中,增加分詞標(biāo)記,查詢指針向后移動(dòng)WordFlag步,跳(2);(9)返回W,查詢結(jié)束。詞匹配示例:如對(duì)“中國(guó)人民從此站起來(lái)了”進(jìn)行分詞。假定查詢指針已指向“中”的位置。1)取字串“中國(guó)”作為關(guān)鍵詞進(jìn)行Hash匹配,匹配成功,返回第一后綴首尾指針Start,End。2)取字串“人”作為關(guān)鍵字,在剩余字串結(jié)點(diǎn)數(shù)組的Start到End范圍內(nèi)進(jìn)行快速二分查找,匹配成功,返回第二后綴首尾指針Start,End。3)取字串“民”作為關(guān)鍵字,在剩余字串結(jié)點(diǎn)數(shù)組的Start,End索引范圍內(nèi)進(jìn)行二分快速匹配,匹配成功,首尾指針等于-1,查詢結(jié)束,返回“中國(guó)人民”。4)查詢指針指向“從”的位置,取字串“從此”作為關(guān)鍵字進(jìn)行Hash匹配,匹配成功,返回第一后綴首尾指針Start,End。5)取字串“站”作為關(guān)鍵字,在剩余字串結(jié)點(diǎn)數(shù)組的Start到End范圍內(nèi)進(jìn)行快速二分查找,匹配失敗?！皬拇恕笔窃~,返回“從此”。6)查詢指針指向“站”的位置,取字串“站起”作為關(guān)鍵字進(jìn)行Hash匹配,匹配成功,返回第一后綴首尾指針Start,End。7)取字串“來(lái)”作為關(guān)鍵字,在剩余字串結(jié)點(diǎn)數(shù)組的Start到End范圍內(nèi)進(jìn)行快速二分查找,匹配成功,返回第二后綴首尾指針Start,End。8)取字串“了”作為關(guān)鍵字,在剩余字串結(jié)點(diǎn)數(shù)組的Start,End索引范圍內(nèi)進(jìn)行二分快速匹配,匹配失敗,“站起來(lái)”是詞,返回“站起來(lái)”。9)查詢指針指向“了”的位置,未切分子串長(zhǎng)度不足2,返回“了“,分詞結(jié)束。從詞典的結(jié)構(gòu)及上面的示例中可以看出,詞典的Hash索引表關(guān)鍵字是詞的第一字和第二字。匹配過(guò)程的第一次比較便截取字串的前兩個(gè)字符進(jìn)行hash匹配,匹配不成功說(shuō)明是單字詞或者是非漢字字符,匹配成功說(shuō)明是多字詞,若返回的指針域不為-1,再在剩余字串結(jié)點(diǎn)數(shù)組的相應(yīng)索引范圍內(nèi)用快速二分法進(jìn)行第三字以上的匹配查找。3實(shí)驗(yàn)分析3.1et技術(shù)構(gòu)建分詞系統(tǒng)是在Windows2000操作系統(tǒng)平臺(tái)下,基于.Net技術(shù)構(gòu)建,詞典詞條數(shù)21,8252條。我們從2000年《人民日?qǐng)?bào)》中隨機(jī)選取了2個(gè)文本,分別進(jìn)行了整詞二分、TRIE索引樹算法、組合Hash索引分詞算法的對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)數(shù)據(jù)見表1:3.2總結(jié)點(diǎn)長(zhǎng)度和匹配次數(shù)一字詞的匹配次數(shù):hash索引表匹配不成功時(shí)表示關(guān)鍵字的第一字是一字詞,因此匹配次數(shù)為1。二字詞以上的匹配次數(shù)分兩種情況:①無(wú)后綴:此時(shí)hash索引表匹配成功,匹配次數(shù)為1。②有后綴:平均匹配次數(shù)按公式(1)計(jì)算n+1n1b(n+1)?1(1)n+1n1b(n+1)-1(1)Hash表總結(jié)點(diǎn)長(zhǎng)度為142557個(gè),其中有后綴結(jié)點(diǎn)92532個(gè),兩字有后綴的平均寬度為0.649,代入(1)式,第三字的平均匹配次數(shù)為0.834;第四字總長(zhǎng)度為42348,平均寬度0.457,第四字平均匹配次數(shù)為0.565;四字以上總長(zhǎng)度2170,平均寬度0.051,二分查找四字以上詞的平均匹配次數(shù)為0.041。理論分析表明,切分2字以上詞的平均匹配次數(shù)少于文獻(xiàn)的1.56、1.66各1.08。從實(shí)驗(yàn)的結(jié)果可以看出,在時(shí)間性能上,基于TRIE索引樹和組合Hash索引的分詞算法比整詞二分算法時(shí)間效率上有顯著提高,組合Hash索引分詞算法的處理速度較整詞二分平均提高了13.8倍,較TRIE索引樹平均提高了2.7倍,并且詞典的數(shù)據(jù)結(jié)構(gòu)比TRIE索引