陳書雨 曹集翔 姚寒冰

摘? 要： 分析基于詞表的最大匹配分詞算法，針對(duì)其缺陷設(shè)計(jì)了一個(gè)附近字表，內(nèi)容為高頻字在詞表中出現(xiàn)的左邊首字和右邊首字。設(shè)計(jì)的算法根據(jù)高頻詞的特點(diǎn)，將句子盡可能多的分成段，然后將段進(jìn)行最大匹配。當(dāng)發(fā)現(xiàn)句子中高頻詞時(shí)，只取句子中高頻詞的左邊首字和右邊首字在附近字表中查找；若未找到，則表示句子中此高頻字單獨(dú)成詞，無需在詞表中匹配，從而減少高頻字單獨(dú)成詞時(shí)的匹配時(shí)間，進(jìn)而減少整個(gè)分詞過程的時(shí)間。通過實(shí)驗(yàn)證明此技術(shù)能提高中文分詞的效率。

關(guān)鍵詞： 高頻詞； 預(yù)處理； 中文分詞

中圖分類號(hào)：TP391? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：1006-8228（2023）05-123-04

Pre-treatment technology for Chinese word segmentation

Chen Shuyu1， Cao Jixiang2， Yao Hanbing2

（1. Centre for Multidisciplinary and Intercultural Inquiry， University College London， London W55RF， UK;

2. School of Compute Science and Artificial Intelligence， Wuhan University of Technology）

Abstract： In this paper， we analyze the maximum matching word segmentation algorithm based on the word-list， and design a nearby character-list based on the high-frequency-words pre-treatment technology to improve the efficiency of Chinese word segmentation. In the proposed algorithm， the sentence is divided into many segments based on the characteristics of high-frequency-words， and then the maximum matching is carried out by searching for part of high-frequency-words in the nearby character-list. Using the algorithm reduces the matching time with the vocabulary in the whole word segmentation process. The experimental data prove that the technology will improve the Chinese word segmentation efficiency.

Key words： high-frequency-words; pre-treatment; Chinese word segmentation

0 引言

隨著自然語言處理的發(fā)展，分詞作為基礎(chǔ)任務(wù)成為研究重點(diǎn)，中文因其復(fù)雜性和特殊性成為分詞熱點(diǎn)話題。中國(guó)知網(wǎng)和Web of Science的相關(guān)論文顯示，自2010年分詞研究達(dá)到小高峰后，中文分詞研究熱度再次緩步增長(zhǎng)。作為自然語言處理的基礎(chǔ)任務(wù)，分詞究竟有沒有必要，Li等在2019年ACL會(huì)議上提出此觀點(diǎn)，并在機(jī)器翻譯、文本分類、句子匹配和語言建模4個(gè)NLP任務(wù)上驗(yàn)證分詞的非必要性，但這并不說明分詞研究不再有意義[1]。詞級(jí)別模型欠佳表現(xiàn)在數(shù)據(jù)稀疏、過擬合、OOV以及數(shù)據(jù)遷移能力缺乏等方面，要解決此類問題，提高分詞性能仍有重大意義。由于詞是最小的能夠獨(dú)立運(yùn)用的語言單位，而漢語文本不像西方的書面語言，其詞與詞之間沒有任何空格之類的顯式標(biāo)志指示詞的邊界，因此漢語的自動(dòng)分詞問題就成了計(jì)算機(jī)處理漢語時(shí)的首要基礎(chǔ)工作，涉及自動(dòng)翻譯、文本檢索、語音識(shí)別、文本校對(duì)及搜索等領(lǐng)域，是諸多應(yīng)用系統(tǒng)不可或缺的一個(gè)重要環(huán)節(jié)[2]。

1 中文分詞的現(xiàn)狀

分詞就是將連續(xù)的字符串或序列按照一定規(guī)范重新組合成詞序列的過程。目前，已經(jīng)有很多成熟的漢語分詞技術(shù)。鄒海山等在現(xiàn)有分詞技術(shù)的基礎(chǔ)上提出一種基于詞典的正向最大匹配和逆向最大匹配相結(jié)合的漢語分詞方案，可以高效、準(zhǔn)確地實(shí)現(xiàn)中文文檔的主題詞條抽取和詞頻統(tǒng)計(jì)；應(yīng)志偉等基于一個(gè)實(shí)際的文語轉(zhuǎn)換系統(tǒng)，改進(jìn)最大匹配算法，從實(shí)用角度解決多音字的異讀問題和中文姓名自動(dòng)識(shí)別問題；歐振猛、余順爭(zhēng)采用基于自動(dòng)建立詞庫(kù)的最佳匹配方法進(jìn)行中文分詞[3]。

