漢語分詞最大匹配方法

1、,漢語分詞:最大匹配方法,張月（李正華指導(dǎo)）2015.9.15,,中文分詞的目的是將漢字序列切分為詞序列舉例說明：輸入句子：他是研究生物化學(xué)的?？赡艿姆衷~：他 是 研究生 物化 學(xué) 的 。 他 是 研究生 物 化學(xué) 的 。 他 是 研究 生物 化學(xué) 的 。合理答案：他 是 研究 生物 化學(xué) 的 。,分詞任務(wù),從左到右尋找詞的最大匹配（

2、每次都貪心的找一個最長的詞典詞）我們有一個詞典，用于存放所有可能的詞語，即除了單字，分詞結(jié)果中的每個詞均要在詞典中出現(xiàn)。,正向最大匹配算法,從左到右尋找詞的最大匹配從當(dāng)前位置開始，向右截取最大長度，組成當(dāng)前詞；和字典中的詞逐一進行匹配；若匹配成功，則進行下次匹配，下次匹配的當(dāng)前位置則為這次詞后面的那個字。如果未能匹配，就縮短長度（長度減一）重新截取，直到當(dāng)前詞與詞典中的詞匹配或者當(dāng)前詞是單字；,正向最大匹配算法,

3、從左到右尋找詞的最大匹配,正向最大匹配算法,例子：我是中國人 詞典中包括【中國、中國人】假設(shè)：最大詞長為3,正向最大匹配算法,例子：我是中國人 第一輪：第一次："我是中"是選取的詞，在詞典中 未找到匹配項 第二次："我是"是選取的詞，在詞典中未 找到匹配項 第三次："我"是選取的詞，是單字，匹配 成功,正向最大

4、匹配算法,例子：我/是中國人 第二輪：第一次："是中國"是選取的詞，在詞典中 未找到匹配項 第二次："是中"是選取的詞，在詞典中未 找到匹配項 第三次："是"是選取的詞，是單字，匹配 成功,正向最大匹配算法,例子：我/是/中國人/ 第三輪：第一次："中國人"是選取的詞，在詞典中

5、 找到匹配項，匹配成功。 至此，短句中所有字匹配結(jié)束，該短句分詞結(jié)束。,正向最大匹配算法,從右到左尋找詞的最大匹配 與正向最大匹配的區(qū)別在于，從句子的末尾開始，向左邊截取一定的長度去匹配。,逆向最大匹配算法,從右到左尋找詞的最大匹配,逆向最大匹配算法,例子：我是中國人 第一輪：第一次："中國人"是選取的詞，在詞典中 找到匹配項，匹配成功,逆向最大匹配算法,例子：我是/

6、中國人 第二輪：第一次：因為剩余字?jǐn)?shù)已不足3，小于假 定的最大詞長，所以選擇"我是"， 在詞典中未找到匹配項 第二次："是"是選取的詞，是單字，匹配 成功,逆向最大匹配算法,例子：我/是/中國人 第三輪：第一次：因為剩余字?jǐn)?shù)已不足3，小于假 定的最大詞長，所以選擇"我"， 是單字，匹配成功 至此，短句中所

7、有字匹配結(jié)束，該短句 分詞結(jié)束。,逆向最大匹配算法,給定人工標(biāo)注的分詞答案，評價某一算法給出的結(jié)果。正確率(Precision) = 正確識別的詞數(shù) / 識別出的個體總數(shù)召回率(Recall) = 正確識別的個體總數(shù) / 測試集中存在的個體總數(shù)F值 = 正確率* 召回率 * 2 / (正確率 + 召回率),分詞算法評價：正確率/召回率/F值,思考：評價程序應(yīng)該怎么寫？,utf-8是不定長的，根據(jù)左側(cè)位1的個數(shù)來決定

8、占用了幾個字節(jié)，中文一般占2-4個字節(jié),UTF-8編碼,gbk的編碼方式是中文占兩個字節(jié)，英文占一個字節(jié),根據(jù)第一個字節(jié)的最高位來判斷如果第一個字節(jié)的最高位是1，則是兩個字節(jié)連在一起為一個字符，否則一個字節(jié)為一個字符中文的編碼范圍 第一個字節(jié) | 第二個字節(jié) 0x81-0xFE(129-254) | 0x40-0xFE(64-254),GBK編碼,,數(shù)據(jù)格式,四個編程任務(wù)（編程語言不限，Li

9、nux上運行）,1. 構(gòu)建詞典（3分）給一個人工分好詞的文件data.conll，構(gòu)建一個詞典，輸出到一個文件中，起名為word.dict（格式自定義）2. 構(gòu)建毛文本（2分）將data.conll文件中的格式修改為：每行一句話，詞語之間無空格，起名為data.txt,四個編程任務(wù)（編程語言不限，Linux上運行）,3. 前向（5分）或（二者只可以選一個）后向（7分）最大匹配分詞算法給定詞典word.dict，對data.txt