陳書雨 曹集翔 姚寒冰

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

關鍵詞： 高頻詞； 預處理； 中文分詞

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

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

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

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

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

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

正向最大匹配算法的切分原理是：①將文本內容按標點符號分成句子集。②對于句子集中每一句子，假定詞典中最大詞長為L，對于待切分的句子，從句首取長度為L的字串進行匹配，如果匹配成功則認為此字串為一個詞，再從下一個字開始繼續(xù)該過程；如果匹配不成功，則去掉此字串的最后一個字進行匹配，直至匹配成功或子句為空。例如：對于文本中的字串ABCD，其中AB∈W，ABC∈W，ABCD[?]W，那么切分結果為：ABC/D。

3 高頻詞的預處理技術及算法設計

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

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

3.1 算法理論基礎

舉個最大匹配的例子：待切分字串為：ABCDEFG。詞典中最大詞長L為7。詞典W內容為：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是一個詞，那么總的匹配次數(shù)將大大減少。

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

3.2 高頻詞表的內容和數(shù)據(jù)結構設計

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

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

3.3 高頻詞表數(shù)據(jù)結構設計說明

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

3.4 算法描述

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

輸出：經預處理后的句子NS

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

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

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

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

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

procedure segment （）

LastPos←0;

for j←1 to S.length do

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

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 //分割位置在當前關鍵字位置之后，表示右部首詞已分割

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） //將匹配出成詞的字串做出標記放入NS中

LastPos←e

end if

repeat

end match ]

3.5 算法舉例

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

4 實驗結果及分析

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

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

5 結論

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

參考文獻（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)計自然語言處理[M].北京：清華大學出版社，2008

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

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

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

[6] 孫茂松，左正平，黃昌寧.漢語自動分詞詞典機制的實驗研究[J].中文信息學報，1999，14（1）：1-6