分詞方法的性能可以從準(zhǔn)確性、高效性、通用性和適用性等幾個(gè)方面來衡量。但考慮到分詞算法的應(yīng)用領(lǐng)域大多對(duì)實(shí)時(shí)性和準(zhǔn)確性兩方面有很高的要求，因此，實(shí)現(xiàn)較簡(jiǎn)單的機(jī)械式分詞法中的正向最大匹配法仍然是應(yīng)用最為廣泛的一種方法。

吳育良在百度中文分詞技術(shù)淺析一文中提出百度分詞使用的就是正向最大匹配法的推測(cè)[4]；而中科院軟件所的張俊林在百度分詞算法分析一文中提出百度分詞采用的是雙向最大匹配算法（即正向最大匹配和反向最大匹配相結(jié)合）的推測(cè)，同時(shí)提到Google采用的是正向最大匹配分詞算法。下面就首先介紹正向最大匹配算法的基本原理，然后介紹本文中提高效率的預(yù)處理技術(shù)。

2 正向最大匹配算法基本原理

正向最大匹配算法的切分原理是：①將文本內(nèi)容按標(biāo)點(diǎn)符號(hào)分成句子集。②對(duì)于句子集中每一句子，假定詞典中最大詞長(zhǎng)為L(zhǎng)，對(duì)于待切分的句子，從句首取長(zhǎng)度為L(zhǎng)的字串進(jìn)行匹配，如果匹配成功則認(rèn)為此字串為一個(gè)詞，再?gòu)南乱粋€(gè)字開始繼續(xù)該過程；如果匹配不成功，則去掉此字串的最后一個(gè)字進(jìn)行匹配，直至匹配成功或子句為空。例如：對(duì)于文本中的字串ABCD，其中AB∈W，ABC∈W，ABCD[?]W，那么切分結(jié)果為：ABC/D。

3 高頻詞的預(yù)處理技術(shù)及算法設(shè)計(jì)

本算法與常用的基于詞典的最大匹配算法不同之處在于：在文本按標(biāo)點(diǎn)符號(hào)及段落切成若干小段過后，先進(jìn)行高頻詞的匹配，而此匹配不同于最大匹配算法，詞典的結(jié)構(gòu)也有所不同，這將在后續(xù)章節(jié)中做詳細(xì)闡述。這樣提前處理的優(yōu)點(diǎn)就是將段（按標(biāo)點(diǎn)符號(hào)切分生成的）再繼續(xù)切分，以減少之后最大匹配的次數(shù)，從而減少整個(gè)分詞過程的時(shí)間，提高效率，這也是本算法的優(yōu)勢(shì)所在。由于此操作發(fā)生在最大匹配之前，故在本文中稱之為預(yù)處理過程。

本算法實(shí)驗(yàn)中用到的詞庫(kù)來自搜狗實(shí)驗(yàn)室的互聯(lián)網(wǎng)詞庫(kù)（SogouW），其來自于對(duì)SOGOU搜索引擎所索引到的中文互聯(lián)網(wǎng)語料的統(tǒng)計(jì)分析，統(tǒng)計(jì)所進(jìn)行的時(shí)間是2020年10月，涉及到的互聯(lián)網(wǎng)語料規(guī)模在1億頁(yè)面以上。統(tǒng)計(jì)出的詞條數(shù)約為15萬條高頻詞，除標(biāo)出這部分詞條的詞頻信息之外，還標(biāo)出了常用的詞性信息。

3.1 算法理論基礎(chǔ)

舉個(gè)最大匹配的例子：待切分字串為：ABCDEFG。詞典中最大詞長(zhǎng)L為7。詞典W內(nèi)容為：AB、CD、EF。則匹配步驟為：①ABCDEFG[?]W、ABCDEF[?]W、ABCDE[?]W、ABCD[?]W、ABC[?]W、AB∈W，切分：AB/CDEFG；②CDEFG[?]W、CDEF[?]W、CDE[?]W、CD∈W，切分：AB/CD/EFG；③EFG[?]W、EF∈W，切分：AB/CD/EF/G；切分完成?？梢钥闯觯荷鲜鋈街?，總共12次匹配，只有3次匹配是有效的，其他的匹配都是無效的。如果能有方法提前確定CD或EF是一個(gè)詞，那么總的匹配次數(shù)將大大減少。

本文的出發(fā)點(diǎn)就是提前確定句子中常用的詞，然后進(jìn)行最大匹配。為了減少這種提前操作的盲目性，本文提出了基于高頻字的預(yù)處理技術(shù)，高頻字的特點(diǎn)是在文章中出現(xiàn)頻率很高，因此，本算法的目的就是通過對(duì)高頻詞提前識(shí)別這一預(yù)處理方式，來減少無效匹配的次數(shù)，從而提高分詞的效率。

3.2 高頻詞表的內(nèi)容和數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

高頻詞表的內(nèi)容有兩部分組成：①單個(gè)字的高頻字；②含有①中高頻字的所有詞。在化柏林[5]的文中給出了從1989～2005年圖書情報(bào)學(xué)中文核心期刊的42989篇論文的摘要中（其中1996年以前的很多論文沒有摘要）經(jīng)過分詞提取，得到高頻字，除了標(biāo)點(diǎn)符號(hào)分別是：的、和、了、與、在、及、是、對(duì)、中、為、從、等、上、以、下、個(gè)。這就組成了本算法中高頻詞表內(nèi)容中的第一部分。然后將詞庫(kù)（SogouW）中所有含第一部分高頻字的詞找出，構(gòu)成了本算法中高頻詞表內(nèi)容的第二部分，第二部分含有第一部分中的高頻詞的個(gè)數(shù)分別是：的（246）、和（347）、了（1113）、與（195）、在（767）、及（174）、是（493）、對(duì)（422）、中（2089）、為（890）、從（243）、等（250）、上（1415）、以（659）、下（1297）、個(gè)（491）。

孫茂松[6]等人對(duì)整詞二分法、Trie索引樹和逐字二分法三種常用的分詞詞典機(jī)制進(jìn)行了詳細(xì)分析，這些機(jī)制都采用首字Hash索引，而本算法中第一部分中的高頻詞在第二部分中并不總是出現(xiàn)在首位，例如：含“的”的“的士”，“目的”和“有的放矢”。因此，本文根據(jù)原有的詞典機(jī)制，設(shè)計(jì)出三個(gè)表組合的詞典機(jī)制：高頻字表（上述第一部分所有的高頻字）、附近字表（上述第二部分包含高頻字附近的詞即左、右邊首字）和詞表（上述第二部分所有的詞），其結(jié)構(gòu)如圖1所示。

3.3 高頻詞表數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)說明

本算法設(shè)計(jì)了一個(gè)附近字表，其內(nèi)容為高頻字在詞表中出現(xiàn)的左邊首字和右邊首字。當(dāng)在句子中發(fā)現(xiàn)高頻字時(shí)，則只取句子中高頻字的左邊首字和右邊首字在附近字表中查找；若未找到，則表示句子中此高頻單獨(dú)成詞（如“書和筆”中的“和”），無需在詞表中匹配，從而減少高頻字單獨(dú)成詞時(shí)的匹配時(shí)間。當(dāng)句中高頻字不單獨(dú)成詞（如“維護(hù)和平”中的“和”）時(shí)，會(huì)在附近字表中找到“平”，然后將首字和關(guān)鍵字兩字一起出現(xiàn)的詞（即“和平”）在詞表中的區(qū)間進(jìn)行匹配。

3.4 算法描述

輸入：一個(gè)文檔數(shù)據(jù)中所有句子集合中的一個(gè)句子S：{t1，t2，……tn}，tj為S中第j個(gè)字

輸出：經(jīng)預(yù)處理后的句子NS

// LH為高頻字表，其中第k個(gè)區(qū)域是LHk：{Text，Num，Lpos，Rpos}，Text為高頻字；Num為含高頻字的詞的數(shù)目，Lpos為左邊首字指向?qū)?yīng)附近詞表的起始位置；Rpos為右邊首字指向?qū)?yīng)附近詞表的起始位置

// LN為附近字表，其中第k個(gè)區(qū)域是LNk：{ Text， Num， Pos}，Text為首字；Num為含首字和高頻字組合的詞的數(shù)目；Pos為指向?qū)?yīng)詞表的起始位置

// LS為詞表，其中第k個(gè)區(qū)域是LSk：{ Text，Len，Pos}，Text為詞；Len為詞的長(zhǎng)度，即所含字的個(gè)數(shù)；Pos為高頻字在詞中出現(xiàn)的位置

// length為集合或表的長(zhǎng)度，即元素的個(gè)數(shù)

[integer LastPos;//記錄當(dāng)前句子最后一次分割的位置

procedure segment （）

LastPos←0;

for j←1 to S.length do

if LastPos>j then j←LastPos endif //分割位置在當(dāng)前關(guān)鍵字位置之后，表示右部首詞已分割，匹配從最后分割位置開始

for k←1 to LH.length do

if S.tj==LHk.Text then

if S.tj-1≠NULL then

for m←LHk.Lpos to LHk.Rpos do

if S.tj-1==LNm.Text then call match（S，j，LNk）;break; end if

repeat

end if

if LastPos>j then break end if //分割位置在當(dāng)前關(guān)鍵字位置之后，表示右部首詞已分割

if S.tj+1≠NULL then

for m←LHk.Rpos to LHk.Num-LHk.Rpos do

if S.tj+1==LNm.Text then call match（S，j，LNk）;break end if

repeat

end if

break? //跳出循環(huán)，匹配句子中下一字

end if

repeat

repeat

end segment

procedure match （S，j，LNk）? //找出句子中含高頻字的詞，并放入NS中

integer s，e

for n← LNk.Pos to LNk.Pos+ LNk.Len do

s← j - LNk.Pos ， e← s + LNk.Len

if LSn.Test== S.tsts+1……te then

NS.put（S.tsts+1……te） //將匹配出成詞的字串做出標(biāo)記放入NS中

LastPos←e

end if

repeat

end match ]

3.5 算法舉例

例句：“這個(gè)方案的目的是可以高效準(zhǔn)確地實(shí)現(xiàn)中文文檔的主題詞條抽取和詞頻統(tǒng)計(jì)”。經(jīng)過預(yù)處理后句子為：“這個(gè)/方案/的/目的/是/可以/高效準(zhǔn)確地實(shí)現(xiàn)/中文/文檔/的/主題詞條抽取/和/詞頻統(tǒng)計(jì)”（加粗部分為本算法匹配出的高頻詞）。

4 實(shí)驗(yàn)結(jié)果及分析

本文的實(shí)驗(yàn)是基于Apache Jakarta家族中的開源項(xiàng)目Lucene，實(shí)驗(yàn)數(shù)據(jù)來自搜狗實(shí)驗(yàn)室的全網(wǎng)新聞數(shù)據(jù)（SogouCA）的精簡(jiǎn)版（一個(gè)月數(shù)據(jù)， 437MB），其數(shù)據(jù)來自若干新聞?wù)军c(diǎn)2020年5月-6月期間奧運(yùn)、體育、IT、國(guó)內(nèi)、國(guó)際等18個(gè)頻道的新聞數(shù)據(jù)，提供URL和正文信息。本實(shí)驗(yàn)針對(duì)正向最大匹配算法，在相同實(shí)驗(yàn)環(huán)境下，選取不同的數(shù)據(jù)集，進(jìn)行三次數(shù)據(jù)測(cè)試，其實(shí)驗(yàn)結(jié)果見表1。

從表1可以看出，經(jīng)過預(yù)處理后的變化：①分詞速度有明顯的提高，證明了此預(yù)處理技術(shù)的可行性；②分詞正確率沒有降低，因?yàn)榇祟A(yù)處理過程同樣是基于詞典的匹配過程。這說明該方法具有一定的實(shí)用性。切分錯(cuò)誤原因主要有兩個(gè)方面：一是未登錄到字典中的詞；二是含有錯(cuò)別字的字串。

5 結(jié)論

隨著中文信息處理技術(shù)的發(fā)展和互聯(lián)網(wǎng)信息數(shù)據(jù)的日益增加，對(duì)中文分詞的速率要求越來越高，作為中文分詞基礎(chǔ)的詞典機(jī)制研究已成熟。本文研究現(xiàn)有的基于詞典的最大匹配算法的機(jī)制，根據(jù)高頻詞的特點(diǎn)，通過提前匹配出所有高頻詞進(jìn)而把整個(gè)文本分成更多的段，從而提高分詞的速度，并且高頻詞出現(xiàn)次數(shù)越多，該算法的性能越好。當(dāng)然此算法只是在分詞速度上有所提高，而對(duì)于正向最大匹配算法的分詞準(zhǔn)確率及未登陸詞的識(shí)別等沒有改善。

參考文獻(xiàn)（References）：

[1] LI X， MENG Y， SUN X， et al. Is word segmentationnecessary for deeplearning of chinese representations？[c].Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics，2019：359-401

[2] 宗成慶.統(tǒng)計(jì)自然語言處理[M].北京：清華大學(xué)出版社，2008

[3] 王佳楠，梁永全.中文分詞研究綜述[J].軟件導(dǎo)刊，2021，20（4）：247-252

[4] 吳育良.百度中文分詞技術(shù)淺析[J].河南圖書館學(xué)刊，2008，28（4）：115-117

[5] 化柏林.知識(shí)抽取中的停用詞處理技術(shù)[J].知識(shí)組織與知識(shí)管理，2007（8）：48-51

[6] 孫茂松，左正平，黃昌寧.漢語自動(dòng)分詞詞典機(jī)制的實(shí)驗(yàn)研究[J].中文信息學(xué)報(bào)，1999，14（1）：1-6